數(shù)據(jù)結(jié)構(gòu)課件-第05章 樹與二叉樹

數(shù)據(jù)結(jié)構(gòu)計算機領(lǐng)域本科教育教學改革試點工作計劃（“101計劃”）研究成果101樹與二叉樹第5章5.1問題引入5.2樹的定義與結(jié)構(gòu)5.3二叉樹5.4二叉樹的遍歷5.5哈夫曼樹5.6樹與森林5.7拓展延伸5.8應(yīng)用場景5.1問題引入：商品分類樹5.1問題引入數(shù)據(jù)結(jié)構(gòu)問題：如何方便了解超市商品有哪些類別？每個類別可分為哪些更小的類別，以及屬于該類別的終端商品有哪些？關(guān)鍵：如何展示商品不同類別之間的層次關(guān)系（包含關(guān)系）商品分類樹：5.1問題引入：商品分類樹5.1問題引入數(shù)據(jù)結(jié)構(gòu)商品分類樹

結(jié)構(gòu)與倒立的樹相似，展示對數(shù)以千萬計的商品由上至下、由粗到細的分類

根結(jié)點（所有商品）葉結(jié)點（終端商品）相鄰兩層結(jié)點用邊連接，表示父子關(guān)系（包含關(guān)系）除樹根外，每個結(jié)點都有且僅有一個父結(jié)點相鄰兩層結(jié)點有邊連接，表示父子關(guān)系5.1問題引入：商品分類樹5.1問題引入數(shù)據(jù)結(jié)構(gòu)商品分類樹

結(jié)構(gòu)與倒立的樹相似，展示對數(shù)以千萬計的商品由上至下、由粗到細的分類問題主要內(nèi)容如何在計算機上表達商品分類樹？能否用順序表、鏈表等線性結(jié)構(gòu)存儲樹？如何在計算機上查詢每個分類包含哪些商品？如何判斷兩個分類之間是否有包含關(guān)系？樹與二叉樹的定義、存儲實現(xiàn)、遍歷方式及其典型應(yīng)用5.2樹的定義與結(jié)構(gòu)5.2樹的定義與結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)樹的定義：

遞歸定義父子關(guān)系屬于二元關(guān)系

<r,

ri>由于根結(jié)點沒有父結(jié)點，而其它所有結(jié)點都有一個且僅一個父結(jié)點，所以由n個結(jié)點構(gòu)成的樹共包含n-1對父子關(guān)系如果用邊連接有父子關(guān)系的結(jié)點，則樹中共有n-1條邊思考：如何從定義中推斷非根結(jié)點有且僅有一個父結(jié)點?

5.2樹的定義與結(jié)構(gòu)5.2樹的定義與結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)樹的結(jié)構(gòu)示例：樹T

=

{A,

B,

C,

D,

E,

F,

G,

H,

I,

J,

K,

L,

M}樹根：A子樹：T1

=

{B,

E,

F,

G,

K,

L}，B為根

T2

=

{C,

H},

C為根

T3

=

{D,

I,

J,

M},

D為根父子關(guān)系:

<A,

B>、<A,

C>、<A,

D>T1也是樹（遞歸定義）樹根：B子樹：{E},

{F,

K,

L},

{G}父子關(guān)系：<B,

E>,

<B,

F>,

<B,

G>樹的基本術(shù)語5.2樹的定義與結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)結(jié)點的度：子結(jié)點或非空子樹的個數(shù)樹的度：樹中所有結(jié)點的度的最大值葉結(jié)點：樹中度為0的結(jié)點中間結(jié)點：樹中葉結(jié)點以外的結(jié)點，亦稱內(nèi)部結(jié)點兄弟結(jié)點：父結(jié)點相同的結(jié)點彼此是兄弟結(jié)點結(jié)點的層次：根結(jié)點在第1層；如果結(jié)點的層次是??(??≥1)，則其子結(jié)點都在第??+1層。亦稱結(jié)點的深度

結(jié)點的高度：葉結(jié)點的高度等于1；中間結(jié)點的高度等于其所有子結(jié)點的高度的最大值加1樹的高度：根結(jié)點的高度，亦稱樹的深度有序樹：樹中各結(jié)點的子樹從左向右依次排列，不能交換次序；否則稱作無序樹森林：零個或多個互不相交（獨立）的樹的集合樹的基本術(shù)語5.2樹的定義與結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)結(jié)點度結(jié)點高度34層次（深度）1234葉結(jié)點：E,

G,

H,

J,

K,

L,

M樹的高度：4樹的度：3中間結(jié)點：A,

B,

C,

D,

F,

I331223221201010101010101兄弟結(jié)點：{B,

C,

D}

/

{E,

F,

G}

/

{I,

J}

/

{K,

L}樹的基本術(shù)語5.2樹的定義與結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)祖先結(jié)點：根沒有祖先；父結(jié)點以及父結(jié)點的祖先都是結(jié)點的祖先結(jié)點子孫結(jié)點：葉結(jié)點沒有子孫；中間結(jié)點的各子結(jié)點以及子結(jié)點的子孫都是它的子孫結(jié)點以任一結(jié)點為根的子樹中包含所有且僅有該結(jié)點的子孫(1)根結(jié)點是其它所有結(jié)點的祖先(2)如果結(jié)點u是結(jié)點v的祖先，則存在路徑<r1,

r2,

…

,

rn>，滿足r1=u,

rn=v且ri

是ri+1

的父結(jié)點(0<i<n)(3)由于任何非根結(jié)點有且僅有一個父結(jié)點，從祖先結(jié)點u到子孫結(jié)點v的路徑是唯一的結(jié)點B的子孫：{E,

F,

G,

K,

L}樹的基本操作5-2樹的定義與結(jié)構(gòu)

InitTree(tree):

初始化一個空樹tree

CreatTree(tree,definition):按照definition構(gòu)造一個樹

IsEmpty(tree):樹tree為空返回true,否則返回false

Root(tree):返回樹tree的根結(jié)點

Get(tree,node):返回樹tree的結(jié)點node的值

Parent(tree,node):返回樹tree中結(jié)點node的父結(jié)點

GetChild(tree,node,k):返回樹tree中結(jié)點node的第k個子樹

InsertChild(tree,node,k,subtree):將樹subtree插入到樹tree中，使其成為結(jié)點node的第k個子樹

Search(tree,x):在樹tree中查找值為x的結(jié)點，如果查找成功，返回結(jié)點，否則返回NIL

Traverse(tree):訪問樹tree中每個結(jié)點，且每個結(jié)點只訪問一次

5.3.1二叉樹的定義5.3二叉樹數(shù)據(jù)結(jié)構(gòu)二叉樹是應(yīng)用最廣泛的樹形結(jié)構(gòu)二叉樹每個結(jié)點有且僅有兩個子樹，并且子樹有左右區(qū)別（有序樹）二叉樹的定義：

5.3.1二叉樹的定義5.3二叉樹數(shù)據(jù)結(jié)構(gòu)二叉樹的基本形態(tài)：空樹單根樹左子樹非空，右子樹是空樹左子樹是空樹，右子樹非空左子樹和右子樹都非空只有一個結(jié)點有序樹二叉樹的基本操作5-3二叉樹BinaryTreeNode():創(chuàng)建一個二叉樹結(jié)點

Height(tree):返回二叉樹tree的高度（深度）

PreOrder(tree):前序遍歷二叉樹tree

InOrder(tree):中序遍歷二叉樹tree

PostOrder(tree):后序遍歷二叉樹tree

LevelOrder(tree):層序遍歷二叉樹tree

CreatBinaryTree(value,left_tree,right_tree):構(gòu)造二叉樹，根結(jié)點的數(shù)據(jù)為value,左子樹和右子樹分別是left_tree和right_treeIsLeaf(tree,node):如果二叉樹tree中結(jié)點node為葉結(jié)點，返回true；否則返回false

5.3.2滿二叉樹、完全二叉樹、完美二叉樹5.3二叉樹數(shù)據(jù)結(jié)構(gòu)滿二叉樹：由度為0的葉結(jié)點和度為2的中間結(jié)點構(gòu)成的二叉樹，樹中沒有度為1的結(jié)點滿二叉樹非滿二叉樹滿二叉樹實例：哈夫曼樹、表達式樹形態(tài)結(jié)構(gòu)特殊、應(yīng)用廣泛的二叉樹5.3.2滿二叉樹、完全二叉樹、完美二叉樹5.3二叉樹數(shù)據(jù)結(jié)構(gòu)完全二叉樹

完全二叉樹實例：堆形態(tài)結(jié)構(gòu)特殊、應(yīng)用廣泛的二叉樹5.3.2滿二叉樹、完全二叉樹、完美二叉樹5.3二叉樹數(shù)據(jù)結(jié)構(gòu)完全二叉樹

形態(tài)結(jié)構(gòu)特殊、應(yīng)用廣泛的二叉樹沒有度為1的中間結(jié)點只有一個度為1的中間結(jié)點且左子樹非空5.3.2滿二叉樹、完全二叉樹、完美二叉樹5.3二叉樹數(shù)據(jù)結(jié)構(gòu)完全二叉樹從第1層到第???2層全是度為2的中間結(jié)點第??層的結(jié)點都是葉結(jié)點，度為0在第???1層，各結(jié)點的度從左向右單調(diào)非遞增排列，同時度為1的結(jié)點要么沒有，要么只有一個且該結(jié)點的左子樹非空非完全二叉樹示例理由：度為0的結(jié)點D在度為2的結(jié)點E的左邊，不滿足條件(3)理由1：結(jié)點C的度為1，不滿足條件(1)理由2：結(jié)點E的度為1，但左子樹為空，不滿足條件(3)形態(tài)結(jié)構(gòu)特殊、應(yīng)用廣泛的二叉樹5.3.2滿二叉樹、完全二叉樹、完美二叉樹5.3二叉樹數(shù)據(jù)結(jié)構(gòu)

完美二叉樹中的所有子樹都是完美二叉樹去掉完全二叉樹最下層的葉結(jié)點，由此生成的樹是完美二叉樹形態(tài)結(jié)構(gòu)特殊、應(yīng)用廣泛的二叉樹5.3.2滿二叉樹、完全二叉樹、完美二叉樹5.3二叉樹數(shù)據(jù)結(jié)構(gòu)擴充二叉樹：在二叉樹結(jié)點的空子樹位置添加特殊的結(jié)點：空樹葉，形成的二叉樹稱作擴充二叉樹

二叉樹中所有結(jié)點都被擴充成度為2的中間結(jié)點擴充二叉樹是滿二叉樹，并且所有的葉結(jié)點都是空樹葉形態(tài)結(jié)構(gòu)特殊、應(yīng)用廣泛的二叉樹5.3.3二叉樹基本性質(zhì)5.3二叉樹數(shù)據(jù)結(jié)構(gòu)命題5-1：設(shè)非空二叉樹中度為??∈[??,??]的結(jié)點數(shù)為??i

，則????=????+??。

定理5-1：（滿二叉樹定理）非空滿二叉樹中葉結(jié)點數(shù)等于中間結(jié)點數(shù)加1。

證明：滿二叉樹沒有度為1的中間結(jié)點，由命題5-1直接得證5.3.3二叉樹基本性質(zhì)5.3二叉樹數(shù)據(jù)結(jié)構(gòu)

5.3.3二叉樹基本性質(zhì)5.3二叉樹數(shù)據(jù)結(jié)構(gòu)

完全二叉樹的分層編號5.3二叉樹數(shù)據(jù)結(jié)構(gòu)

實現(xiàn)對所有結(jié)點從上至下、從左向右連續(xù)編號！

5.3.3二叉樹基本性質(zhì)5.3二叉樹數(shù)據(jù)結(jié)構(gòu)

定理5-3是完全二叉樹實現(xiàn)順序存儲以及二叉堆的重要性質(zhì)！

5.3.4二叉樹的順序存儲實現(xiàn)5.3二叉樹數(shù)據(jù)結(jié)構(gòu)

二叉樹的主要存儲方式：順序存儲+鏈接存儲完全二叉樹的順序存儲：完全二叉樹所有結(jié)點可以分層從左向右連續(xù)編號，可用一組地址連續(xù)的存儲單元（順序表）存儲二叉樹的各個結(jié)點各結(jié)點的索引（編號）與順序表位置一一對應(yīng)，結(jié)點的數(shù)據(jù)存放在順序表相應(yīng)位置的單元中5.3.4二叉樹的順序存儲實現(xiàn)5.3二叉樹數(shù)據(jù)結(jié)構(gòu)非完全二叉樹的順序存儲結(jié)點編號：樹根的索引為1；設(shè)結(jié)點的編號為??(??≥1)，如果其左子樹非空，則左子結(jié)點的編號為2??；如果右子樹非空，則右子結(jié)點為2??+1順序存放：用一組地址連續(xù)的存儲單元存儲二叉樹的各個結(jié)點各結(jié)點的索引（編號）與順序表位置一一對應(yīng)，結(jié)點的數(shù)據(jù)存放在順序表相應(yīng)位置的單元中5.3.4二叉樹的順序存儲實現(xiàn)5.3二叉樹數(shù)據(jù)結(jié)構(gòu)

缺點對一般的二叉樹，可能造成空間浪費在最壞情況下，存放n個結(jié)點的二叉樹可能需要長度為O(2n)的順序表可用其它序列化的方法降低順序存儲的空間復雜度，但無法通過在順序表中的相對位置直接確定兩個結(jié)點是否有父子關(guān)系，增加了查詢結(jié)點間邏輯關(guān)系的時間復雜度5.3.5二叉樹的鏈接存儲實現(xiàn)5.3二叉樹數(shù)據(jù)結(jié)構(gòu)二叉樹的主要存儲方式：順序存儲+鏈接存儲鏈接存儲：使用鏈表存放二叉樹，比順序存儲能更有效地表達二叉樹的非線性邏輯結(jié)構(gòu)數(shù)據(jù)域data左指針域left右指針域right數(shù)據(jù)域data左指針域left右指針域right父結(jié)點指針域parent二叉鏈表三叉鏈表指向左子結(jié)點指向右子結(jié)點指向左子結(jié)點指向右子結(jié)點指向父結(jié)點5.3.5二叉樹的鏈接存儲實現(xiàn)5.3二叉樹數(shù)據(jù)結(jié)構(gòu)鏈接存儲：使用鏈表存放二叉樹，比順序存儲能更有效地表達二叉樹的非線性邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)二叉鏈表存儲結(jié)構(gòu)

用指針tree表示二叉樹構(gòu)造二叉樹的算法5-3二叉樹算法5-1：構(gòu)造二叉樹CreateBinaryTree(value,left_tree,right_tree)輸入：結(jié)點數(shù)據(jù)value,二叉樹left_tree和right_tree輸出：以value為根結(jié)點數(shù)據(jù)、left_tree和right_tree為左右子樹的二叉樹

tree←newBinaryTreeNode()//生成新的二叉鏈表結(jié)點

tree.data←value//設(shè)置根結(jié)點的數(shù)據(jù)

tree.left←left_tree//設(shè)置根的左子樹

tree.right←right_tree//設(shè)置根的右子樹

return

tree//返回構(gòu)造的二叉樹5.4.1二叉樹遍歷的基本概念5.4二叉樹的遍歷數(shù)據(jù)結(jié)構(gòu)遍歷的概念：按預先設(shè)定的順序依次訪問樹中所有結(jié)點，并且每個結(jié)點僅訪問一次深度優(yōu)先遍歷：按序獨立處理二叉樹的各個分支單元：根r、左子樹L和右子樹R廣度優(yōu)先遍歷：按層從上至下、從左向右依次訪問樹中所有結(jié)點，也稱作層序遍歷廣度優(yōu)先遍歷：按層從上至下、從左向右依次訪問樹中所有結(jié)點，也稱作層序遍歷rLR3種深度優(yōu)先遍歷方案：

(1)

rLR

—前序

(2)

LrR

—中序

(3)

LRr

—后序深度優(yōu)先遍歷遞歸思想：對左子樹L和右子樹R按相同的方案進行遍歷深度原則：獨立處理各分支，即在訪問完一個分支的所有結(jié)點后，才能開始遍歷下一個分支限制子樹的遍歷順序：對子樹的遍歷始終按從左向右的順序進行5.4.2二叉樹遍歷的遞歸算法5.4二叉樹的遍歷數(shù)據(jù)結(jié)構(gòu)前序遍歷方案訪問根結(jié)點r前序遍歷左子樹L前序遍歷右子樹RrLR中序遍歷方案中序遍歷左子樹L訪問根結(jié)點r中序遍歷右子樹R后序遍歷方案后序遍歷左子樹L后序遍歷右子樹R訪問根結(jié)點r5.4.2二叉樹遍歷的遞歸算法5.4二叉樹的遍歷數(shù)據(jù)結(jié)構(gòu)前序遍歷：<A,B,D,H,I,E,J,C,F,K>中序遍歷：<H,D,I,B,E,J,A,F,K,C>后序遍歷：<H,I,D,J,E,B,K,F,C,A>根結(jié)點位置：前序遍歷的最前后序遍歷的最后中序遍歷出現(xiàn)在左子樹和右子樹遍歷結(jié)果之間遍歷二叉樹并按序輸出結(jié)點數(shù)據(jù)遞歸算法5-4二叉樹的遍歷算法5-2.前序遍歷二叉樹PreOrder(tree)if

tree

≠

NILthen//空樹不做處理，直接返回|Visit(tree)

//訪問根結(jié)點|PreOrder(tree.left)

//前序遍歷左子樹|PreOrder(tree.right)//前序遍歷右子樹end算法5-3.中序遍歷二叉樹InOrder(tree)if

tree

≠

NILthen|Inorder(tree.left)

//中序遍歷左子樹|

Visit(tree)

//訪問根結(jié)點|InOrder(tree.right)//中序遍歷右子樹end算法5-4.后序遍歷二叉樹PostOrder(tree)if????????

≠

NILthen|Postorder(tree.left)

//后序遍歷左子樹|PostOrder(tree.right)//后序遍歷右子樹|

Visit(tree)

//訪問根結(jié)點end后序遍歷遞歸算法的應(yīng)用5-4二叉樹的遍歷算法5-5.計算二叉樹高度Height(tree)輸入：二叉樹tree輸出：二叉樹的高度值iftree

=

NILthen//空樹|return0//空樹的高度為0else|h_left←Height(tree.left)

//遍歷左子樹，求子樹的高度|h_right←Height(tree.right)

//遍歷右子樹，求子樹的高度|returnMax(h_left,h_right)+1

//樹的高度等于左右子樹高度

//的較大值加1end表達式樹5.4二叉樹的遍歷數(shù)據(jù)結(jié)構(gòu)算術(shù)表達式：由常數(shù)、運算符和括號組成，有前綴、中綴、后綴三種表示法

中綴表示法：9

+

(6

+

3

*

2)

/

(8

/

(5

-

3))

前綴表示法：+9/+6*32/8-53后綴表示法：9632*+853-//+表達式樹：表示算術(shù)表達式（非線性）邏輯結(jié)構(gòu)的二叉樹

中綴表達式的遞歸定義單個常數(shù)是表達式若exp1、exp2是表達式，則(exp1)

op

(exp2)

也是表達式

(op表示運算符)表達式樹單個常數(shù)用單根樹表示若表達式包含多個常數(shù)及運算符，將表達式分解成(expr_left)op(expr_right)用根結(jié)點表示運算符op，并用左右子樹分別表示expr_left和expr_right（遞歸）轉(zhuǎn)換表達式樹5.4二叉樹的遍歷數(shù)據(jù)結(jié)構(gòu)9

+

(6

+

3

*

2)

/

(8

/

(5

-

3))

轉(zhuǎn)換中綴表達式表達式樹葉結(jié)點都對應(yīng)常數(shù)每個中間結(jié)點都存放一個運算符表達式樹是滿樹根結(jié)點是表達式中優(yōu)先級最低的運算符表達式樹5.4二叉樹的遍歷數(shù)據(jù)結(jié)構(gòu)表達式樹前序遍歷結(jié)果：+9/+6*32/8-53后序遍歷結(jié)果：9632*+853-//+

中序遍歷結(jié)果：9

+

6

+

3

*

2

/

8

/

5

–

3

沒有括號，不是正確的中綴表達式！表達式：9

+

(6

+

3

*

2)

/

(8

/

(5

-

3))

需要對左右子樹生成的表達式加上括號=前綴表示法=后綴表示法

將表達式樹轉(zhuǎn)換成中綴表達式的算法5-4二叉樹的遍歷算法5-6.

PrintInfixExpression(tree)輸入：非空二叉樹tree輸出：中綴表達式（含冗余括號）

iftree.left

≠

NILthen

//左子樹非空|print

(

//輸出左括號|PrintInfixExpression(tree.left)

//中序遍歷左子樹并生成表達式|print

)

//輸出右括號，與前面左括號一起將表達式加上括號endprinttree.data

//若結(jié)點是葉結(jié)點，輸出常數(shù)；否則，輸出運算符iftree.right

≠

NILthen//右子樹非空|print

(

//輸出左括號|PrintInfixExpression(tree.right)

//中序遍歷右子樹并生成表達式|print

)

//輸出右括號，與前面左括號一起將表達式加上括號end表達式樹5.4二叉樹的遍歷數(shù)據(jù)結(jié)構(gòu)表達式樹前序遍歷結(jié)果：+9/+6*32/8-53

前綴表示法后序遍歷結(jié)果：9632*+853-//+

后綴表示法算法5-6：(9)+(((6)+((3)*(2)))/((8)/((5)-(3))))

中綴表示法

表達式：9

+

(6

+

3

*

2)

/

(8

/

(5

-

3))

通過遍歷將表達式樹轉(zhuǎn)換為算術(shù)表達式的時間復雜度是O(n),

n表示結(jié)點數(shù)目思考：如何將算術(shù)（中綴）表達式轉(zhuǎn)換為表達式樹，分析需要使用的關(guān)鍵數(shù)據(jù)結(jié)構(gòu)5.4.3二叉樹遍歷的非遞歸算法5.4二叉樹的遍歷數(shù)據(jù)結(jié)構(gòu)遞歸算法的問題：

(1)存在不支持遞歸算法的程序設(shè)計語言

(2)遞歸算法在運行中，需要系統(tǒng)在內(nèi)存棧中分配空間保存函數(shù)的參數(shù)、返回地址以及局部變量等，運行效率較低

(3)系統(tǒng)對每個進程分配的棧容量有限，如果二叉樹的深度太大造成遞歸調(diào)用的層次太高，容易導致棧溢出非遞歸算法實現(xiàn)的關(guān)鍵：使用棧結(jié)構(gòu)模擬函數(shù)調(diào)用中系統(tǒng)棧的工作原理算法5-7：非遞歸前序遍歷PreOrder(tree)5-4二叉樹的遍歷

InitStack(stack)//初始化棧stack，用于存放結(jié)點

while

tree

≠

NIL或IsEmpty(stack)=false

do|while

tree

≠

NIL????

//當前結(jié)點不是空結(jié)點

||Visit(tree)

//訪問結(jié)點

||Push(stack,tree)//結(jié)點壓入棧

||tree←tree.left

//沿左分支下移

|end

|ifIsEmpty(stack)=falsethen//如果棧不為空

||tree←Top(stack)||Pop(stack)//彈出棧頂結(jié)點

||tree←tree.right//移到棧頂結(jié)點的右子樹

|end

endDestroyStack(stack)沿左分支下移，并將經(jīng)過的結(jié)點壓入棧tree=NIL表示左子樹為空，或者左子樹遍歷結(jié)束，則從棧中彈出結(jié)點，開始遍歷結(jié)點的右子樹算法5-8：非遞歸中序遍歷InOrder(tree)5-4二叉樹的遍歷

InitStack(stack)//初始化棧stack，用于存放結(jié)點

while

tree

≠

NIL或IsEmpty(stack)=false

do|while

tree

≠

NIL????

//當前結(jié)點不是空結(jié)點

||Push(stack,tree)//結(jié)點壓入棧

||tree←tree.left

//沿左分支下移

|end

|ifIsEmpty(stack)=falsethen//如果棧不為空

||tree←Top(stack)

|

|

Visit(tree)

//訪問棧頂結(jié)點||Pop(stack)//彈出棧頂結(jié)點

||tree←tree.right//移到棧頂結(jié)點的右子樹

|end

endDestroyStack(stack)沿左分支下移，并將經(jīng)過的結(jié)點壓入棧tree=NIL表示左子樹為空，或者左子樹遍歷結(jié)束，則從棧中彈出結(jié)點，開始遍歷結(jié)點的右子樹5.4.3二叉樹遍歷的非遞歸算法5.4二叉樹的遍歷數(shù)據(jù)結(jié)構(gòu)后序遍歷算法的非遞歸化二叉樹所有結(jié)點的后序遍歷次序，用各結(jié)點左邊的數(shù)字表示

后序遍歷次序的結(jié)點序列可分為多個段，用虛線分開，每段中的結(jié)點具有以下性質(zhì)：段中各結(jié)點的訪問次序是連續(xù)的，并且最先訪問（次序最?。┑慕Y(jié)點沒有右子結(jié)點段中若有多個結(jié)點，則次序相鄰的任意兩個結(jié)點，次序小的結(jié)點是次序大的結(jié)點的右子結(jié)點段中次序最大的結(jié)點如果不是根，則是其父結(jié)點的左子結(jié)點算法5-9：非遞歸后序遍歷PostOrder(tree)5-4二叉樹的遍歷InitStack(stack)while

tree

≠

NIL或IsEmpty(stack)=falsedo|while

tree

≠

NIL????//當前結(jié)點不是空結(jié)點||Push(stack,tree)//結(jié)點壓入棧||tree←tree.left//沿左分支下移|end

||top←Top(stack)

//stack非空，top指向棧頂結(jié)點|pre_top←NIL

//初始化pre_top|

//如果棧頂結(jié)點的右子樹為空，開始從棧彈出結(jié)點沿左分支下移，并將經(jīng)過的結(jié)點壓入棧開始時，pre_top

=

NIL(continue)5-4二叉樹的遍歷|whileIsEmpty(stack)=false

且top.right=pre_top

do||Visit(top)

//訪問當前棧頂結(jié)點||pre_top←top//棧頂結(jié)點傳給pre_top||Pop(stack)//彈出棧頂結(jié)點||ifIsEmpty(stack)=falsethen|||top←Top(stack)//棧非空，top指向新的棧頂結(jié)點||else|||top←NIL//空棧，top賦值NIL，結(jié)束遍歷||end

|end|if

top≠NILthen

||tree←top.right//移到棧頂結(jié)點的右子樹并開始遍歷|endendDestroyStack(stack)從右子樹為空的結(jié)點開始。依次彈出各段中的結(jié)點若彈出的結(jié)點是新棧頂結(jié)點的右子結(jié)點，繼續(xù)彈出5.4.3二叉樹遍歷的非遞歸算法5.4二叉樹的遍歷數(shù)據(jù)結(jié)構(gòu)遞歸算法的問題：

(1)存在不支持遞歸算法的程序設(shè)計語言

(2)遞歸算法在運行中，需要系統(tǒng)在內(nèi)存棧中分配空間保存函數(shù)的參數(shù)、返回地址以及局部變量等，運行效率較低

(3)系統(tǒng)對每個進程分配的棧容量有限，如果二叉樹的深度太大造成遞歸調(diào)用的層次太高，容易導致棧溢出非遞歸算法實現(xiàn)的關(guān)鍵：使用棧結(jié)構(gòu)模擬函數(shù)調(diào)用中系統(tǒng)棧的工作原理非遞歸算法分析：前序、中序和后序的非遞歸算法均使用一個存放結(jié)點的棧實現(xiàn)，并且在遍歷過程中每個結(jié)點都有且僅有1次入棧和1次出棧的機會，因此算法的時間復雜度和空間復雜度都是O(n)，其中n表示二叉樹的結(jié)點數(shù)層序遍歷5.4二叉樹的遍歷數(shù)據(jù)結(jié)構(gòu)廣度優(yōu)先遍歷：從根結(jié)點開始，從上至下按層訪問每個結(jié)點，并且每層的結(jié)點按照從左向右的順序進行處理層序遍歷方案通常設(shè)計成非遞歸的算法，可以用隊列結(jié)構(gòu)來實現(xiàn)層序遍歷：<A,B,C,D,E,F,H,I,J,K>算法5-10：層序遍歷二叉樹LevelOrder(tree)5-4二叉樹的遍歷InitQueue(queue)

//初始化隊列queue，用于存放結(jié)點EnQueue(queue,tree)

//樹根結(jié)點入隊whileIsEmpty(queue)=falsedo|node_ptr←GetFront(queue)//取出隊首結(jié)點|DeQueue(queue)

//隊首出隊|ifnode_ptr≠NILthen//結(jié)點非空||Visit(node_ptr)//訪問結(jié)點||EnQueue(queue,node_ptr.left)//左子結(jié)點入隊||EnQueue(queue,node_ptr.right)//右子結(jié)點入隊|endend

DestroyQueue(queue)層序遍歷5.4二叉樹的遍歷數(shù)據(jù)結(jié)構(gòu)廣度優(yōu)先遍歷：從根結(jié)點開始，從上至下按層訪問每個結(jié)點，并且每層的結(jié)點按照從左向右的順序進行處理層序遍歷：<A,B,C,D,E,F,H,I,J,K>算法分析：二叉樹的每個結(jié)點都會入隊1次，然后出隊1次，因此層序遍歷的時間復雜度為O(n)，與深度優(yōu)先遍歷相同5.4.4二叉樹的序列化與反序列化5.4二叉樹的遍歷數(shù)據(jù)結(jié)構(gòu)二叉樹的序列化：按某種遍歷方案訪問所有結(jié)點并依次輸出結(jié)點數(shù)據(jù)，由此形成結(jié)點的線性序列

二叉樹的反序列化：根據(jù)線性序列重構(gòu)原始的二叉樹問題：序列化的作用：將樹的非線性結(jié)構(gòu)轉(zhuǎn)換成線性結(jié)構(gòu)，便于使用線性表或字符串等存儲完全二叉樹的順序存儲是一種序列化方案，并且可以根據(jù)結(jié)點間的相對位置確定它們之間的邏輯關(guān)系，重構(gòu)出二叉樹但該方法對于一般的二叉樹可能造成空間浪費，在最壞情況下，空間復雜度達到O(2n)常用的前序遍歷或?qū)有虮闅v算法，產(chǎn)生的結(jié)點序列只包含了樹結(jié)構(gòu)的部分信息，通常無法重構(gòu)二叉樹5.4.4二叉樹的序列化與反序列化5.4二叉樹的遍歷數(shù)據(jù)結(jié)構(gòu)二叉樹的序列化：按某種遍歷方案訪問所有結(jié)點并依次輸出結(jié)點數(shù)據(jù)，由此形成結(jié)點的線性序列二叉樹的反序列化：根據(jù)線性序列重構(gòu)原始的二叉樹前序遍歷：<A,B,D,H,I,E,J,C,F,K>從序列中，最多只能確定A是根結(jié)點，其它信息，如左子樹包含哪些結(jié)點等無法確定問題：如何使前序遍歷的結(jié)果能夠重構(gòu)二叉樹？5.4.4二叉樹的序列化與反序列化5.4二叉樹的遍歷數(shù)據(jù)結(jié)構(gòu)二叉樹的序列化：按某種遍歷方案訪問所有結(jié)點并依次輸出結(jié)點數(shù)據(jù)，由此形成結(jié)點的線性序列二叉樹的反序列化：根據(jù)線性序列重構(gòu)原始的二叉樹序列化方法用特殊符號#表示空結(jié)點當在前序遍歷過程中遇到空結(jié)點或空子樹時，不是直接返回，而是輸出符號#，從而將空結(jié)點也標記在序列中前序序列5.4二叉樹的遍歷數(shù)據(jù)結(jié)構(gòu)二叉樹前序序列化：前序遍歷二叉樹，如果結(jié)點非空，輸出結(jié)點數(shù)據(jù)，否則輸出#<A,B,D,H,#,#,I,#,#,E,#,J,#,#,C,F,#,K,#,#,#>前序序列通過在結(jié)點序列中插入空記號，記錄二叉樹的非線性結(jié)構(gòu)算法5-11：二叉樹前序序列化PreOrderSerialize(tree

)5-4二叉樹的遍歷輸入：二叉樹tree輸出：二叉樹的前序序列

if

tree

=

NILthen//空樹|print

#//輸出特殊符號，代表空結(jié)點else|print

tree.data//輸出結(jié)點數(shù)據(jù)|PreOrderSerialize(tree.left)

//對左子樹前序序列化|PreOrderSerialize(tree.right)//對右子樹前序序列化end基于前序遍歷算法前序序列5.4二叉樹的遍歷數(shù)據(jù)結(jié)構(gòu)前序序列的反序列化<A,B,D,H,#,#,I,#,#,E,#,J,#,#,C,F,#,K,#,#,#>前序序列從前序序列先端依次讀取數(shù)據(jù)，執(zhí)行下面的操作：如果讀取的數(shù)據(jù)是#，則返回NIL，表示空結(jié)點或空樹否則新建二叉樹結(jié)點，把數(shù)據(jù)代入結(jié)點并遞歸地重構(gòu)結(jié)點的左子樹和右子樹，然后返回結(jié)點。算法5-12：二叉樹前序序列的反序列化PreOrderDeSerialize(preorder,

n)5-4二叉樹的遍歷

k←k+1

tree←NIL//初始化一個空樹

if

k<n

then//k是線性表的有效序號

|data←Get(preorder,k)//讀出線性表第k個元素

|if

data≠#

then//非空記號

||tree←newBinaryTreeNode()//新建二叉樹結(jié)點

||tree.data←data//代入數(shù)據(jù)

||tree.left←PreOrderDeSerialize(preorder,n)//重構(gòu)左子樹

||tree.right←PreOrderDeSerialize(preorder,n)//重構(gòu)右子樹

|end

end

return

tree//返回新建的二叉樹或空樹輸入：存放二叉樹前序序列的線性表preorder，表中元素個數(shù)n(n>0)輸出：二叉樹全局變量：k，初始值為-1二叉樹的序列化：按某種遍歷方案訪問所有結(jié)點并依次輸出結(jié)點數(shù)據(jù)，由此形成結(jié)點的線性序列二叉樹的反序列化：根據(jù)線性序列重構(gòu)原始的二叉樹思考：（1）與前序序列類似，在二叉樹的層序遍歷過程中，輸出表示空結(jié)點的標記，可生成二叉樹的層序序列，并根據(jù)層序序列重構(gòu)二叉樹（過程及算法參考教材）（2）（經(jīng)典問題）用前序遍歷與中序遍歷結(jié)果重構(gòu)二叉樹，分析重構(gòu)條件及算法的時間復雜度5.4.4二叉樹的序列化與反序列化5.4二叉樹的遍歷數(shù)據(jù)結(jié)構(gòu)前序遍歷：<A,B,D,H,I,E,J,C,F,K>中序遍歷：<H,D,I,B,E,J,A,F,K,C>5.5.1最優(yōu)二叉樹5.5哈夫曼樹數(shù)據(jù)結(jié)構(gòu)

帶有相同權(quán)重集{1,

2,

3,

4

,5}的三棵帶權(quán)二叉樹

WPL

=5.5.1最優(yōu)二叉樹5.5哈夫曼樹數(shù)據(jù)結(jié)構(gòu)帶權(quán)二叉樹：每個葉結(jié)點帶有一個權(quán)重值（正數(shù)）的二叉樹帶有相同權(quán)重集{1,

2,

3,

4

,5}的三棵帶權(quán)二叉樹

最小值最優(yōu)二叉樹：給定一組葉結(jié)點權(quán)重，由此構(gòu)建的所有帶權(quán)二叉樹中，帶權(quán)路徑長度最小的二叉樹，亦稱哈夫曼樹最優(yōu)二叉樹基本性質(zhì)5.5哈夫曼樹數(shù)據(jù)結(jié)構(gòu)定理5-4：最優(yōu)二叉樹（哈夫曼樹）是滿二叉樹證明：假設(shè)帶權(quán)二叉樹中存在度為1的中間結(jié)點。刪除度為1的中間結(jié)點并把其唯一的子結(jié)點與父結(jié)點直接相連，使得從樹根到該中間結(jié)點的所有子孫結(jié)點的路徑長度減1，能夠減小樹的帶權(quán)路徑長度。因此，最優(yōu)二叉樹不含度為1的中間結(jié)點。減小樹的帶權(quán)路徑長度，使其成為最優(yōu)二叉樹刪除度為1的中間結(jié)點命題5-5：最優(yōu)二叉樹中，如果兩個葉結(jié)點的權(quán)重值不同，則權(quán)重值小的葉結(jié)點在樹中的層數(shù)大于等于權(quán)重值大的葉結(jié)點最優(yōu)二叉樹基本性質(zhì)5.5哈夫曼樹數(shù)據(jù)結(jié)構(gòu)

交換權(quán)重值相同或者在樹中同一層上的兩個葉結(jié)點，不會改變二叉樹的帶權(quán)路徑長度命題5-6：給定一組葉結(jié)點權(quán)重，存在最優(yōu)二叉樹，權(quán)重最小和次小的葉結(jié)點在樹的最下層并且互為兄弟結(jié)點。最優(yōu)二叉樹基本性質(zhì)5.5哈夫曼樹數(shù)據(jù)結(jié)構(gòu)證明：最優(yōu)二叉樹是滿樹，因此最下層必有兩個以上的葉結(jié)點如果權(quán)重最小的葉結(jié)點不在最下層，則最下層所有結(jié)點的權(quán)重都必須等于最小值，因此可以通過交換把權(quán)重最小的葉結(jié)點移到最優(yōu)二叉樹的最下層同理可證權(quán)重次小的葉結(jié)點也在最下層在最下層權(quán)重最小葉結(jié)點必有兄弟結(jié)點（滿二叉樹）。如果權(quán)重最小結(jié)點和次小結(jié)點不是兄弟，可以把最小結(jié)點的兄弟與次小結(jié)點交換，使兩個結(jié)點共有一個父結(jié)點中間結(jié)點的權(quán)重：除了葉結(jié)點帶有權(quán)重，帶權(quán)二叉樹各中間結(jié)點也可定義權(quán)重，等于它的左子結(jié)點和右子結(jié)點的權(quán)重之和哈夫曼算法：一種至下而上構(gòu)建最優(yōu)二叉樹的方法，通過不斷合并兩個帶權(quán)二叉樹，最終生成最優(yōu)二叉樹，具體過程如下：哈夫曼算法5.5哈夫曼樹數(shù)據(jù)結(jié)構(gòu)對于給定的一組權(quán)重w1,w2,…,wn(n≥2)，首先創(chuàng)建n個只有一個結(jié)點（葉結(jié)點）的二叉樹T={T1,T2,…,Tn}，其中Tj

的根結(jié)點權(quán)重為wj(1≤j≤n)；創(chuàng)建新的結(jié)點，并從T中取出根結(jié)點權(quán)重最小和次小的兩個二叉樹，分別作為新結(jié)點的左右子樹，設(shè)置結(jié)點的權(quán)重為左右子樹的根結(jié)點權(quán)重之和；把(2)構(gòu)成的新二叉樹插入二叉樹集T中；重復(2)和(3)的操作，直到T中只剩一個二叉樹。最后剩下的二叉樹就是所要構(gòu)建的哈夫曼樹。哈夫曼算法：一種至下而上構(gòu)建最優(yōu)二叉樹的方法，通過不斷合并兩個帶權(quán)二叉樹，最終生成最優(yōu)二叉樹哈夫曼算法5.5哈夫曼樹數(shù)據(jù)結(jié)構(gòu)首先創(chuàng)建5棵單根樹最優(yōu)二叉樹的構(gòu)建過程每次合并左端根權(quán)重最小和次小的兩棵樹哈夫曼樹算法5-15：創(chuàng)建哈夫曼樹CreateHuffmanTree(w

)5-4二叉樹的遍歷

輸入：權(quán)重值的數(shù)據(jù)集w，|w|≥2

輸出：哈夫曼樹時間TW_Extract時間TQ_Insert算法5-15：創(chuàng)建哈夫曼樹CreateHuffmanTree(w

)5-4二叉樹的遍歷

|

for

i←1to

n-1do//合并二叉樹，共n-1次

|tree←newBinaryTreeNode()//新建樹根結(jié)點

|tree.left←ExtractMin(tree_set)//取出根權(quán)重最小樹作為左子樹

|tree.right←ExtractMin(tree_set)//取出根權(quán)重次小樹作為右子樹

|tree.weight←tree.left.weight+tree.right.weight//設(shè)置新樹的根權(quán)重

|Insert(tree_set,tree)

//將新樹插入集合tree_set

end

tree←Extract(tree_set)

//取出集合中唯一的二叉樹，即哈夫曼樹

return

tree

時間TQ_ExtractMin時間TQ_ExtractMin時間TQ_Insert時間TQ_Extract哈夫曼算法：一種至下而上構(gòu)建最優(yōu)二叉樹的方法，通過不斷合并兩個帶權(quán)二叉樹，最終生成最優(yōu)二叉樹算法分析：哈夫曼算法5.5哈夫曼樹數(shù)據(jù)結(jié)構(gòu)用n個權(quán)重值創(chuàng)建了n個單根二叉樹，并依次放入集合tree_set中，時間復雜度為O(n)*(TQ_Insert

+

TW_Extract)合并兩個二叉樹的時間是2TQ_ExtractMin

+

TQ_Insert算法的時間復雜度等于O(n)*TQ_Insert

+

O(n)*TQ_ExtractMin

+

O(n)*TW_Extract假設(shè)數(shù)據(jù)集w和tree_set直接用線性表實現(xiàn)，TQ_Insert和TW_Extract都是O(1)，但TQ_ExtractMin=O(n)，即在tree_set中順序查找權(quán)重最小二叉樹的時間，因此構(gòu)建哈夫曼樹的時間復雜度達到O(n2)更高效的構(gòu)建方案是使用比線性表更復雜的數(shù)據(jù)結(jié)構(gòu)，比如堆，這將在第6章中介紹。問題：如何傳輸由字母a、b、c、w、z組成的字符串“baaacabwbzc”？

關(guān)鍵：需要將文字符串轉(zhuǎn)換成計算機能夠識別處理的二進制字符串（編碼）定長碼：把每個字母轉(zhuǎn)換成固定長度的二進制字符串不定長碼：使用頻率高的字母采用短編碼，頻率小的采用長編碼哈夫曼編碼5.5哈夫曼樹數(shù)據(jù)結(jié)構(gòu)定長碼：a–000,

b–001,

c–010,

w–011,

z–100

baaacabwbzc001000000000010000001011001100010不定長碼：a–01,

b–00,

c–10,

w–110,

z–111

baaacabwbzc000101011001001100011110

編碼長度33長度24頻率：a(4),

b(3),

c(2),

w(1),

z(1)不定長碼比定長碼的編碼效率高！編碼前綴碼：一種常用的不定長碼，每個字母的編碼都不是其它字母編碼的前綴

哈夫曼編碼5.5哈夫曼樹數(shù)據(jù)結(jié)構(gòu)a–01,

b–00,

c–10,

w–110,

z–111

a–1,

b–00,

c–10,

w–110,

z–111

前綴碼非前綴碼對二進制字符串解碼會出現(xiàn)歧義例：”1101”

“wa”

“1101”

“aca”可用二叉樹表示前綴碼前綴碼：常用的不定長碼，每個字母的編碼都不是其它字母編碼的前綴

哈夫曼編碼5.5哈夫曼樹數(shù)據(jù)結(jié)構(gòu)a–01,

b–00,

c–10,

w–110,

z–111

前綴碼前綴碼樹各結(jié)點的左分支對應(yīng)0，右分支對應(yīng)1每個葉結(jié)點記錄唯一的一個字母從根到各葉結(jié)點經(jīng)過的分支序列表示對應(yīng)字母的編碼，同時編碼長度等于路徑長度各葉節(jié)點中的數(shù)值表示權(quán)重，等于對應(yīng)字母在字符串“baaacabwbzc”中出現(xiàn)的次數(shù)（頻率）字符串“baaacabwbzc”的編碼長度前綴碼樹的帶權(quán)路徑長度WPL前綴碼：常用的不定長碼，每個字母的編碼都不是其它字母編碼的前綴問題：給定一個字符串，求最優(yōu)前綴碼，使編碼出的二進制字符串長度最短

哈夫曼編碼5.5哈夫曼樹數(shù)據(jù)結(jié)構(gòu)字符串的編碼長度前綴碼樹的帶權(quán)路徑長度WPL最優(yōu)前綴碼可用哈夫曼算法求解，并把求得的前綴碼稱為哈夫曼編碼對應(yīng)權(quán)重集{3,4,2,1,1}的哈夫曼樹a–01,

b–00,

c–10,

w–110,

z–111

是字符串“baaacabwbzc”的哈夫曼編碼算法5-16：使用哈夫曼樹對二進制字符串解碼Decoding(tree,binary_code)

5-5哈夫曼樹

p←tree

//指向樹根n←Length(binary_code)//二進制字符串長度for

i←0to

n-1do|if

binary_code[i]=0then||p←p.left//遇到0,沿左分支下移|else//binary_code[i]=1||p←p.right//遇到1,沿右分支下移|end|if

p.left=NIL且p.right=NILthen//到達葉結(jié)點||print

p.data//輸出文字符||p←tree//返回樹根，重新開始解碼|endend輸入：非空前綴碼樹tree，二進制字符串binary_code輸出：解碼后的文字符序列算法分析對長度為n的二進制字符串，使用哈夫曼（前綴碼）樹只需要O(n)

的時間就能解碼生成原來的文字串

5.6.1樹的存儲結(jié)構(gòu)5.6樹與森林數(shù)據(jù)結(jié)構(gòu)與二叉樹相似，樹也有順序存儲與鏈接存儲兩種方式，而選擇何種方式與在樹結(jié)點中記錄哪些表示樹邏輯結(jié)構(gòu)的信息相關(guān)常用的樹邏輯結(jié)構(gòu)表示法：父親表示法、孩子表示法以及孩子兄弟表示法父親表示法5.6樹與森林數(shù)據(jù)結(jié)構(gòu)父親表示法要求每個結(jié)點保存父結(jié)點的位置信息，也可稱為父結(jié)點表示法適合用順序表來存儲樹的所有結(jié)點對所有結(jié)點從0開始連續(xù)編號

結(jié)點數(shù)據(jù)包含兩個域，一個是數(shù)據(jù)域tree[i].data記錄樹結(jié)點的數(shù)據(jù)元素，另一個域tree[i].parent存放父結(jié)點位置可用順序表存儲樹根結(jié)點的父結(jié)點位置域是-1算法5-17：查找父親表示法的樹的根結(jié)點FindRoot(tree,

x)

5-6樹與森林

while

tree[??].????????????≠?1do

//結(jié)點??有父結(jié)點，非根|??←tree[??].parent//??移動至父結(jié)點endreturn??輸入：父親表示法的樹（順序表）tree，結(jié)點（索引）??輸出：樹tree的根結(jié)點索引時間復雜度O(H),

H表示樹的高度父親表示法方便每個結(jié)點查找其祖先結(jié)點，而且每個結(jié)點只需存放父結(jié)點位置，可節(jié)省存儲空間父親表示法可用于實現(xiàn)并查集（不相交集）如果是查找結(jié)點的所有子結(jié)點或兄弟結(jié)點，父親表示法需要對整個樹進行遍歷，時間效率低

孩子表示法5.6樹與森林數(shù)據(jù)結(jié)構(gòu)與父親表示法一樣，用順序表存儲樹，每個結(jié)點包含數(shù)據(jù)域，父結(jié)點位置域，以及子結(jié)點鏈表域，用來存放指向單鏈表的指針鏈表中各子結(jié)點按從左向右的順序排列孩子表示法5.6樹與森林數(shù)據(jù)結(jié)構(gòu)與父親表示法一樣，用順序表存儲樹，每個結(jié)點包含數(shù)據(jù)域，父結(jié)點位置域，以及子結(jié)點鏈表域，用來存放指向單鏈表的指針第一個孩子：各結(jié)點在樹中最左邊的子結(jié)點下一個兄弟：各結(jié)點右側(cè)并且相鄰的兄弟結(jié)點結(jié)點B的第一個孩子:

E，下一個兄弟：C各結(jié)點的第一個孩子就是其子結(jié)點鏈表的第一個結(jié)點，查找時間O(1)各結(jié)點的下一個兄弟需要遍歷其父結(jié)點的子結(jié)點鏈表，時間復雜度O(d),

d是樹的度孩子兄弟表示法5.6樹與森林數(shù)據(jù)結(jié)構(gòu)樹應(yīng)用最廣泛的存儲結(jié)構(gòu)。每個結(jié)點存放其第一個孩子和下一個兄弟的信息，可以直接使用二叉鏈表實現(xiàn)，因此這種表示法也稱作二叉鏈表表示法二叉鏈表中的指針域left

改稱first_child，指向結(jié)點的第一個子結(jié)點；同時，指針域right

改稱next_sibling，指向右側(cè)的兄弟結(jié)點二叉鏈表結(jié)構(gòu)5.6.2樹、森林與二叉樹的轉(zhuǎn)換5.6樹與森林數(shù)據(jù)結(jié)構(gòu)鏈接存儲結(jié)構(gòu)根結(jié)點無右子結(jié)點根結(jié)點無兄弟結(jié)點樹與二叉樹的轉(zhuǎn)換對任何一個樹，存在唯一的一個二叉樹與它對應(yīng)，兩者具有相同的二叉鏈表結(jié)構(gòu)二叉樹樹孩子兄弟表示法二叉鏈表結(jié)構(gòu)算法5-18：查找樹中帶有指定數(shù)據(jù)的結(jié)點Search(tree,

x)

5-6樹與森林

node_ptr←treeif

node_ptr≠NILthen|if

node_ptr.data≠??then||node_ptr←Search(tree.first_child,??)//在子孫結(jié)點中查找||if

node_ptr=NILthen

//不在子孫結(jié)點中|||node_ptr←Search(tree.next_sibling,??)//在兄弟結(jié)點及其子孫中找||end|endendreturn

node_ptr輸入：基于孩子兄弟表示法的tree，結(jié)點元素??輸出：如果樹中有數(shù)據(jù)域等于??的結(jié)點，返回該結(jié)點；否則，返回NIL時間復雜度O(n),

n是樹中結(jié)點數(shù)目采用二叉樹的前序遍歷算法森林與二叉樹的轉(zhuǎn)換5.6樹與森林數(shù)據(jù)結(jié)構(gòu)對于每一棵獨立的樹，由于根結(jié)點沒有兄弟，它對應(yīng)的二叉樹的根沒有右子結(jié)點，即右子樹為空利用右子樹的鏈將樹串聯(lián)起來，建立森林與二叉樹的對應(yīng)關(guān)系森林轉(zhuǎn)換成二叉樹把森林中的每個樹轉(zhuǎn)換為二叉樹把森林中第一個二叉樹的根結(jié)點作為轉(zhuǎn)換后的二叉樹的根，從第二個二叉樹開始，把每個二叉樹的根作為前一個二叉樹的根的右子結(jié)點三棵獨立的樹對應(yīng)每棵樹的二叉樹對應(yīng)森林的二叉樹5.6.3樹與森林的遍歷5.6樹與森林數(shù)據(jù)結(jié)構(gòu)樹的遍歷方案：前序遍歷、后序遍歷（無中序遍歷?。┣靶虮闅v：先訪問樹根，然后對根的各子樹從左向右依次進行前序遍歷后序遍歷：遍歷根的各子樹，最后訪問根結(jié)點前序遍歷：<A,B,E,F,K,L,G,C,H,D,I,J,M>后序遍歷：<E,K,L,F,G,B,H,C,I,M,J,D,A>樹與對應(yīng)的二叉樹的遍歷5.6樹與森林數(shù)據(jù)結(jié)構(gòu)<A,B,E,F,K,L,G,C,H,D,I,J,M><E,K,L,F,G,B,H,C,I,M,J,D,A><A,B,E,F,K,L,G,C,H,D,I,J,M><E,K,L,F,G,B,H,C,I,M,J,D,A>對應(yīng)前序前序后序中序樹的前序遍歷與對應(yīng)的二叉樹的前序遍歷結(jié)果相同樹的后序遍歷與對應(yīng)的二叉樹的中序遍歷結(jié)果相同基于二叉樹遍歷方案的樹遍歷算法5-6樹與森林算法5-19.前序遍歷樹PreOrder(tree)輸入：基于孩子兄弟表示法存儲的樹tree

（二叉鏈表結(jié)構(gòu)）輸出：按前序遍歷的順序依次訪問各結(jié)點if

tree

≠

NILthen//空樹不做處理，直接返回|Visit(tree)

//先訪問根結(jié)點|PreOrder(tree.first_child)

//接下來訪問tree所有子孫結(jié)點|PreOrder(tree.next_sibling)//最后訪問tree后序的兄弟結(jié)點及其子孫end算法5-20.后序遍歷樹PostOrder(tree)輸入：基于孩子兄弟表示法存儲的樹tree

（二叉鏈表結(jié)構(gòu)）輸出：按后序遍歷的順序依次訪問各結(jié)點if

tree

≠

NILthen//空樹不做處理，直接返回|PostOrder(tree.first_child)

//先訪問tree所有子孫結(jié)點|

Visit(tree)

//接下來訪問根結(jié)點|PostOrder(tree.next_sibling)//最后訪問tree后序的兄弟結(jié)點及其子孫end二叉樹的中序遍歷算法二叉樹的前序遍歷算法森林的遍歷5.6樹與森林數(shù)據(jù)結(jié)構(gòu)前序遍歷：從其中的第一個樹開始，按序?qū)γ總€樹進行前序遍歷后序遍歷：從其中的第一個樹開始，按序?qū)γ總€樹進行后序遍歷前序遍歷：<B,E,F,K,L,G,C,H,D,I,J,M>后序遍歷：<E,K,L,F,G,B,H,C,I,M,J,D>從左向右依次遍歷每棵樹！森林與對應(yīng)的二叉樹的遍歷5.6樹與森林數(shù)據(jù)結(jié)構(gòu)<B,E,F,K,L,G,C,H,D,I,J,M><E,K,L,F,G,B,H,C,I,M,J,D><E,K,L,F,G,B,H,C,I,M,J,D>對應(yīng)前序前序后序中序森林的前序遍歷與對應(yīng)的二叉樹的前序遍歷結(jié)果相同森林的后序遍歷與對應(yīng)的二叉樹的中序遍歷結(jié)果相同<B,E,F,K,L,G,C,H,D,I,J,M>算法5.19可用算法5.20可用5.6.2樹、森林與二叉樹的轉(zhuǎn)換5.6樹與森林數(shù)據(jù)結(jié)構(gòu)樹、森林與二叉樹的對應(yīng)關(guān)系表明可以把樹或森林先轉(zhuǎn)換為二叉樹，使用二叉樹的各種操作進行處理，處理結(jié)束后還可以再轉(zhuǎn)換回原來的樹或森林樹或森林二叉樹轉(zhuǎn)換轉(zhuǎn)換執(zhí)行各種操作：比如，遍歷、序列化與反序列化、樹的合并與拆分、數(shù)據(jù)查找等5.7.1拓展延伸：前綴樹5