一导犹、為什么需要樹(shù)這種數(shù)據(jù)結(jié)構(gòu)
數(shù)組存儲(chǔ)方式的分析
- 優(yōu)點(diǎn)：通過(guò)下標(biāo)方式訪問(wèn)元素塞椎，速度快桨仿。對(duì)于有序數(shù)組，還可使用二分查找提高檢索速度案狠。
- 缺點(diǎn)：如果要檢索具體某個(gè)值服傍，或者插入值(按一定順序)會(huì)整體移動(dòng)，效率較低骂铁。
鏈?zhǔn)酱鎯?chǔ)方式的分析
- 優(yōu)點(diǎn)：在一定程度上對(duì)數(shù)組存儲(chǔ)方式有優(yōu)化(比如：插入一個(gè)數(shù)值節(jié)點(diǎn)吹零，只需要將插入節(jié)點(diǎn)，鏈接到鏈表中即可拉庵， 刪除效率也很好)灿椅。
- 缺點(diǎn)：在進(jìn)行檢索時(shí)，效率仍然較低钞支，比如(檢索某個(gè)值阱扬，需要從頭節(jié)點(diǎn)開(kāi)始遍歷)
樹(shù)存儲(chǔ)方式的分析
- 能提高數(shù)據(jù)存儲(chǔ)，讀取的效率, 比如利用 二叉排序樹(shù)(Binary Sort Tree)伸辟，既可以保證數(shù)據(jù)的檢索速度麻惶，同時(shí)也可以保證數(shù)據(jù)的插入，刪除信夫，修改的速度窃蹋。為了更好的了解樹(shù)的用法卡啰，我們先來(lái)看看二叉樹(shù)是怎么工作的。
1警没、二叉樹(shù)的基本概念
- 二叉樹(shù)是n個(gè)有限元素的集合匈辱，當(dāng)集合不為空時(shí)，二叉樹(shù)由一個(gè)稱為根（root）的元素及兩個(gè)不相交的杀迹、被分別稱為左子樹(shù)和右子樹(shù)的樹(shù)組成亡脸，他的左子樹(shù)和右子樹(shù)同樣為一個(gè)二叉樹(shù)；當(dāng)集合為空時(shí)树酪，稱該二叉樹(shù)為空二叉樹(shù)妆丘。在二叉樹(shù)中碍彭，一個(gè)元素也稱作一個(gè)節(jié)點(diǎn)。
一顆二叉樹(shù)
- 也就是說(shuō)二叉樹(shù)（binary tree）的每個(gè)節(jié)點(diǎn)不能多于有兩個(gè)兒子，上面的圖就是一顆二叉樹(shù)苇经。它是一種最簡(jiǎn)單且最重要的樹(shù)假哎。二叉樹(shù)的遞歸定義為：二叉樹(shù)是一棵空樹(shù)吝梅，或者是一棵由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的员咽，分別稱作根的左子樹(shù)和右子樹(shù)組成的非空樹(shù)；左子樹(shù)和右子樹(shù)又同樣都是二叉樹(shù)
- 一棵非空樹(shù)至少會(huì)有一個(gè)節(jié)點(diǎn)(根節(jié)點(diǎn))
- 樹(shù)由節(jié)點(diǎn)組成力试，每個(gè)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)是這樣的：
-
因此徙邻，我們定義樹(shù)的時(shí)候往往是->定義節(jié)點(diǎn)->節(jié)點(diǎn)連接起來(lái)就成了樹(shù)，而節(jié)點(diǎn)的定義就是：一個(gè)數(shù)據(jù)畸裳、兩個(gè)指針(如果有節(jié)點(diǎn)就指向節(jié)點(diǎn)鹃栽、沒(méi)有節(jié)點(diǎn)就指向null)
二叉樹(shù)節(jié)點(diǎn)的代碼實(shí)現(xiàn)：public class TreeNode{ int val; //二叉樹(shù)存放數(shù)據(jù)的區(qū)域 TreeNode leftNode; //二叉樹(shù)的左節(jié)點(diǎn)指針 TreeNode rightNode; //二叉樹(shù)的右節(jié)點(diǎn)指針 }
1.滿二叉樹(shù)
- 如果該二叉樹(shù)的所有葉子節(jié)點(diǎn)都在最后一層，并且結(jié)點(diǎn)總數(shù)= 2^n -1 , n 為層數(shù)躯畴，則我們稱為滿二叉樹(shù)民鼓。
滿二叉樹(shù)
2.完全二叉樹(shù)
- 如果該二叉樹(shù)的所有葉子節(jié)點(diǎn)都在最后一層或者倒數(shù)第二層，而且最后一層的葉子節(jié)點(diǎn)在左邊連續(xù)蓬抄，倒數(shù)第二層的葉子節(jié)點(diǎn)在右邊連續(xù)丰嘉，我們稱為完全二叉樹(shù)。通俗一點(diǎn)來(lái)講就是把樹(shù)的節(jié)點(diǎn)按順序從上到下嚷缭、從左往右排形成的二叉樹(shù)
完全二叉樹(shù)
3饮亏、順序存儲(chǔ)二叉樹(shù)
- 從數(shù)據(jù)存儲(chǔ)來(lái)看，數(shù)組存儲(chǔ)方式和樹(shù)的存儲(chǔ)方式可以相互轉(zhuǎn)換阅爽，即數(shù)組可以轉(zhuǎn)換成樹(shù)路幸，樹(shù)也可以轉(zhuǎn)換成數(shù)組:
- 順序存儲(chǔ)二叉樹(shù)的特點(diǎn)（n表示二叉樹(shù)中的第幾個(gè)元素(按0開(kāi)始編號(hào)):
- 順序二叉樹(shù)通常只考慮完全二叉樹(shù)
- 第n個(gè)元素的左子節(jié)點(diǎn)為 2 * n + 1
- 第n個(gè)元素的右子節(jié)點(diǎn)為 2 * n + 2
- 第n個(gè)元素的父節(jié)點(diǎn)為 (n-1) / 2
順序存儲(chǔ)二叉樹(shù)在后面的堆排序中也會(huì)運(yùn)用到，所以還是挺重要的
二付翁、創(chuàng)建一顆簡(jiǎn)單的二叉樹(shù)
class BinaryTreeNode{
private int id; //節(jié)點(diǎn)序號(hào)
private BinaryTreeNode left; //左節(jié)點(diǎn)
private BinaryTreeNode right; //右節(jié)點(diǎn)
//構(gòu)造方法
public BinaryTreeNode(int id){this.id = id;}
}
為了在其他類中訪問(wèn)到這些字段简肴，我們還需要get和set方法
然后我們?cè)诜椒ɡ锩鎰?chuàng)建一顆這樣子的樹(shù)：
public static void main(String[] args) {
BinaryTreeNode t1 = new BinaryTreeNode(1);
BinaryTreeNode t2 = new BinaryTreeNode(2);
BinaryTreeNode t3 = new BinaryTreeNode(3);
BinaryTreeNode t4 = new BinaryTreeNode(4);
BinaryTreeNode t5 = new BinaryTreeNode(5);
BinaryTreeNode t6 = new BinaryTreeNode(6);
BinaryTreeNode t7 = new BinaryTreeNode(7); //先new出7個(gè)節(jié)點(diǎn)
//然后在把他們連接起來(lái)
t1.setLeft(t2);
t1.setRight(t3); //表示父節(jié)點(diǎn)1的左右節(jié)點(diǎn)
t2.setLeft(t4);
t2.setRight(t5); //表示2的左右節(jié)點(diǎn)
t3.setLeft(t6);
t3.setRight(t7); //表示3的左右節(jié)點(diǎn)
//因?yàn)?、5百侧、6砰识、7都是葉子節(jié)點(diǎn)能扒，葉子節(jié)點(diǎn)的左右節(jié)點(diǎn)都為null，所以不需要set
}
遍歷一顆二叉樹(shù)
遍歷二叉樹(shù)有三種方式：
1.前序遍歷： 先輸出父節(jié)點(diǎn)辫狼，再遍歷左子樹(shù)和右子樹(shù)
2.中序遍歷：先遍歷左子樹(shù)初斑，再輸出父節(jié)點(diǎn)，再遍歷右子樹(shù)
3.后序遍歷：先遍歷左子樹(shù)膨处，再遍歷右子樹(shù)见秤，最后輸出父節(jié)點(diǎn)
要看是什么遍歷，只需要看父節(jié)點(diǎn)的輸出位置就行了真椿，用這顆樹(shù)為例子：
-
如果是前序遍歷：1 ->2 ->4 ->5 ->3 ->6 ->7
代碼如下（方法寫在BinaryTreeNode類中）：//前序遍歷 public void pre() { //輸出父節(jié)點(diǎn) System.out.println(this.id); //往左遍歷 if(this.left != null) { this.left.pre(); } //往右遍歷 if(this.right != null) { this.right.pre(); } }
在main方法中使用t1.pre();遍歷結(jié)果如下：
-
如果是中序遍歷：4 ->2 ->5 ->1 ->6 ->3 ->7
代碼如下：//中序遍歷 public void mid() { //往左遍歷 if(this.left != null) { this.left.mid(); } //輸出父節(jié)點(diǎn) System.out.println(this.id); //往右遍歷 if(this.right != null) { this.right.mid(); } }
在main方法中使用t1.mid();遍歷結(jié)果如下：
-
如果是后序遍歷：4 ->5 ->2 ->6 ->7 ->3 ->1
代碼如下：//后序遍歷 public void next() { //往左遍歷 if(this.left != null) { this.left.next(); } //往右遍歷 if(this.right != null) { this.right.next(); } //輸出父節(jié)點(diǎn) System.out.println(this.id); }
在main方法中使用t1.next();遍歷結(jié)果如下：
查找二叉樹(shù)中的值
二叉樹(shù)的查找也分為前鹃答、中、后序瀑粥，因?yàn)榇篌w思想和遍歷差不多挣跋，我這里也只上前序查找的代碼了：
//前序查找
public BinaryTreeNode preFind(int id) {
BinaryTreeNode res = null;
if(this.id == id) {
return this;
}
if(this.left != null) {
res = this.left.preFind(id);
}
if(res != null) {
return res;
}
if(this.right != null) {
res = this.right.preFind(id);
}
return res;
}
