一礁遵、什么是二叉樹廊移？

二叉樹是n(n>=0)個(gè)結(jié)點(diǎn)的有限集合盔憨，該集合或者為空集（稱為空二叉樹）羽莺，或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱為根結(jié)點(diǎn)的左子樹和右子樹組成葛菇。
下圖展示了一棵普通二叉樹：

image

二油额、二叉樹遍歷

1 定義

二叉樹的遍歷是指從二叉樹的根結(jié)點(diǎn)出發(fā)泞坦，按照某種次序依次訪問二叉樹中的所有結(jié)點(diǎn)斑鸦，使得每個(gè)結(jié)點(diǎn)被訪問一次愕贡，且僅被訪問一次。
二叉樹的訪問次序可以分為三種：
前序遍歷
中序遍歷
后序遍歷

2 前序遍歷（根左右）

前序遍歷通俗的說就是從二叉樹的根結(jié)點(diǎn)出發(fā)巷屿，當(dāng)?shù)谝淮蔚竭_(dá)結(jié)點(diǎn)時(shí)就輸出結(jié)點(diǎn)數(shù)據(jù)固以，按照先向左在向右的方向訪問。

image

圖3.13所示二叉樹訪問如下：

從根結(jié)點(diǎn)出發(fā)攒庵，則第一次到達(dá)結(jié)點(diǎn)A嘴纺，故輸出A;
繼續(xù)向左訪問，第一次訪問結(jié)點(diǎn)B浓冒，故輸出B栽渴；
按照同樣規(guī)則，輸出D稳懒，輸出H闲擦；
當(dāng)?shù)竭_(dá)葉子結(jié)點(diǎn)H，返回到D场梆，此時(shí)已經(jīng)是第二次到達(dá)D墅冷，故不在輸出D，進(jìn)而向D右子樹訪問或油，D右子樹不為空寞忿，則訪問至I，第一次到達(dá)I顶岸，則輸出I腔彰；
I為葉子結(jié)點(diǎn)，則返回到D辖佣，D左右子樹已經(jīng)訪問完畢霹抛，則返回到B，進(jìn)而到B右子樹卷谈，第一次到達(dá)E杯拐，故輸出E；
向E左子樹世蔗，故輸出J端逼；
按照同樣的訪問規(guī)則，繼續(xù)輸出C凸郑、F裳食、G；

則3.13所示二叉樹的前序遍歷輸出為：
ABDHIEJCFG

3 中序遍歷(左根右)

中序遍歷就是從二叉樹的根結(jié)點(diǎn)出發(fā)芙沥，當(dāng)?shù)诙蔚竭_(dá)結(jié)點(diǎn)時(shí)就輸出結(jié)點(diǎn)數(shù)據(jù)诲祸，按照先向左在向右的方向訪問。

image

圖3.13所示二叉樹中序訪問如下：

從根結(jié)點(diǎn)出發(fā)而昨，則第一次到達(dá)結(jié)點(diǎn)A救氯，不輸出A，繼續(xù)向左訪問歌憨，第一次訪問結(jié)點(diǎn)B着憨，不輸出B；繼續(xù)到達(dá)D务嫡，H甲抖；
到達(dá)H漆改，H左子樹為空，則返回到H准谚，此時(shí)第二次訪問H挫剑，故輸出H；
H右子樹為空柱衔，則返回至D樊破，此時(shí)第二次到達(dá)D，故輸出D唆铐；
由D返回至B哲戚，第二次到達(dá)B，故輸出B艾岂；
按照同樣規(guī)則繼續(xù)訪問顺少，輸出J、E澳盐、A祈纯、F、C叼耙、G腕窥；

則3.13所示二叉樹的中序遍歷輸出為：
HDIBJEAFCG

4 后序遍歷(左右根)

后序遍歷就是從二叉樹的根結(jié)點(diǎn)出發(fā)，當(dāng)?shù)谌蔚竭_(dá)結(jié)點(diǎn)時(shí)就輸出結(jié)點(diǎn)數(shù)據(jù)筛婉，按照先向左在向右的方向訪問簇爆。

image

圖3.13所示二叉樹后序訪問如下：

從根結(jié)點(diǎn)出發(fā)，則第一次到達(dá)結(jié)點(diǎn)A爽撒，不輸出A入蛆，繼續(xù)向左訪問，第一次訪問結(jié)點(diǎn)B硕勿，不輸出B哨毁；繼續(xù)到達(dá)D，H源武；
到達(dá)H扼褪，H左子樹為空，則返回到H粱栖，此時(shí)第二次訪問H话浇，不輸出H；
H右子樹為空闹究，則返回至H幔崖，此時(shí)第三次到達(dá)H，故輸出H；
由H返回至D赏寇，第二次到達(dá)D吉嫩，不輸出D；
繼續(xù)訪問至I嗅定，I左右子樹均為空率挣，故第三次訪問I時(shí)，輸出I露戒；
返回至D，此時(shí)第三次到達(dá)D捶箱，故輸出D智什；
按照同樣規(guī)則繼續(xù)訪問，輸出J丁屎、E荠锭、B、F晨川、G证九、C，A共虑；

則圖3.13所示二叉樹的后序遍歷輸出為：
HIDJEBFGCA

三愧怜、二叉查找樹

1 定義

二叉查找樹也叫二叉搜索樹，二叉排序樹
1.若它的左子樹不為空妈拌，則左子樹上所有結(jié)點(diǎn)的值均小于等于根結(jié)點(diǎn)的值拥坛；
2.若它的右子樹不為空，則右子樹上所有結(jié)點(diǎn)的值均大于等于根結(jié)點(diǎn)的值尘分；
3.它的左右子樹均為二分查找樹猜惋。

2 圖解實(shí)例

選取一個(gè)節(jié)點(diǎn)為參照根節(jié)點(diǎn)，會(huì)發(fā)現(xiàn)所有的左側(cè)子節(jié)點(diǎn)小于等于參照點(diǎn)培愁，右側(cè)大于等于參照點(diǎn)著摔。

比如根節(jié)點(diǎn)9， 9所有的左側(cè)子節(jié)點(diǎn)（5定续、2谍咆、7、1香罐、3）都小于等于9.

比如根節(jié)點(diǎn)13卧波，13所有的左側(cè)子節(jié)點(diǎn)（11、10庇茫、12）都大于等于13.

image

3 查找

查找節(jié)點(diǎn) 10：根節(jié)點(diǎn)9開始港粱，10>9 右側(cè)，10<13 左側(cè)，10<11 左側(cè)查坪，找到10.

image

下圖是二叉查找樹的極端情況

image.png

二叉查找樹就是為了提高查詢效率寸宏，而當(dāng)前這種和我們寫了一堆for循環(huán)是一樣的。
為了應(yīng)對(duì)這種情況：又出現(xiàn)了平衡二叉樹--紅黑樹偿曙。后面會(huì)提到氮凝。

四、紅黑樹

1 定義

R-B Tree望忆，全稱是Red-Black Tree罩阵，又稱為“紅黑樹”，它一種特殊的二叉查找樹启摄。紅黑樹的每個(gè)節(jié)點(diǎn)上都有存儲(chǔ)位表示節(jié)點(diǎn)的顏色稿壁，可以是紅(Red)或黑(Black)。

紅黑樹的特性:
（1）每個(gè)節(jié)點(diǎn)或者是黑色歉备，或者是紅色傅是。
（2）根節(jié)點(diǎn)是黑色。
（3）每個(gè)葉子節(jié)點(diǎn)（NIL）是黑色蕾羊。 [注意：這里葉子節(jié)點(diǎn)喧笔，是指為空(NIL或NULL)的葉子節(jié)點(diǎn)！]
（4）如果一個(gè)節(jié)點(diǎn)是紅色的龟再，則它的子節(jié)點(diǎn)必須是黑色的书闸。也就是不能有連在一起的紅色節(jié)點(diǎn)，但是可以有連在一起的黑色節(jié)點(diǎn)
（5）滿足所有的二叉查找樹的性質(zhì)

紅黑樹示意圖如下：

image

2 變換規(guī)則

image.png

image

左旋又分為兩種情況利凑，

（1）我們操作的結(jié)點(diǎn)E是整棵樹的根節(jié)點(diǎn)，那么左旋實(shí)現(xiàn)為下面步驟

a. 將結(jié)點(diǎn)s的左子樹變化為E的右子樹截碴。也就是將E.rightchild值修改為S.leftchild后將S.leftchild置為NULL,將S.leftchild.parent置為結(jié)點(diǎn)E的指針梳侨。
b.將結(jié)點(diǎn)E的父結(jié)點(diǎn)指針parent指向結(jié)點(diǎn)S
c.將s結(jié)點(diǎn)的父結(jié)點(diǎn)指針parent置為NULL。

（2）我們操作的結(jié)點(diǎn)E有父結(jié)點(diǎn)，那么左旋實(shí)現(xiàn)為下面步驟

a. 將結(jié)點(diǎn)s的左子樹變化為E的右子樹，也就是將E.rightchild值修改為S.leftchild后將S.leftchild置為NULL束凑，將S.leftchild.parent置為結(jié)點(diǎn)E的指針
b.聲明一個(gè)輔助指針變量汪诉，指向結(jié)點(diǎn)E迄本，即存儲(chǔ)的是E結(jié)點(diǎn)的指針嘉赎。將結(jié)點(diǎn)S的父結(jié)點(diǎn)指針parent修改為結(jié)點(diǎn)E的父指針parent的值
c.通過輔助指針變量，將結(jié)點(diǎn)E的父指針parent修改指向結(jié)點(diǎn)S奢米。

3）右旋

image

右旋同樣分為兩種情況鬓长，與左旋情況類似英上，故實(shí)際操作參考左旋窗声。

3 插入

首先使用二叉搜索樹的插入算法將一個(gè)元素插入到紅黑樹中固翰，該元素作為新的葉子結(jié)點(diǎn)插入到某一外部結(jié)點(diǎn)位置，才插入結(jié)點(diǎn)過程中需要為新元素染色没炒。

注意：上述描述中一個(gè)很重要的點(diǎn)是，在插入元素時(shí)犯戏，是將元素作為葉子結(jié)點(diǎn)插入的送火，插入到原紅黑樹的外部結(jié)點(diǎn)。

插入結(jié)點(diǎn)染色情況

1.如果插入前是空樹先匪，那么新插入的元素就會(huì)成為根節(jié)點(diǎn)种吸，根據(jù)特征，需要將根節(jié)點(diǎn)染成黑色呀非。
2.如果紅黑樹非空坚俗，那么在紅黑樹中插入新的結(jié)點(diǎn)時(shí)，所有的點(diǎn)都默認(rèn)是紅色結(jié)點(diǎn)岸裙。

插入結(jié)點(diǎn)后調(diào)整和平衡過程

1.變顏色的情況： 當(dāng)前結(jié)點(diǎn)的父親是紅色猖败，且它的祖父結(jié)點(diǎn)的另一個(gè)結(jié)點(diǎn)（也就是叔叔結(jié)點(diǎn)）也是紅色：

（1）把父結(jié)點(diǎn)設(shè)為黑色
（2）把叔叔結(jié)點(diǎn)也設(shè)為黑色
（3）把祖父結(jié)點(diǎn)，也就是父親的父親設(shè)置為紅色（爺爺結(jié)點(diǎn)）
（4）把指針定義到祖父結(jié)點(diǎn)設(shè)為當(dāng)前要操作的結(jié)點(diǎn)（爺爺結(jié)點(diǎn)）降允。分析點(diǎn)的變換規(guī)則恩闻，進(jìn)行變換。

2.左旋：當(dāng)前父結(jié)點(diǎn)是紅色剧董，叔叔結(jié)點(diǎn)是黑色的時(shí)候幢尚，且當(dāng)前的結(jié)點(diǎn)時(shí)右子樹，則進(jìn)行左旋翅楼。左旋過程不需要進(jìn)行顏色變換尉剩。

3.右旋：當(dāng)前父結(jié)點(diǎn)時(shí)紅色，叔叔結(jié)點(diǎn)是黑色的時(shí)候毅臊，且當(dāng)前的結(jié)點(diǎn)是左子樹边涕，則進(jìn)行右旋。右旋過程中需要進(jìn)行顏色變換褂微，具體右旋過程如下功蜓。

（1）把父結(jié)點(diǎn)變?yōu)楹谏?br> （2）把祖父結(jié)點(diǎn)變?yōu)榧t色（爺爺結(jié)點(diǎn)）
（3）以祖父結(jié)點(diǎn)進(jìn)行右旋（爺爺結(jié)點(diǎn)）

實(shí)例講解

image

參考視頻：
https://www.bilibili.com/video/BV1tE411f7tP?p=4&spm_id_from=pageDriver