day7二叉樹

樹的基本概念

節(jié)點(diǎn)，根節(jié)點(diǎn)肋殴，父節(jié)點(diǎn)囤锉，子節(jié)點(diǎn)，兄弟節(jié)點(diǎn)都是屬于樹的范濤护锤；

一棵樹可以沒有任何節(jié)點(diǎn)官地，稱為空樹弱卡；

一棵樹可以只有1個(gè)節(jié)點(diǎn)倘屹，也就是只有根節(jié)點(diǎn)瑞筐；

樹又可以分為子樹，左子樹传睹，右子樹

節(jié)點(diǎn)的度（degree）：子樹的個(gè)數(shù)

樹的度：所有節(jié)點(diǎn)度中的最大值

葉子節(jié)點(diǎn)（leaf）：度為0的節(jié)點(diǎn)

非葉子節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)

層數(shù)（level）：根節(jié)點(diǎn)在第1層，根節(jié)點(diǎn)的子節(jié)點(diǎn)在第2層遏佣，以此類推

節(jié)點(diǎn)的深度(depth);從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的唯一路徑上的節(jié)點(diǎn)總數(shù)

節(jié)點(diǎn)的高度（height）：從當(dāng)前節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的路徑上的節(jié)點(diǎn)總數(shù)

樹的深度：所有節(jié)點(diǎn)深度中的最大值

樹的高度：所有節(jié)點(diǎn)高度中的最大值

樹的深度等于樹的高度

按照順序來分

有序樹：樹中任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間有順序關(guān)系

無序數(shù)：樹中任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間沒有順序關(guān)系

森林：由m（ $m>= 0$ )棵互不相交的樹組成的集合

二叉樹

二叉樹的表型的表現(xiàn)形勢圖如下所示：

二叉樹

二叉樹的特點(diǎn)

每個(gè)節(jié)點(diǎn)的度最大為2白粉，最小為0

左子樹和右子樹是有順序的

即使某節(jié)點(diǎn)只有一棵子樹，也要區(qū)分左右子樹

二叉樹的性質(zhì)

非空二叉樹的第i層雪情，最多有 $2^{i-1}$ 個(gè)節(jié)點(diǎn)（i >= 1)

節(jié)點(diǎn)樹指示

可以看出最多層最多有個(gè) $2^{i-1}$ 節(jié)點(diǎn)是正確的

在高度為h的二叉樹上最多有 $2^h-1$ 個(gè)結(jié)點(diǎn)（h>=1)

對于任何一棵非空二叉樹遵岩，如果葉子節(jié)點(diǎn)個(gè)數(shù)為n0，度為2的節(jié)點(diǎn)個(gè)數(shù)為n2,則有：n0 = n2 + 1

證明：

1.假設(shè)度為1的節(jié)點(diǎn)個(gè)數(shù)為n1,那么二叉樹的節(jié)點(diǎn)總數(shù)n = n0 + n1 + n2;

2.二叉樹的邊數(shù)T = n1 + 2 * n2 = n - 1 = n0 + n1 + n2 - 1

3.因此n0 = n2 + 1;

真二叉樹(Proper Binary Tree)又稱完滿二叉樹(Full Binary Tree)

真二叉樹：所有節(jié)點(diǎn)的度要么為0旺罢，要么為2

真二叉樹

非真二叉樹

滿二叉樹(Full Binary Tree)又稱（Perfect Binary Tree)完美二叉樹

所有節(jié)點(diǎn)的度要么為0旷余，要么為2，且所有的葉子節(jié)點(diǎn)都在最后一層扁达，如下圖所示：

滿二叉樹

1.假設(shè)滿二叉樹的高度為h（h>=1),第i層的節(jié)點(diǎn)數(shù)量: $2^{i-1}$ ,葉子節(jié)點(diǎn)數(shù)量： $2^{h-1}$ ,總節(jié)點(diǎn)數(shù)量n= $2^0+2^1+2^2+...2^{h-1}$ = $2^h-1$ -------> h = $\log_2 {(n+1)}$

2.在同樣高度的二叉樹中正卧，滿二叉樹的葉子節(jié)點(diǎn)數(shù)量最多，總結(jié)點(diǎn)數(shù)量最多

3.滿二叉樹一定是真二叉樹跪解，真二叉樹不一定是滿二叉樹

完全二叉樹(Complete Binary Tree)

葉子節(jié)點(diǎn)只會(huì)出現(xiàn)在最后2層炉旷，且最后1層的葉子節(jié)點(diǎn)都靠左對齊

完全二叉樹

非完全二叉樹

滿二叉樹

完全二叉樹從根節(jié)點(diǎn)至倒數(shù)第2層是一棵滿二叉樹，滿二叉樹一定是完全二叉樹叉讥，完全二叉樹不一定是滿二叉樹

如何判斷是否為完全二叉樹

判斷條件：如果樹為空窘行，返回false，如果樹不為空图仓，開始層序遍歷二叉樹（用隊(duì)列方式處理）

如果node.left != null && node.right != null,將node.left,node.right 按順序入隊(duì)罐盔；如果node.left == null && node.right != null ,返回false;如果node.left != null && node.right == null 或者 node.left == null && node.right == null ,那么后面遍歷的節(jié)點(diǎn)應(yīng)該都是葉子節(jié)點(diǎn)，否則返回false救崔，遍歷結(jié)束惶看，返回true，代碼圖如下：

方法1

方法2

方法2相對方法1六孵，減少重復(fù)代碼的判斷條件纬黎；

完全二叉樹的性質(zhì)

一棵有n個(gè)節(jié)點(diǎn)的完全二叉樹(n>0),從上到下，從左到右對節(jié)點(diǎn)從0開始進(jìn)行編號(hào)劫窒，對任意第i個(gè)節(jié)點(diǎn)本今，如果i = 0,它是根節(jié)點(diǎn)；如果i > 0,它的父節(jié)點(diǎn)編號(hào)為floor((i-1)/2);如果2i + 1 $\leq$ n - 1,它的左子節(jié)點(diǎn)編號(hào)為2i + 1;如果2i + 1 > n - 1,它無左子節(jié)點(diǎn)主巍；如果2i+2 $\leq$ n -1,它的右子節(jié)點(diǎn)編號(hào)為2i + 2冠息；如果2i + 2 > n - 1,它無右子節(jié)點(diǎn)；

測試題目

如果一棵完全二叉樹有768個(gè)節(jié)點(diǎn)煤禽，求葉子節(jié)點(diǎn)的個(gè)數(shù)铐达？

假設(shè)葉子節(jié)點(diǎn)個(gè)數(shù)為n0,度為1的節(jié)點(diǎn)個(gè)數(shù)為n1,度為2的節(jié)點(diǎn)個(gè)數(shù)為n2，那么總結(jié)點(diǎn)個(gè)數(shù)n = n0 + n1 + n2,另外二叉樹的性質(zhì)有一個(gè)定論n0 = n2 + 1;那么可以推導(dǎo)出n = 2n0 + n1 -1;另外完全二叉樹的n1(子節(jié)點(diǎn)的個(gè)數(shù)）要么為0要么為1檬果，所以這里分為兩種情況：

1.n1為1的時(shí)候瓮孙，n=2n0,n必然是偶數(shù)唐断，那么葉子節(jié)點(diǎn)的個(gè)數(shù)n0 = n /2,非葉子節(jié)點(diǎn)個(gè)數(shù)n1+n2 = n/2

2.n1為0時(shí)，n = 2n0 -1,n必然是奇數(shù)杭抠，葉子節(jié)點(diǎn)個(gè)數(shù)n0=(n+1)/2,非葉子節(jié)點(diǎn)個(gè)數(shù)n1+n2=(n-1)/2

那么葉子節(jié)點(diǎn)個(gè)數(shù)n0 = floor((n+1)/2) = ceiling(n/2),非葉子節(jié)點(diǎn)個(gè)數(shù)n1 + n2 = floor(n/2) = ceiling((n-1)/2)

因此葉子節(jié)點(diǎn)個(gè)數(shù)為384

二叉樹的遍歷

遍歷是數(shù)據(jù)結(jié)構(gòu)中的常見操作脸甘，遍歷有兩種：1.正序遍歷；2.逆序遍歷

根據(jù)節(jié)點(diǎn)訪問順序的不同偏灿，二叉樹常見的遍歷方式有4種

1.前序遍歷（Preorder Traversal)

2.中序遍歷（Inorder Traversal）

3.后續(xù)遍歷（Postorder Traversal）

4.層序遍歷（Level Order Traversal）

前序遍歷（Preorder Traversal）

下面的幾種遍歷順序方法都以下面的圖為準(zhǔn)

訪問順序：根節(jié)點(diǎn)->前序遍歷左子樹->前序遍歷右子樹

7->4->2-1->3->5->9->8->11->10->12

中序遍歷（Inorder Traversal）

訪問順序：左子樹->根節(jié)點(diǎn)->右子樹

1->2>3->4->5->7->8->9->10->11->12

可以看到二叉搜索樹的中序遍歷結(jié)果是升序的

后續(xù)遍歷

訪問順序：左子樹->右子樹->根節(jié)點(diǎn)

1->3->2->5->4->8->10->12->11->9->7

層序遍歷(Level Order Traversal)

訪問順序：從上到下丹诀，從左到右依次訪問每一個(gè)節(jié)點(diǎn)

7->4->9->2->5->8->11->1->3->10->12

層序的遍歷之路：使用隊(duì)列

1.將根節(jié)點(diǎn)入隊(duì)；2.循環(huán)執(zhí)行以下操作翁垂，直到隊(duì)列為空铆遭；3.將隊(duì)頭節(jié)點(diǎn)A出隊(duì)，進(jìn)行訪問沿猜；4.將A的左子節(jié)點(diǎn)入隊(duì)枚荣；5.將A的右子節(jié)點(diǎn)入隊(duì)

遍歷的作用

前序遍歷：可以用于一些樹狀結(jié)構(gòu)展示

中序遍歷：二叉搜索樹的中序遍歷按升序或者降序處理節(jié)點(diǎn)

后續(xù)遍歷：適用于一些先子后父的操作

層序遍歷：計(jì)算二叉樹的高度，判斷一棵樹是否為完全二叉樹

前驅(qū)節(jié)點(diǎn)(predecessor)

前驅(qū)節(jié)點(diǎn)：中序遍歷時(shí)的前一個(gè)節(jié)點(diǎn)啼肩，如果是二叉搜索樹橄妆，前驅(qū)節(jié)點(diǎn)就是前一個(gè)比它小的節(jié)點(diǎn)

以圖表說明一下：

demo圖

前驅(qū)節(jié)點(diǎn)的尋找分幾種情況的：

node.left != null

例如6,13,8;這種節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)通常都是在node.left.right.right......,終止條件為right 等于 null，因?yàn)楦鶕?jù)前面所說的祈坠，二叉搜索樹害碾，前驅(qū)節(jié)點(diǎn)就是前一個(gè)比它小的節(jié)點(diǎn)，如果left不等于null的情況下赦拘，那要符合這個(gè)條件慌随，必須是節(jié)點(diǎn)在right.....一直到null結(jié)束尋找

6的前驅(qū)節(jié)點(diǎn)是5，因?yàn)?的做節(jié)點(diǎn)是5躺同，5節(jié)點(diǎn)的right等于null儒陨，所以5就是前面一個(gè)比它小的節(jié)點(diǎn)；13的前驅(qū)節(jié)點(diǎn)是12笋籽，因?yàn)?3的做節(jié)點(diǎn)是10，然后最終的有節(jié)點(diǎn)是12椭员，12的right等于nul车海，所以12是最后一個(gè)右節(jié)點(diǎn)；8的前驅(qū)節(jié)點(diǎn)是7隘击，因?yàn)?是8左節(jié)點(diǎn)之后的最后一個(gè)右節(jié)點(diǎn)侍芝；

node.left == null && node.parent != null

例如：7，11埋同，9州叠，1；類似這種節(jié)點(diǎn)node.left == null && node.parent != null的情況凶赁，前驅(qū)節(jié)點(diǎn)predecessor 是存放在node.parent.parent.....,最終的終止條件是node在parent的right右子樹中咧栗，可以看到這種情況返回的前驅(qū)節(jié)點(diǎn)最終是node.parent....逆甜；

7的前驅(qū)節(jié)點(diǎn)是6，因?yàn)?的parent節(jié)點(diǎn)是6致板，7又是parent6的right節(jié)點(diǎn)交煞，符合條件；11的前驅(qū)節(jié)點(diǎn)是10,首先11的parent節(jié)點(diǎn)是12斟或，但是11不滿足是node.parent的right素征，而是left，所以繼續(xù)往上尋找萝挤，node=node.parent,這個(gè)時(shí)候node是12御毅，那么12的parent節(jié)點(diǎn)是10，然后12又是parent10的right怜珍，所以返回node.parent,也就是10端蛆；9的前驅(qū)節(jié)點(diǎn)是8，分析和11的前驅(qū)節(jié)點(diǎn)以一樣道理绘面；1的前驅(qū)節(jié)點(diǎn)是null欺税，也就是沒有前驅(qū)節(jié)點(diǎn)，因?yàn)橐宦飞先ふ业倪^程之后揭璃，發(fā)現(xiàn)并沒有找到符合的條件

node.left == null && node.parent != null

符合這種情況的只有晚凿，沒有左子樹的跟節(jié)點(diǎn)

代碼圖大概如下：

前驅(qū)節(jié)點(diǎn)

后繼節(jié)點(diǎn)（successor）

后繼節(jié)點(diǎn)，中序遍歷時(shí)的后一個(gè)節(jié)點(diǎn)瘦馍，如果是二叉搜索樹歼秽，后繼節(jié)點(diǎn)就是后一個(gè)比它大的節(jié)點(diǎn)

以下圖為例：

demo圖

后繼節(jié)點(diǎn)也要分幾種情況：

node.right != null

例如1，8情组，4燥筷；這種節(jié)點(diǎn)的遍歷條件是successor = node.right.left.left.left...，因?yàn)楹罄^節(jié)點(diǎn)是后一個(gè)比它大的節(jié)點(diǎn)院崇，對于搜索二叉樹來說肆氓，所以首先要獲取right的，然后再不斷的獲取left底瓣，獲取到后一個(gè)比它大的節(jié)點(diǎn)谢揪，終止條件是left 為null；所以1的后繼節(jié)點(diǎn)是2捐凭，因?yàn)?節(jié)點(diǎn)沒有l(wèi)eft節(jié)點(diǎn)拨扶；8的后繼節(jié)點(diǎn)是9，因?yàn)?的right是10茁肠，10的left最后是9患民，9沒有了left，所以9是最終的結(jié)束條件垦梆；4的后繼節(jié)點(diǎn)是5匹颤，原理和8的分析一樣

node.right == null && node.parent != null

例如：7仅孩，6，3惋嚎，11杠氢；遍歷條件是successor = node.parent.parent.parent...,終止條件是node在parent的左子樹當(dāng)中；因?yàn)橹挥性谧笞訕洚?dāng)中另伍，才能保證返回的node.parent 大于當(dāng)前例子節(jié)點(diǎn)鼻百；所以7的后繼節(jié)點(diǎn)是8，6的后繼節(jié)點(diǎn)是7摆尝，3的后繼節(jié)點(diǎn)4温艇，11的后繼節(jié)點(diǎn)是null

node.right == null && node.parent == null

滿足這種條件的就只有沒有右子樹的根節(jié)點(diǎn)

代碼圖如下

后繼節(jié)點(diǎn)

二叉搜索樹設(shè)計(jì)

private int size;//元素?cái)?shù)量

private Node<E> root;//根節(jié)點(diǎn)

private Comparator<E>comparator;//比較器，根據(jù)不同的判斷做不同的選擇展示

public int size(); //返回樹的元素個(gè)數(shù)

public boolean isEmpty;//查看樹是否為空

public boolean clear();//清空樹

public void add(E element);//添加元素

public void remove(E element);//移除元素

public boolean contains(E element);//是否包含元素

private Node<E>node(E element);//獲取節(jié)點(diǎn)元素

在這里呢堕汞，只會(huì)介紹添加方法和刪除方法勺爱；首先先看一下添加方法的步驟：

添加方法public void add(E element)

1.找到父節(jié)點(diǎn)；2.創(chuàng)建新節(jié)點(diǎn)讯检；3.parent.left = node 或者parent.right = node;

4.如果值相等的元素的琐鲁，覆蓋舊元素

add

思路看上去還是比較簡單易懂的，就是先判斷是否是root元素人灼，如果是root元素围段，直接賦值root元素，否則的話投放，就將傳進(jìn)來的element元素從root節(jié)點(diǎn)開始一個(gè)一個(gè)比較奈泪，找到符合項(xiàng)，然后插入元素灸芳，根據(jù)是左節(jié)點(diǎn)還是右節(jié)點(diǎn)插入相關(guān)位置

public void remove(Node node)

刪除相對來說就會(huì)復(fù)雜點(diǎn)：因?yàn)橐袛喽鄠€(gè)節(jié)點(diǎn)的情況：

1.兩個(gè)節(jié)點(diǎn)的刪除涝桅；1個(gè)節(jié)點(diǎn)的刪除；葉子節(jié)點(diǎn)的刪除

刪除的操作以下面的圖為例子說明一下：

刪除度為2的節(jié)點(diǎn)

以下面的圖為例烙样，假設(shè)現(xiàn)在我要?jiǎng)h除一個(gè)節(jié)點(diǎn)度為2的節(jié)點(diǎn)冯遂，假設(shè)是5，那么根據(jù)前面所說的

5谒获，3债蜜，8，1究反，4，6儒洛，9精耐，2，7

我們應(yīng)該找到前驅(qū)后者后繼節(jié)點(diǎn)的值覆蓋原來節(jié)點(diǎn)的值琅锻，然后刪除相應(yīng)的前驅(qū)或者后繼節(jié)點(diǎn)卦停，那么刪除5節(jié)點(diǎn)之后向胡，應(yīng)該變成如下圖所示：

5，3惊完，8僵芹，1，4小槐，6拇派，9，2凿跳，7

代碼步驟分析圖如下：

刪除度為2的節(jié)點(diǎn)步驟1

如果是度為2的節(jié)點(diǎn)件豌，上面這一步就是在獲取后繼節(jié)點(diǎn)，然后將后繼節(jié)點(diǎn)的值賦值給本來的node節(jié)點(diǎn)控嗜；也就是將后繼節(jié)點(diǎn)6的值賦值給5茧彤，然后再用之前指向5的node節(jié)點(diǎn)指向6節(jié)點(diǎn)stepNode，方便之后的操作疆栏，如果不是度為2的節(jié)點(diǎn)曾掂，直接執(zhí)行下面的操作就可以了，接下來看看node度為1和0的情況壁顶，

刪除度為1或者0的步驟2

如果刪除的節(jié)點(diǎn)是度為2的節(jié)點(diǎn)珠洗，就會(huì)多出上面一步操作刪除度為2的步驟1，否則就直接進(jìn)入到刪除度為1或者0的步驟2博助。這里就直接針對度為2的來往下說险污，這個(gè)時(shí)候的node指向的是原來值為6的節(jié)點(diǎn)，那么這個(gè)節(jié)點(diǎn)的度就是為1富岳，因?yàn)橛夜?jié)點(diǎn)為7蛔糯，那么這個(gè)時(shí)候就要將replacementNode的parent指向6的parent，因?yàn)閚ode是在parent的左邊（也就是6在8的左邊窖式，所以將8的left指向7）蚁飒，也就是如下圖：

刪除節(jié)點(diǎn)的子節(jié)點(diǎn)圖更改

于是通過這些步驟就得到來上面的刪除度為2的節(jié)點(diǎn)圖；

刪除度為1的節(jié)點(diǎn)

遵循的原則應(yīng)該是：用子節(jié)點(diǎn)替代原來節(jié)點(diǎn)的位置萝喘，child 是 node.left 或者child是node.right淮逻，如果用child替代node的位置，如果node是左子節(jié)點(diǎn)：child.parent = node.parent,node.parent.left = child;如果node是右子節(jié)點(diǎn)阁簸，child.parent = node.parent,node.parent.right = child

如果node是根節(jié)點(diǎn)：那么直接root = null爬早，就可以了，也就是會(huì)進(jìn)入if 判斷中的這個(gè)node.parentNode == null启妹；

非根節(jié)點(diǎn)：

demo圖

假設(shè)現(xiàn)在刪除4筛严，根據(jù)前面說刪除度為1的原則，首先拿到5節(jié)點(diǎn)作為child饶米，也就是代碼中的replaceNode桨啃，先將5節(jié)點(diǎn)的parent指向原來parent4的parent節(jié)點(diǎn)车胡，也就是現(xiàn)在5節(jié)點(diǎn)的parent指向3節(jié)點(diǎn)，然后因?yàn)?節(jié)點(diǎn)是3節(jié)點(diǎn)的right照瘾，所以將3節(jié)點(diǎn)的right重新指向?yàn)閏hild節(jié)點(diǎn)也就是5匈棘，所以得到圖下：

刪除度為1的圖

刪除葉子節(jié)點(diǎn)（也就是度為0的節(jié)點(diǎn)）

這種節(jié)點(diǎn)，如果是根節(jié)點(diǎn)的話析命，就直接node.parent = null,root = null即可主卫，非根節(jié)點(diǎn)的話，就要判斷是左或右子節(jié)點(diǎn)碳却，如果node == node.parent.left --> node.parent.left = null ,如果node == node.parent.right--->node.parent.right = null

平衡二叉搜索樹

為什么會(huì)有平衡二叉搜索樹的概念出現(xiàn)呢队秩？我們先來看看一個(gè)這樣的情景：

如果是按照7，4昼浦，9馍资，2，5关噪，8鸟蟹，11的順序添加節(jié)點(diǎn)：

7，4使兔，9建钥，2，5虐沥，8熊经，11(圖1)

另外一個(gè)是從小到大添加節(jié)點(diǎn)：

從小到大(圖2)

圖一的復(fù)雜度是O(h) = O(logn),圖二的復(fù)雜度是O(h) = O(n)

那么當(dāng)n比較大的時(shí)候，兩者的性能差異就會(huì)比較大欲险，刪除的過程之后也可能會(huì)導(dǎo)致圖2的情況镐依，這樣就相當(dāng)于二叉搜索樹會(huì)退化成鏈表，這個(gè)會(huì)影響性能天试，因此我們需要平衡二叉樹出現(xiàn)槐壳，首先因?yàn)楣?jié)點(diǎn)的添加，刪除順序是無法限制的喜每，因此我們可以在節(jié)點(diǎn)的添加务唐，刪除操作之后，想辦法讓二叉搜索樹恢復(fù)平衡带兜，也就是減少樹的高度枫笛，但是調(diào)整的次數(shù)多的時(shí)候，反而會(huì)增加了時(shí)間復(fù)雜度刚照，因此總的來說刑巧，我們要用盡量少的調(diào)整次數(shù)達(dá)到適度平衡。好啦，這個(gè)就是我目前學(xué)到的相關(guān)樹的知識(shí)了海诲，之后會(huì)學(xué)習(xí)AVL樹，B樹還有紅黑樹檩互。

最后編輯于：2021.07.14 17:11:38

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末特幔，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子闸昨，更是在濱河造成了極大的恐慌蚯斯，老刑警劉巖，帶你破解...
沈念sama閱讀 216,544評論 6贊 501
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件饵较，死亡現(xiàn)場離奇詭異拍嵌，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)循诉，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,430評論 3贊 392
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門横辆，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人茄猫，你說我怎么就攤上這事狈蚤。” “怎么了划纽？”我有些...
開封第一講書人閱讀 162,764評論 0贊 353
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵脆侮，是天一觀的道長。經(jīng)常有香客問我勇劣，道長靖避，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 58,193評論 1贊 292
?港島之戀（遺憾婚禮）
正文為了忘掉前任比默，我火速辦了婚禮幻捏，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘退敦。我一直安慰自己粘咖，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 67,216評論 6贊 388
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布侈百。她就那樣靜靜地躺著瓮下，像睡著了一般。火紅的嫁衣襯著肌膚如雪钝域。梳的紋絲不亂的頭發(fā)上讽坏，一...
開封第一講書人閱讀 51,182評論 1贊 299
城市分裂傳說
那天，我揣著相機(jī)與錄音例证，去河邊找鬼路呜。笑死，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的胀葱。我是一名探鬼主播漠秋，決...
沈念sama閱讀 40,063評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼抵屿！你這毒婦竟也來了庆锦？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 38,917評論 0贊 274
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤轧葛，失蹤者是張志新（化名）和其女友劉穎搂抒，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體尿扯，經(jīng)...
沈念sama閱讀 45,329評論 1贊 310
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡求晶，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,543評論 2贊 332
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了衷笋。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片芳杏。...
茶點(diǎn)故事閱讀 39,722評論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖右莱，靈堂內(nèi)的尸體忽然破棺而出蚜锨，到底是詐尸還是另有隱情，我是刑警寧澤慢蜓，帶...
沈念sama閱讀 35,425評論 5贊 343
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布亚再，位于F島的核電站，受9級(jí)特大地震影響晨抡，放射性物質(zhì)發(fā)生泄漏氛悬。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,019評論 3贊 326
男人毒藥：我在死后第九天來索命
文/蒙蒙一耘柱、第九天我趴在偏房一處隱蔽的房頂上張望如捅。院中可真熱鬧，春花似錦调煎、人聲如沸镜遣。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,671評論 0贊 22
一樁弒父案士袄，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽悲关。三九已至，卻和暖如春娄柳，著一層夾襖步出監(jiān)牢的瞬間寓辱，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 32,825評論 1贊 269
情欲美人皮
我被黑心中介騙來泰國打工赤拒，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留秫筏，地道東北人诱鞠。一個(gè)月前我還...
沈念sama閱讀 47,729評論 2贊 368
代替公主和親
正文我出身青樓，卻偏偏與公主長得像这敬，于是被迫代替她去往敵國和親航夺。傳聞我的和親對象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,614評論 2贊 353

day7二叉樹

樹的基本概念

按照順序來分

二叉樹

真二叉樹(Proper Binary Tree)又稱完滿二叉樹(Full Binary Tree)

滿二叉樹(Full Binary Tree)又稱（Perfect Binary Tree)完美二叉樹

完全二叉樹(Complete Binary Tree)

如何判斷是否為完全二叉樹

完全二叉樹的性質(zhì)

測試題目

二叉樹的遍歷

前序遍歷（Preorder Traversal）

中序遍歷（Inorder Traversal）

后續(xù)遍歷

層序遍歷(Level Order Traversal)

遍歷的作用

前驅(qū)節(jié)點(diǎn)(predecessor)

后繼節(jié)點(diǎn)（successor）

二叉搜索樹設(shè)計(jì)

刪除度為2的節(jié)點(diǎn)

刪除度為1的節(jié)點(diǎn)

刪除葉子節(jié)點(diǎn)（也就是度為0的節(jié)點(diǎn)）

平衡二叉搜索樹

推薦閱讀更多精彩內(nèi)容