總目錄：地址如下看總綱
1、樹的常用術(shù)語
image.png
1适滓、節(jié)點(diǎn)：就是節(jié)點(diǎn)岖沛，沒什么雞毛好講
2鲜滩、根節(jié)點(diǎn)：就是最上層，祖宗
3鸿市、父節(jié)點(diǎn)：
4锯梁、子節(jié)點(diǎn)：
5、葉子節(jié)點(diǎn)：沒有子節(jié)點(diǎn)的節(jié)點(diǎn)
6焰情、節(jié)點(diǎn)的權(quán)：就是節(jié)點(diǎn)值（大多時(shí)候是個(gè)對(duì)象）
7陌凳、路徑：從root節(jié)點(diǎn)找到該節(jié)點(diǎn)的路線
8、層
9内舟、子樹
10冯遂、樹的高度：最大層數(shù)
11、森林 :多顆子樹構(gòu)成森林
2谒获、二叉樹的概念
- 樹有很多種蛤肌，每個(gè)節(jié)點(diǎn)最多只能有兩個(gè)子節(jié)點(diǎn)的一種形式稱為二叉樹。
- 二叉樹的子節(jié)點(diǎn)分為左節(jié)點(diǎn)和右節(jié)點(diǎn)批狱。
以下三種均為二叉樹：
image.png如果該二叉樹的所有葉子節(jié)點(diǎn)都在最后一層裸准，并且結(jié)點(diǎn)總數(shù)= 2^n -1 , n 為層數(shù)，則我們稱為滿二叉樹
image.png如果該二叉樹的所有葉子節(jié)點(diǎn)都在最后一層或者倒數(shù)第二層赔硫，而且最后一層的葉子節(jié)點(diǎn)在左邊連續(xù)炒俱，倒數(shù)第二層的葉子節(jié)點(diǎn)在右邊連續(xù)，我們稱為完全二叉樹。
image.png
3权悟、二叉樹的遍歷說明
- 前序遍歷: 先輸出父節(jié)點(diǎn)砸王，再遍歷左子樹和右子樹
- 中序遍歷: 先遍歷左子樹，再輸出父節(jié)點(diǎn)峦阁，再遍歷右子樹
- 后序遍歷: 先遍歷左子樹谦铃，再遍歷右子樹，最后輸出父節(jié)點(diǎn)
- 小結(jié): 看輸出父節(jié)點(diǎn)的順序榔昔，就確定是前序驹闰，中序還是后序
4、前撒会，中嘹朗，后序遍歷詳解
- 創(chuàng)建一顆二叉樹
- 前序遍歷
2.1 先輸出當(dāng)前節(jié)點(diǎn)(初始的時(shí)候是root節(jié)點(diǎn))
2.2 如果左子節(jié)點(diǎn)不為空，則遞歸繼續(xù)前序遍歷
2.3 如果右子節(jié)點(diǎn)不為空诵肛，則遞歸繼續(xù)前序遍歷- 中序遍歷
3.1 如果當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)不為空屹培，則遞歸中序遍歷
3.2 輸出當(dāng)前節(jié)點(diǎn)
3.3 如果當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)不為空，則遞歸中序遍歷后序遍歷
4.1 如果當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)不為空怔檩，則遞歸后序遍歷
4.2 如果當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)不為空褪秀，則遞歸后序遍歷
4.3 輸出當(dāng)前節(jié)點(diǎn)
image.png
5、前珠洗，中溜歪，后序代碼實(shí)現(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é)點(diǎn)
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("前序遍歷，預(yù)計(jì)結(jié)果：1许蓖，2蝴猪，3，5膊爪，4");
binaryTree.perOrder();
System.out.println("中序遍歷自阱，預(yù)計(jì)結(jié)果：2，1米酬，5沛豌，3，4");
binaryTree.infixOrder();
System.out.println("后序遍歷赃额，預(yù)計(jì)結(jié)果：2加派，5，4跳芳，3芍锦，1");
binaryTree.postOrder();
}
}
// 定義二叉樹
class BinaryTree {
private HeroNode root;// 根節(jié)點(diǎn)
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é)點(diǎn)
class HeroNode {
private int no;
private String name;
private HeroNode left; // 左節(jié)點(diǎn)（默認(rèn)為null）
private HeroNode right; // 右節(jié)點(diǎn)（默認(rèn)為null）
public HeroNode(int no, String name) {
this.no = no;
this.name = name;
}
// 節(jié)點(diǎn)的前序遍歷
public void perOrder() {
// 1.先輸出入父節(jié)點(diǎn)
System.out.println(this);
// 2.遞歸左子樹前序遍歷
if (this.left != null) {
this.left.perOrder();
}
// 3.遞歸右子樹前序遍歷
if (this.right != null) {
this.right.perOrder();
}
}
// 節(jié)點(diǎn)的中序遍歷
public void infixOrder() {
// 1.遞歸左子樹中序遍歷
if (this.left != null) {
this.left.infixOrder();
}
// 2.輸出父節(jié)點(diǎn)
System.out.println(this);
// 3.遞歸右子樹中序遍歷
if (this.right != null) {
this.right.infixOrder();
}
}
// 節(jié)點(diǎn)的后序遍歷
public void postOrder() {
// 1.遞歸左子樹后序遍歷
if (this.right != null) {
this.left.postOrder();
}
// 2.遞歸右子樹后序遍歷
if (this.right != null) {
this.right.postOrder();
}
// 3.輸出父節(jié)點(diǎn)
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票腰、先判斷當(dāng)前結(jié)點(diǎn)的 no 是否等于要查找的
2、如果是相等,則返回當(dāng)前結(jié)點(diǎn)
3女气、如果不等杏慰，則判斷當(dāng)前結(jié)點(diǎn)的左子節(jié)點(diǎn)是否為空，如果不為空主卫，則遞歸前序查找4逃默、如果左遞歸前序查找鹃愤，找到結(jié)點(diǎn)簇搅，則返回，否繼續(xù)判斷软吐，當(dāng)前的結(jié)點(diǎn)的右子節(jié)點(diǎn)是否為空瘩将，如果不空，則繼續(xù)向右遞歸前序查找.- 中序查找思路：
1凹耙、判斷當(dāng)前結(jié)點(diǎn)的左子節(jié)點(diǎn)是否為空姿现，如果不為空，則遞歸中序查找
2肖抱、如果找到备典，則返回，如果沒有找到意述，就和當(dāng)前結(jié)點(diǎn)比較提佣，如果是則返回當(dāng)前結(jié)點(diǎn)，否則繼續(xù)進(jìn)行右遞歸的中序查找
3荤崇、如果右遞歸中序查找拌屏，找到就返回，否則返回 null后序查找思路
1术荤、判斷當(dāng)前結(jié)點(diǎn)的左子節(jié)點(diǎn)是否為空倚喂，如果不為空，則遞歸后序查找
2瓣戚、如果找到端圈，就返回，如果沒有找到子库，就判斷當(dāng)前結(jié)點(diǎn)的右子節(jié)點(diǎn)是否為空舱权，如果不為空,則右遞歸進(jìn)行后序查找，如果找到刚照，就返回
3刑巧、最后和當(dāng)前結(jié)點(diǎn)進(jìn)行比較喧兄，是則返回，否則返回 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é)點(diǎn)
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("前序遍歷恭理，預(yù)計(jì)統(tǒng)計(jì)次數(shù)：4 ===> 查找順序 1拯辙，2，3颜价，5涯保，4");
binaryTree.perOrderSearch(5);
System.out.println("中序遍歷，預(yù)計(jì)統(tǒng)計(jì)次數(shù)：3 ===》 查找順序 2周伦，1夕春，5，3专挪，4");
binaryTree.infixOrderSearch(5);
//
System.out.println("后序遍歷及志，預(yù)計(jì)統(tǒng)計(jì)次數(shù)：2 ===》 查找順序 2,5, 4,3,1");
binaryTree.postOrderSearch(5);
}
}
// 定義二叉樹
class BinaryTree {
private HeroNode root;// 根節(jié)點(diǎn)
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é)點(diǎn)
class HeroNode {
private int no;
private String name;
private HeroNode left; // 左節(jié)點(diǎn)（默認(rèn)為null）
private HeroNode right; // 右節(jié)點(diǎn)（默認(rèn)為null）
public HeroNode(int no, String name) {
this.no = no;
this.name = name;
}
/**
* 須知：關(guān)于查找次數(shù)的統(tǒng)計(jì)
* 為了有效的統(tǒng)計(jì)出正確的次數(shù)，應(yīng)該放在 if(this.no == no) 上面
* @param no
* @return
*/
// 節(jié)點(diǎn)的前序遍歷查找
public HeroNode perOrderSearch(int no) {
System.out.println("記錄前序遍歷查找寨腔，打印次數(shù)決定查找運(yùn)行次數(shù)速侈！");
// 比較當(dāng)前節(jié)點(diǎn)是否
if (this.no == no) {
return this;
}
// 1、判斷當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)是否為空迫卢，若不為空倚搬，則左遞歸前序查找
// 2、若左遞歸前序查找乾蛤，找到節(jié)點(diǎn)則返回
HeroNode resNode = null;
if (this.left != null) {
resNode = this.left.perOrderSearch(no);
}
if (resNode != null) {// 說明在左子樹上找到了
return resNode;
}
// 1每界、當(dāng)前節(jié)點(diǎn)的右子樹是否為空，若不為空幻捏，則右遞歸前序查找
// 2盆犁、若右遞歸前序查找，找到節(jié)點(diǎn)則返回
if (this.right != null) {
resNode = this.right.perOrderSearch(no);
}
return resNode;
}
// 節(jié)點(diǎn)的中序遍歷查找
public HeroNode infixOrderSearch(int no) {
// 1篡九、判斷當(dāng)前左節(jié)點(diǎn)是否為空谐岁，若不為空，則繼續(xù)左遞歸中序遍歷查找
HeroNode resNode = null;
if (this.left != null) {
resNode = this.left.infixOrderSearch(no);
}
// 2榛臼、若不為空伊佃，則返回（既找到）
if (resNode != null) {
return resNode;
}
System.out.println("進(jìn)入中序查找的次數(shù)統(tǒng)計(jì)");
// 3、和當(dāng)前節(jié)點(diǎn)進(jìn)行比較沛善，若是則返回
if (this.no == no) {
return this;
}
// 4航揉、若不是，則繼續(xù)右遞歸中序遍歷查找
if (this.right != null) {
resNode = this.right.infixOrderSearch(no);
}
return resNode;
}
// 節(jié)點(diǎn)的后序遍歷查找
public HeroNode postOrderSearch(int no) {
// 1金刁、判斷當(dāng)前左節(jié)點(diǎn)是否為空帅涂，若不為空议薪，則繼續(xù)左遞歸后序遍歷查找
HeroNode resNode =null;
if(this.left!=null) {
resNode = this.left.postOrderSearch(no);
}
// 2、若不為空媳友，則返回
if(resNode !=null) {
return resNode;
}
// 3斯议、若當(dāng)前左子樹沒有找到，則開始右子樹后序遞歸遍歷查找
if(this.right!=null) {
resNode = this.right.postOrderSearch(no);
}
// 4醇锚、若不為空哼御，則返回
if(resNode!=null) {
return resNode;
}
System.out.println("進(jìn)入后序號(hào)查找次數(shù)統(tǒng)計(jì)");
// 5、若左右子樹都沒有找到焊唬，就比較當(dāng)前節(jié)點(diǎn)是否
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é)點(diǎn)思路分析（入門版）
- 規(guī)定
1、若刪除的節(jié)點(diǎn)是葉子節(jié)點(diǎn)赶促，則刪除該節(jié)點(diǎn)
2液肌、若刪除的節(jié)點(diǎn)是非葉子節(jié)點(diǎn)，則刪除該子樹- 思路：
1芳杏、判空矩屁，若只有一個(gè) root 根節(jié)點(diǎn)存在辟宗，則等價(jià)于二叉樹置空
2爵赵、故當(dāng)前入門級(jí)二叉樹是單向的，所以我們是只判斷當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)是否為需要?jiǎng)h除的
3泊脐、若當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)不為空空幻，并且左子節(jié)點(diǎn)就是要?jiǎng)h除的節(jié)點(diǎn)，就將 this.left =null(既刪除)容客，并返回（return 結(jié)束遞歸）
4秕铛、若當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)不為空，并且右子節(jié)點(diǎn)就是要?jiǎng)h除的節(jié)點(diǎn)缩挑，就將 this.rigth=null (既刪除)但两，并返回（return 結(jié)束遞歸）
5、若 以上兩步都沒有刪除節(jié)點(diǎn)供置，那么就進(jìn)行左子樹遞歸刪除
6谨湘、如若以上三步都沒有刪除，則進(jìn)行右子樹遞歸刪除
9芥丧、刪除樹節(jié)點(diǎn)代碼（入門版）
package com.kk.datastructure.tree;
/**
* title: 刪除節(jié)點(diǎn)
* @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é)點(diǎn)
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é)點(diǎn)
public void setRoot(HeroNode root) {
this.root = root;
}
// 刪除節(jié)點(diǎn)
public void delNode(int no) {
if (this.root != null) {
// 1擅耽、判空，若只有一個(gè) root 根節(jié)點(diǎn)存在物遇，則等價(jià)于二叉樹置空
if (root.getNo() == no) {
root = null;
} else {
// 否則 遞歸刪除
root.delNode(no);
}
} else {
System.out.println("當(dāng)前二叉樹為空乖仇，刪個(gè)雞毛憾儒？？");
}
}
}
// 定義節(jié)點(diǎn)
class HeroNode {
private int no;
private String name;
private HeroNode left; // 左節(jié)點(diǎn)（默認(rèn)為null）
private HeroNode right; // 右節(jié)點(diǎn)（默認(rèn)為null）
public HeroNode(int no, String name) {
this.no = no;
this.name = name;
}
// 節(jié)點(diǎn)刪除
// 1乃沙、若刪除的節(jié)點(diǎn)是葉子節(jié)點(diǎn)航夺，則刪除該節(jié)點(diǎn)
// 2、若刪除的節(jié)點(diǎn)是非葉子節(jié)點(diǎn)崔涂，則刪除該子樹
public void delNode(int no) {
// 2阳掐、故當(dāng)前入門級(jí)二叉樹是單向的，所以我們是只判斷當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)是否為需要?jiǎng)h除的
// 3冷蚂、若當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)不為空缭保，并且左子節(jié)點(diǎn)就是要?jiǎng)h除的節(jié)點(diǎn)，就將 this.left =null(既刪除)蝙茶，并返回（return 結(jié)束遞歸）
// 4艺骂、若當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)不為空，并且右子節(jié)點(diǎn)就是要?jiǎng)h除的節(jié)點(diǎn)隆夯，就將 this.rigth=null (既刪除)钳恕，并返回（return 結(jié)束遞歸）
// 5、若 以上兩步都沒有刪除節(jié)點(diǎn)蹄衷，那么就進(jìn)行左子樹遞歸刪除
// 6忧额、如若以上三步都沒有刪除，則進(jìn)行右子樹遞歸刪除
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é)點(diǎn)的前序遍歷
public void perOrder() {
// 1.先輸出入父節(jié)點(diǎn)
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 + "]";
}
}
