二叉树（一）：树的基础知识以及相关的基础操作
一.基础知识
**1.引进树结构的原因：**结合了数组存储和链表存储的优点，能提高数据存储和读取的效率。 **2.满二叉树：**该二叉树的所有叶子节点都在最后一层，并且节点总数=2^n-1,n为层数。 **3.完全二叉树：**所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子结点在左边连续，倒数第二层的叶子结点在右边连续。
二，基本操作
1.遍历： 前序遍历：根左右 中序遍历：左根右 后续遍历：左右根
2.查找指定的结点： 前序遍历查找： （1）比较当前节点是不是 （2）判断当前节点的左子节点是否为空，如果不为空，则递归前序查找 如果左递归前序查找，找到节点，则返回 （3）右递归前序查找，找到节点则返回，否则继续判断 当前的节点的右子节点是否为空，如果不为空，则继续向右递归前序查找
中序遍历查找（就是前序遍历查找的顺序变一下） 后续遍历查找（就是前序遍历查找的顺序变一下）
3.删除指定的结点
要求： 递归删除结点 （1）如果删除节点是叶子结点，则删除该节点 （2）如果删除节点是非叶子结点，则直接删除这个树
思路： （1）.因为我们的二叉树是单向的，所以我们是判断当前节点的子节点是否需要删除节点，而不能判断当前这个节点是不是需要删除的结点。 （2）.如果当前节点的左子节点不为空，并且左子节点就是要删除的结点，就将 this.left = null, 并且就返回（结束递归删除）。 （3）.如果当前节点的右子节点不为空，并且右子节点就是要删除的结点，就将 this.right = null, 并且就返回（结束递归删除）。 （4）.如果第2步和第三步没有删除节点，那我们就需要向左子树进行递归删除。 （5）.如果第4步也没有删除节点，则应当向右子树进行递归删除。
三.相关代码
package com
.cs
.tree
;
import com
.sun
.xml
.internal
.ws
.addressing
.WsaActionUtil
;
public class BinaryTreeDemo {
public static void main(String
[] args
) {
BinaryTree binaryTree
= new BinaryTree();
HeroNode root
= new HeroNode(1,"jack");
HeroNode node2
= new HeroNode(2,"rose");
HeroNode node3
= new HeroNode(3,"daniel");
HeroNode node4
= new HeroNode(4,"james");
HeroNode node5
= new HeroNode(5,"kobe");
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();
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);
}
System
.out
.println("删除前，前序遍历");
binaryTree
.preOrder();
binaryTree
.delNode(5);
System
.out
.println("删除后，前序遍历");
binaryTree
.preOrder();
}
}
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
.infixOrder();
}else {
System
.out
.println("二叉树为空，无法遍历");
}
}
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
;
}
}
public void delNode(int no
){
if (root
!= null
){
if (root
.getNo() == no
){
root
= null
;
}else {
root
.delNode(no
);
}
}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);
}
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
;
}
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
);
}
}
}
