總目錄：地址如下看總綱
1、樹的常用術(shù)語
image.png
1、節(jié)點：就是節(jié)點，沒什么雞毛好講
2、根節(jié)點：就是最上層，祖宗
3、父節(jié)點：
4、子節(jié)點：
5、葉子節(jié)點：沒有子節(jié)點的節(jié)點
6、節(jié)點的權(quán)：就是節(jié)點值（大多時候是個對象）
7、路徑：從root節(jié)點找到該節(jié)點的路線
8、層
9、子樹
10、樹的高度：最大層數(shù)
11、森林 :多顆子樹構(gòu)成森林
2、二叉樹的概念
- 樹有很多種，每個節(jié)點最多只能有兩個子節(jié)點的一種形式稱為二叉樹。
- 二叉樹的子節(jié)點分為左節(jié)點和右節(jié)點。
以下三種均為二叉樹：
image.png如果該二叉樹的所有葉子節(jié)點都在最后一層，并且結(jié)點總數(shù)= 2^n -1 , n 為層數(shù)，則我們稱為滿二叉樹
image.png如果該二叉樹的所有葉子節(jié)點都在最后一層或者倒數(shù)第二層，而且最后一層的葉子節(jié)點在左邊連續(xù)，倒數(shù)第二層的葉子節(jié)點在右邊連續(xù)，我們稱為完全二叉樹。
image.png
3、二叉樹的遍歷說明
- 前序遍歷: 先輸出父節(jié)點，再遍歷左子樹和右子樹
- 中序遍歷: 先遍歷左子樹，再輸出父節(jié)點，再遍歷右子樹
- 后序遍歷: 先遍歷左子樹，再遍歷右子樹，最后輸出父節(jié)點
- 小結(jié): 看輸出父節(jié)點的順序，就確定是前序，中序還是后序
4、前，中，后序遍歷詳解
- 創(chuàng)建一顆二叉樹
- 前序遍歷
2.1 先輸出當前節(jié)點(初始的時候是root節(jié)點)
2.2 如果左子節(jié)點不為空，則遞歸繼續(xù)前序遍歷
2.3 如果右子節(jié)點不為空，則遞歸繼續(xù)前序遍歷- 中序遍歷
3.1 如果當前節(jié)點的左子節(jié)點不為空，則遞歸中序遍歷
3.2 輸出當前節(jié)點
3.3 如果當前節(jié)點的右子節(jié)點不為空，則遞歸中序遍歷后序遍歷
4.1 如果當前節(jié)點的左子節(jié)點不為空，則遞歸后序遍歷
4.2 如果當前節(jié)點的右子節(jié)點不為空，則遞歸后序遍歷
4.3 輸出當前節(jié)點
image.png
5、前，中，后序代碼實現(xiàn)
package com.kk.datastructure.tree;
/**
* title: 二叉樹的前,中,后序遍歷
* @author 阿K
* 2020年12月29日 下午11:29:56
*/
public class BinaryTreeDemo {
public static void main(String[] args) {
// 創(chuàng)建二叉樹
BinaryTree binaryTree = new BinaryTree();
// 創(chuàng)建需要的結(jié)點
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, "關(guān)勝");
// 加入樹
root.setLeft(node2);
root.setRight(node3);
node3.setRight(node4);
node3.setLeft(node5);
binaryTree.setRoot(root);
System.out.println("前序遍歷，預計結(jié)果：1，2，3，5，4");
binaryTree.perOrder();
System.out.println("中序遍歷，預計結(jié)果：2，1，5，3，4");
binaryTree.infixOrder();
System.out.println("后序遍歷，預計結(jié)果：2，5，4，3，1");
binaryTree.postOrder();
}
}
// 定義二叉樹
class BinaryTree {
private HeroNode root;// 根節(jié)點
public void setRoot(HeroNode root) {
this.root = root;
}
// 前序遍歷
public void perOrder() {
if (this.root != null) {
this.root.perOrder();
} 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("二叉樹為空，無法遍歷~");
}
}
}
// 定義節(jié)點
class HeroNode {
private int no;
private String name;
private HeroNode left; // 左節(jié)點（默認為null）
private HeroNode right; // 右節(jié)點（默認為null）
public HeroNode(int no, String name) {
this.no = no;
this.name = name;
}
// 節(jié)點的前序遍歷
public void perOrder() {
// 1.先輸出入父節(jié)點
System.out.println(this);
// 2.遞歸左子樹前序遍歷
if (this.left != null) {
this.left.perOrder();
}
// 3.遞歸右子樹前序遍歷
if (this.right != null) {
this.right.perOrder();
}
}
// 節(jié)點的中序遍歷
public void infixOrder() {
// 1.遞歸左子樹中序遍歷
if (this.left != null) {
this.left.infixOrder();
}
// 2.輸出父節(jié)點
System.out.println(this);
// 3.遞歸右子樹中序遍歷
if (this.right != null) {
this.right.infixOrder();
}
}
// 節(jié)點的后序遍歷
public void postOrder() {
// 1.遞歸左子樹后序遍歷
if (this.right != null) {
this.left.postOrder();
}
// 2.遞歸右子樹后序遍歷
if (this.right != null) {
this.right.postOrder();
}
// 3.輸出父節(jié)點
System.out.println(this);
}
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 + "]";
}
}
6、前，中，后序查找思路
- 前序查找思路：
1、先判斷當前結(jié)點的 no 是否等于要查找的
2、如果是相等,則返回當前結(jié)點
3、如果不等，則判斷當前結(jié)點的左子節(jié)點是否為空，如果不為空，則遞歸前序查找4、如果左遞歸前序查找，找到結(jié)點，則返回，否繼續(xù)判斷，當前的結(jié)點的右子節(jié)點是否為空，如果不空，則繼續(xù)向右遞歸前序查找.- 中序查找思路：
1、判斷當前結(jié)點的左子節(jié)點是否為空，如果不為空，則遞歸中序查找
2、如果找到，則返回，如果沒有找到，就和當前結(jié)點比較，如果是則返回當前結(jié)點，否則繼續(xù)進行右遞歸的中序查找
3、如果右遞歸中序查找，找到就返回，否則返回 null后序查找思路
1、判斷當前結(jié)點的左子節(jié)點是否為空，如果不為空，則遞歸后序查找
2、如果找到，就返回，如果沒有找到，就判斷當前結(jié)點的右子節(jié)點是否為空，如果不為空,則右遞歸進行后序查找，如果找到，就返回
3、最后和當前結(jié)點進行比較，是則返回，否則返回 null
image.png
7、前，中，后序查找代碼
package com.kk.datastructure.tree;
/**
* title: 前中后序查找
* @author 阿K
* 2020年12月30日 下午11:49:44
*/
public class BinaryTreeDemo2 {
public static void main(String[] args) {
// 創(chuàng)建二叉樹
BinaryTree binaryTree = new BinaryTree();
// 創(chuàng)建需要的結(jié)點
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, "關(guān)勝");
// 加入樹
root.setLeft(node2);
root.setRight(node3);
node3.setRight(node4);
node3.setLeft(node5);
binaryTree.setRoot(root);
System.out.println("前序遍歷，預計統(tǒng)計次數(shù)：4 ===> 查找順序 1，2，3，5，4");
binaryTree.perOrderSearch(5);
System.out.println("中序遍歷，預計統(tǒng)計次數(shù)：3 ===》 查找順序 2，1，5，3，4");
binaryTree.infixOrderSearch(5);
//
System.out.println("后序遍歷，預計統(tǒng)計次數(shù)：2 ===》 查找順序 2,5, 4,3,1");
binaryTree.postOrderSearch(5);
}
}
// 定義二叉樹
class BinaryTree {
private HeroNode root;// 根節(jié)點
public void setRoot(HeroNode root) {
this.root = root;
}
// 前序遍歷查找
public HeroNode perOrderSearch(int no) {
if (root != null) {
return root.perOrderSearch(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;
}
}
}
// 定義節(jié)點
class HeroNode {
private int no;
private String name;
private HeroNode left; // 左節(jié)點（默認為null）
private HeroNode right; // 右節(jié)點（默認為null）
public HeroNode(int no, String name) {
this.no = no;
this.name = name;
}
/**
* 須知：關(guān)于查找次數(shù)的統(tǒng)計
* 為了有效的統(tǒng)計出正確的次數(shù)，應(yīng)該放在 if(this.no == no) 上面
* @param no
* @return
*/
// 節(jié)點的前序遍歷查找
public HeroNode perOrderSearch(int no) {
System.out.println("記錄前序遍歷查找，打印次數(shù)決定查找運行次數(shù)！");
// 比較當前節(jié)點是否
if (this.no == no) {
return this;
}
// 1、判斷當前節(jié)點的左子節(jié)點是否為空，若不為空，則左遞歸前序查找
// 2、若左遞歸前序查找，找到節(jié)點則返回
HeroNode resNode = null;
if (this.left != null) {
resNode = this.left.perOrderSearch(no);
}
if (resNode != null) {// 說明在左子樹上找到了
return resNode;
}
// 1、當前節(jié)點的右子樹是否為空，若不為空，則右遞歸前序查找
// 2、若右遞歸前序查找，找到節(jié)點則返回
if (this.right != null) {
resNode = this.right.perOrderSearch(no);
}
return resNode;
}
// 節(jié)點的中序遍歷查找
public HeroNode infixOrderSearch(int no) {
// 1、判斷當前左節(jié)點是否為空，若不為空，則繼續(xù)左遞歸中序遍歷查找
HeroNode resNode = null;
if (this.left != null) {
resNode = this.left.infixOrderSearch(no);
}
// 2、若不為空，則返回（既找到）
if (resNode != null) {
return resNode;
}
System.out.println("進入中序查找的次數(shù)統(tǒng)計");
// 3、和當前節(jié)點進行比較，若是則返回
if (this.no == no) {
return this;
}
// 4、若不是，則繼續(xù)右遞歸中序遍歷查找
if (this.right != null) {
resNode = this.right.infixOrderSearch(no);
}
return resNode;
}
// 節(jié)點的后序遍歷查找
public HeroNode postOrderSearch(int no) {
// 1、判斷當前左節(jié)點是否為空，若不為空，則繼續(xù)左遞歸后序遍歷查找
HeroNode resNode =null;
if(this.left!=null) {
resNode = this.left.postOrderSearch(no);
}
// 2、若不為空，則返回
if(resNode !=null) {
return resNode;
}
// 3、若當前左子樹沒有找到，則開始右子樹后序遞歸遍歷查找
if(this.right!=null) {
resNode = this.right.postOrderSearch(no);
}
// 4、若不為空，則返回
if(resNode!=null) {
return resNode;
}
System.out.println("進入后序號查找次數(shù)統(tǒng)計");
// 5、若左右子樹都沒有找到，就比較當前節(jié)點是否
if(this.no==no) {
return this;
}
return resNode;
}
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 + "]";
}
}
8、刪除樹節(jié)點思路分析（入門版）
- 規(guī)定
1、若刪除的節(jié)點是葉子節(jié)點，則刪除該節(jié)點
2、若刪除的節(jié)點是非葉子節(jié)點，則刪除該子樹- 思路：
1、判空，若只有一個 root 根節(jié)點存在，則等價于二叉樹置空
2、故當前入門級二叉樹是單向的，所以我們是只判斷當前節(jié)點的子節(jié)點是否為需要刪除的
3、若當前節(jié)點的左子節(jié)點不為空，并且左子節(jié)點就是要刪除的節(jié)點，就將 this.left =null(既刪除)，并返回（return 結(jié)束遞歸）
4、若當前節(jié)點的右子節(jié)點不為空，并且右子節(jié)點就是要刪除的節(jié)點，就將 this.rigth=null (既刪除)，并返回（return 結(jié)束遞歸）
5、若 以上兩步都沒有刪除節(jié)點，那么就進行左子樹遞歸刪除
6、如若以上三步都沒有刪除，則進行右子樹遞歸刪除
9、刪除樹節(jié)點代碼（入門版）
package com.kk.datastructure.tree;
/**
* title: 刪除節(jié)點
* @author 阿K
* 2020年12月31日 下午11:57:45
*/
public class BinaryTreeDemo3 {
public static void main(String[] args) {
// 創(chuàng)建二叉樹
BinaryTree binaryTree = new BinaryTree();
// 創(chuàng)建需要的結(jié)點
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, "關(guān)勝");
// 加入樹
root.setLeft(node2);
root.setRight(node3);
node3.setRight(node4);
node3.setLeft(node5);
binaryTree.setRoot(root);
// 刪除測試。。
System.out.println("刪除前：");
binaryTree.perOrder();
binaryTree.delNode(3);
System.out.println("刪除后：");
binaryTree.perOrder();
}
}
// 定義二叉樹
class BinaryTree {
// 前序遍歷
public void perOrder() {
if (this.root != null) {
this.root.perOrder();
} else {
System.out.println("二叉樹為空，無法遍歷~");
}
}
private HeroNode root;// 根節(jié)點
public void setRoot(HeroNode root) {
this.root = root;
}
// 刪除節(jié)點
public void delNode(int no) {
if (this.root != null) {
// 1、判空，若只有一個 root 根節(jié)點存在，則等價于二叉樹置空
if (root.getNo() == no) {
root = null;
} else {
// 否則 遞歸刪除
root.delNode(no);
}
} else {
System.out.println("當前二叉樹為空，刪個雞毛？？");
}
}
}
// 定義節(jié)點
class HeroNode {
private int no;
private String name;
private HeroNode left; // 左節(jié)點（默認為null）
private HeroNode right; // 右節(jié)點（默認為null）
public HeroNode(int no, String name) {
this.no = no;
this.name = name;
}
// 節(jié)點刪除
// 1、若刪除的節(jié)點是葉子節(jié)點，則刪除該節(jié)點
// 2、若刪除的節(jié)點是非葉子節(jié)點，則刪除該子樹
public void delNode(int no) {
// 2、故當前入門級二叉樹是單向的，所以我們是只判斷當前節(jié)點的子節(jié)點是否為需要刪除的
// 3、若當前節(jié)點的左子節(jié)點不為空，并且左子節(jié)點就是要刪除的節(jié)點，就將 this.left =null(既刪除)，并返回（return 結(jié)束遞歸）
// 4、若當前節(jié)點的右子節(jié)點不為空，并且右子節(jié)點就是要刪除的節(jié)點，就將 this.rigth=null (既刪除)，并返回（return 結(jié)束遞歸）
// 5、若 以上兩步都沒有刪除節(jié)點，那么就進行左子樹遞歸刪除
// 6、如若以上三步都沒有刪除，則進行右子樹遞歸刪除
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);
}
}
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;
}
// 節(jié)點的前序遍歷
public void perOrder() {
// 1.先輸出入父節(jié)點
System.out.println(this);
// 2.遞歸左子樹前序遍歷
if (this.left != null) {
this.left.perOrder();
}
// 3.遞歸右子樹前序遍歷
if (this.right != null) {
this.right.perOrder();
}
}
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + "]";
}
}
