二叉树（链式存储）
1、树数据结构与数组和链表的区别
数组存储方式的分析
优点： 通过 下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。缺点： 如果要检索具体某个值，或者插入值( 按一定顺序) 会整体移动，效率较低
链式存储方式的分析
优点： 在一定程度上对数组存储方式有优化(比如： 插入一个数值节点，只需要将插入节点，链接到链表中即可， 删除效率也很好)。缺点： 在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历）
树存储方式的分析
能提高数据存储 ， 读取的效率, 比如利用 二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度，同时也 可以保证数据的 插入，删除，修改的速度。案例: [7, 3, 10, 1, 5, 9, 12]
2、树的示意图及常用术语
3、二叉树的概念
树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树（注： <=2）二叉树的子节点分为左节点和右节点示意图
如果该二叉树的所有叶子节点都在 最后一层，并且**结点总数= 2^n -1 **（等比数列求和） , n 为层数，则我们称为满二叉树
完全二叉树是这样的二叉树：
①完全二叉树的倒数第二行及之前的行，都与满二叉树相同。
②倒数第一行右半部分可以是空的，也可以是满的，但不能有单个的出现！
③倒数第一行左半部分可以是空的，也可以是满的，也可有单个的出现，但有且只能有一个单个，且必须是它父亲的左孩子！
…………
这我们就知道了，满二叉树就是完全二叉树的特殊情况！
4、二叉树遍历的说明
使用 前序，中序和后序对下面的二叉树进行遍历.
前序遍历: 先输出父节点，再遍历左子树和右子树 （根左右）中序遍历: 先遍历左子树，再输出父节点，再遍历右子树 （左根右）后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点 （左右根）小结: 看输出父节点的顺序（即遍历父节点是在前面，中间还是后面），就确定是前序，中序还是后序
5、二叉树遍历实验
应用实例的说明和思路
代码实现
public class BinaryTreeDemo {
public static void main(String
[] args
) {
BinaryTree binaryTree
= new BinaryTree();
HeroNode root
= new HeroNode(1,"宋江");
HeroNode node2
= new HeroNode(2,"吴勇");
HeroNode node3
= new HeroNode(3,"卢俊义");
HeroNode node4
= new HeroNode(4,"林冲");
HeroNode node5
= new HeroNode(5,"关胜");
root
.setLeft(node2
);
root
.setRight(node3
);
node3
.setRight(node4
);
node3
.setLeft(node5
);
binaryTree
.setRoot(root
);
System
.out
.println("前序遍历");
binaryTree
.PreOrder();
System
.out
.println("中序遍历");
binaryTree
.infixOrder();
System
.out
.println("后序遍历");
binaryTree
.postOrder();
}
}
class BinaryTree {
private HeroNode root
;
public void setRoot(HeroNode root
) {
this.root
= root
;
}
public void PreOrder(){
if (this.root
!= null
){
this.root
.PreOrder();
}else {
System
.out
.println("二叉树为空， 无法遍历");
}
}
public void infixOrder(){
if (this.root
!= null
){
this.root
.infixOrder();
}else {
System
.out
.println("二叉树为空， 无法遍历");
}
}
public void postOrder(){
if (this.root
!= null
){
this.root
.postOrder();
}else {
System
.out
.println("二叉树为空， 无法遍历");
}
}
}
class HeroNode{
private int no
;
private String name
;
private HeroNode left
;
private HeroNode right
;
public HeroNode(int no
, String name
) {
this.no
= no
;
this.name
= name
;
}
public int getNo() {
return no
;
}
public void setNo(int no
) {
this.no
= no
;
}
public String
getName() {
return name
;
}
public void setName(String name
) {
this.name
= name
;
}
public HeroNode
getLeft() {
return left
;
}
public void setLeft(HeroNode left
) {
this.left
= left
;
}
public HeroNode
getRight() {
return right
;
}
public void setRight(HeroNode right
) {
this.right
= right
;
}
@Override
public String
toString() {
return "HeroNode{" +
"no=" + no
+
", name='" + name
+ '\'' +
'}';
}
public void PreOrder(){
System
.out
.println(this);
if (this.left
!= null
){
this.left
.PreOrder();
}
if (this.right
!= null
){
this.right
.PreOrder();
}
}
public void infixOrder(){
if (this.left
!= null
){
this.left
.infixOrder();
}
System
.out
.println(this);
if (this.right
!= null
){
this.right
.infixOrder();
}
}
public void postOrder(){
if (this.left
!= null
){
this.left
.postOrder();
}
if (this.right
!= null
){
this.right
.postOrder();
}
System
.out
.println(this);
}
}
6、二叉树-查找指定节点
要求：
请编写前序查找，中序查找和后序查找的方法。并分别使用三种查找方式，查找 herono = 5 的节点并分析各种查找方式，分别比较了多少次思路分析图解
代码实现（只放了新加的，前面的见上一个代码块）
HeroNode类：
public HeroNode
preOrderSearch(int no
){
System
.out
.println("进入前序遍历查找");
if (this.no
== no
){
return this;
}
HeroNode resNode
= null
;
if (this.left
!= null
){
resNode
= this.left
.preOrderSearch(no
);
}
if (resNode
!= null
){
return resNode
;
}
if (this.right
!= null
){
resNode
= this.right
.preOrderSearch(no
);
}
return resNode
;
}
public HeroNode
infixOrderSearch(int no
){
HeroNode resNode
= null
;
if (this.left
!= null
){
resNode
= this.left
.infixOrderSearch(no
);
}
if (resNode
!= null
){
return resNode
;
}
System
.out
.println("进入中序遍历查找");
if (this.no
== no
){
return this;
}
if (this.right
!= null
){
resNode
= this.right
.infixOrderSearch(no
);
}
return resNode
;
}
public HeroNode
postOrderSearch(int no
){
HeroNode resNode
= null
;
if (this.left
!= null
){
resNode
= this.left
.postOrderSearch(no
);
}
if (resNode
!= null
){
return resNode
;
}
if (this.right
!= null
){
resNode
= this.right
.postOrderSearch(no
);
}
if (resNode
!= null
){
return resNode
;
}
System
.out
.println("进入后序遍历查找");
if (this.no
== no
){
return this;
}
return resNode
;
}
BinaryTree类：
public HeroNode
preOrderSearch(int no
){
if (root
!= null
){
return root
.preOrderSearch(no
);
}else {
return null
;
}
}
public HeroNode
infixOrderSearch(int no
){
if (root
!= null
){
return root
.infixOrderSearch(no
);
}else {
return null
;
}
}
public HeroNode
postOrderSearch(int no
){
if (root
!= null
){
return root
.postOrderSearch(no
);
}else {
return null
;
}
}
main里面：
System
.out
.println("后序遍历方式~~~~~");
HeroNode resNode
= binaryTree
.postOrderSearch(5);
if (resNode
!= null
){
System
.out
.printf("找到了， 信息为 no=%d name=%s",resNode
.getNo(),resNode
.getName());
}else {
System
.out
.printf("没有找到 no=%d 的英雄",5);
}
7、二叉树-删除节点
要求：（不考虑删除该节点后是否要把左或右孩子补上来）
如果删除的节点是叶子节点，则删除该节点如果删除的节点是非叶子节点，则删除该子树.测试，删除掉 5 号叶子节点 和 3 号子树.完成删除思路分析
(注： 首先处理的那步，还包含要删除的节点是根节点的情况，按照要求就是把二叉树置空（这条语句写在BinaryTree类里）
对于第一步，其实就是判断当前节点的左孩子或者右孩子是否为我们要删除的节点，因为如果我们是判断当前节点是否要删除的话，那就删不掉了（因为当引用指向要删除的节点的时候，我们无法得到他的父节点）
)
代码实现（其它的代码见上一个代码块） HeroNode类：
public void delNode(int no
){
if (this.left
!= null
&& this.left
.no
== no
){
this.left
= null
;
return;
}
if (this.right
!= null
&& this.right
.no
== no
){
this.right
= null
;
return;
}
if (this.left
!= null
){
this.left
.delNode(no
);
}
if (this.right
!= null
){
this.right
.delNode(no
);
}
}
BinaryTree类：
public void delNode(int no
){
if (root
!= null
){
if (root
.getNo() == no
){
root
= null
;
}else {
root
.delNode(no
);
}
}else {
System
.out
.println("空树！！ 不能删除~");
}
}
BinaryTreeDemo类：
System
.out
.println("删除前， 前序遍历");
binaryTree
.PreOrder();
binaryTree
.delNode(5);
System
.out
.println("删除后， 前序遍历");
binaryTree
.PreOrder();
