源碼學(xué)院算法與數(shù)據(jù)結(jié)構(gòu)樹二叉搜索

樹、二叉樹和二叉搜索樹樹的定義及相關(guān)術(shù)語二叉樹目錄二叉搜索樹樹的定義和術(shù)語樹的定義(遞歸定義)：有n個(gè)節(jié)點(diǎn)的樹有多少條邊？(n-1)樹是n(n≥0)個(gè)結(jié)點(diǎn)的有限集：若n=0，稱為空樹若n>0，則有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；當(dāng)n>1時(shí)，除根以外的其他結(jié)點(diǎn)劃分為m(m>0)個(gè)互不相交的有限集T1,T2,…Tm，其中每一個(gè)集合本身又是一棵樹，并且稱為根的子樹結(jié)點(diǎn)的度：該結(jié)點(diǎn)的子樹數(shù)目樹的度：樹中各結(jié)點(diǎn)度數(shù)的最大值兒子結(jié)點(diǎn)葉子:所有子樹皆為空的節(jié)點(diǎn)父結(jié)點(diǎn)（從根到當(dāng)前節(jié)點(diǎn)的路徑上的離當(dāng)前節(jié)點(diǎn)最近的節(jié)點(diǎn)）、––兄弟結(jié)點(diǎn)祖先結(jié)點(diǎn)：從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上所有結(jié)點(diǎn)層次、高度：null為0,

max(subtree)+1有序樹：規(guī)定所有結(jié)點(diǎn)的兒子結(jié)點(diǎn)次序，否則為無序樹ABCDEF

G

HIL高度為4

、度為3

的樹BELBCDEF

G

HILN個(gè)節(jié)點(diǎn)的樹會(huì)有多少條邊？N-1A樹的定義及相關(guān)術(shù)語二叉樹目錄二叉搜索樹二叉樹二叉樹的定義(遞歸定義)空或有一個(gè)根，根有左子樹、右子樹；而左右子樹本身又是二叉樹特點(diǎn)：每個(gè)結(jié)點(diǎn)至多只有兩棵子樹，子樹有左右之分例：結(jié)點(diǎn)總數(shù)為3時(shí)的所有二叉樹的樹的形狀N個(gè)節(jié)點(diǎn)構(gòu)成多少棵不同的二叉樹？BCDEFL例：二叉樹B二叉樹的性質(zhì)性質(zhì)1：在二叉樹的第i

層上至多有2i-1個(gè)結(jié)點(diǎn)BCDEFLA1層：結(jié)點(diǎn)個(gè)數(shù)21-1=20

個(gè)2層：結(jié)點(diǎn)個(gè)數(shù)22-1=21

個(gè)3層：結(jié)點(diǎn)個(gè)數(shù)23-1=22

個(gè)性質(zhì)2：高度為k的二叉樹至多有2

k-1

個(gè)結(jié)點(diǎn)（sum(2^0+2^1+…+

2^(k-1))性質(zhì)3：二叉樹的葉子結(jié)點(diǎn)數(shù)n0

等于度為2

的結(jié)點(diǎn)數(shù)n2+1???完全二叉樹BCDEFLAP

Q

RS

UBCDEFLAP

Q

RS

U

V

W

X滿二叉樹: 每層結(jié)點(diǎn) 數(shù)最多完全二叉樹: 1、滿二叉樹2、從滿二叉樹最底層從右向左依次去掉若干結(jié)點(diǎn)形成的性質(zhì)4：具有

n

個(gè)結(jié)點(diǎn)的完全二叉樹高度為

log2n +

1完全二叉樹性質(zhì)5：對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹按照從第一層（根所在的層次〕到最后一層，并且每一層都按照從左到右的次序進(jìn)行編號(hào)。根結(jié)點(diǎn)的編號(hào)為1，最后一個(gè)結(jié)點(diǎn)的編號(hào)為n。1：對(duì)任何一個(gè)編號(hào)為i

的結(jié)點(diǎn)而言，它的左兒子的編號(hào)為2i(若2i<=n),而右兒子的編號(hào)為2i+1(若2i

+1<=n)。2：對(duì)任何一個(gè)編號(hào)為

j

的結(jié)點(diǎn)而言，它的父親結(jié)點(diǎn)的的編號(hào)為

j/2

。根結(jié)點(diǎn)無父結(jié)點(diǎn)。P

Q

R

S

U8

9

10

11

12D7F6E5B4C3L2A1i:左子樹的編號(hào)：2i右子樹：2i+1二叉樹的順序存儲(chǔ)ABCDEFGHILA1-1B92C53D6-1E-1-1F-1-1G87H-1-1I-1-1L-140123456789rightdata

left應(yīng)用范圍：適用于二叉樹上的結(jié)點(diǎn)個(gè)數(shù)已知，或不支持動(dòng)態(tài)存儲(chǔ)分配的高級(jí)語言。二叉樹的順序存儲(chǔ)特殊情況：完全二叉樹應(yīng)用范圍：適用于完全二叉樹，且結(jié)點(diǎn)個(gè)數(shù)已知。DCGEFBAHILABCDEFGHI0123456789L二叉樹的順序存儲(chǔ)特殊情況：若不是完全二叉樹，許多數(shù)據(jù)場(chǎng)為空，不合算。如下例所示：考慮浪費(fèi)空間最多的情況，是一種什么情況？浪費(fèi)2^k-1–k

個(gè)單元AB∧D∧∧∧HI0123456789DBAHI二叉樹的鏈接存儲(chǔ)僅定義結(jié)點(diǎn)的類型即可結(jié)點(diǎn)之間的關(guān)系通過指針實(shí)現(xiàn)ABCDEFGHILdataleft

right標(biāo)準(zhǔn)形式：（二叉鏈表）廣義標(biāo)準(zhǔn)形式：（三叉鏈表）dataleft

right

Parent二叉樹的鏈接存儲(chǔ)例：A∧B/\∧C∧

DE∧F∧∧G∧GFDCBAE二叉樹遍歷設(shè)N

代表根節(jié)點(diǎn)，L

代表左子樹，R

代表右子樹。a.前序（或先序）：如果二叉樹為空，則操作為空：否則訪問根結(jié)點(diǎn)；前序遍歷左子樹；前序遍歷右子樹。記為：NLR。b.中序：如果二叉樹為空，則操作為空：否則中序遍歷左子樹；訪問根結(jié)點(diǎn)；中序遍歷右子樹。記為：LNR。如果二叉樹為空，則操作為空：否則后序遍歷左子樹；后序遍歷右子樹；訪問根結(jié)點(diǎn)。記為：LRN。(非遞歸，只用一前個(gè)序Sta：ckA)、L、B、E、C、D、W、c.后序：XBCDLALRW

LRXERLR中序：B、L、E、A、C、W、X、D后序：B、E、L、X、W、D、C、ABCDELAXWBCDELAWXALCDWXBE42713Result:

4,

2,

1,3,

7preorder(4):preorder(2):preorder(1):preorder(null)preorder(null)preorder(3)

:preorder(null)preorder(null)preorder(7):preorder(null)preorder(null)42713Result:25curr745231二叉樹與遞歸統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的數(shù)目求樹的最大高度求樹的節(jié)點(diǎn)數(shù)量層次遍歷樹(遞歸與非遞歸的方法）樹的定義及相關(guān)術(shù)語二叉樹目錄二叉搜索樹二叉搜索樹二叉搜索樹Binary

Search

Tree（BST）定義：–

或者是一棵空樹；–是具有下列性質(zhì)的二叉樹：對(duì)于任何一個(gè)結(jié)點(diǎn)，設(shè)其值為K則該結(jié)點(diǎn)的左子樹(若不空)的任意一個(gè)結(jié)點(diǎn)的值都小于K；該結(jié)點(diǎn)的右子樹(若不空)的任意一個(gè)結(jié)點(diǎn)的值都大于K；?而且它的左右子樹也分別為BST性質(zhì):中序遍歷是正序的（由小到大的排列）二叉搜索樹–搜索若二叉排序樹為空，則查找不成功；否則，–

若給定值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功––若給定值小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹上進(jìn)行查找若給定值大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹上進(jìn)行查找查找37？1，2，3，4，5：平衡二叉樹：AVL、紅黑樹二叉搜索樹–插入首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子將被插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入若二叉樹為空。則首先單獨(dú)生成根結(jié)點(diǎn)e.g：將數(shù)的序列：122、99、250、110、300、280

作為二叉排序樹的結(jié)點(diǎn)的關(guān)鍵字值，生成二叉排序樹。1223001102809912212299122250991222501109912225030011099輸入順序不同所建立的不同二叉排序樹注意二叉搜索樹–刪除

和插入相反，刪除在查找成功之后進(jìn)行，并且要求在刪除二叉排序樹上某個(gè)結(jié)點(diǎn)之后，仍然保持二叉排序樹的特性?？煞譃?種情況：被刪除的結(jié)點(diǎn)是葉子；被刪除的結(jié)點(diǎn)只有左子樹或者只有右子樹；–被刪除的結(jié)點(diǎn)既有左子樹，也有右子樹；50308020908540358832（1）被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)例如:被刪關(guān)鍵字=

20

88直接刪去該節(jié)點(diǎn)。其雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為“空”結(jié)論：二叉搜索樹–刪除2088503080209085403532

88其雙親結(jié)點(diǎn)的相應(yīng)指針域的值改為“指向被刪除結(jié)點(diǎn)的左子樹或右子樹”。（2）被刪除的結(jié)點(diǎn)只有左子樹或者只有右子樹被刪關(guān)鍵字=4080用其左子樹或者右子樹代替它。結(jié)論：二叉搜索樹–刪除30802090854035884032前驅(qū)結(jié)點(diǎn)

被刪結(jié)點(diǎn)以其中序遍歷的前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)點(diǎn)。前驅(qū)是左子樹中最大的節(jié)點(diǎn)。被刪關(guān)鍵字=5050二叉搜索樹–刪除（3）被刪除的結(jié)點(diǎn)既有左子樹，也有右子樹144

Binary

Tree

Preorder

Traversal94

Binary

Tree

Inorder

Traversal145

Binary

Tree

Postorder

Traversal?102Binary

Tree

Level

Order

Traversal?107Binary

Tree

Level

Order

TraversalII?103Binary

Tree

Zigzag

Level

Order

Traversal?105Construct

Binary

Tree

from

Preorder

and

Inorder

Traversal?889Construct

Binary

Tree

from

Preorder

and

Postorder

Traversal?700Search

in

a