第6章樹與二叉樹第6章樹與二叉樹校長一系二系三系六系教務處科研處總務處601602教務科603ABCD…………張三李四王五…例1…工廠校長一二三六教科總601602教603ABCD…………張李王(根目錄)

\f1f2f3fnd1d2dm………例2f11f12f1kd11d12…………(根目錄)f1f2f3fnd1d2dm………例2f11f12例3例31樹的基本概念2樹的存儲結構3二叉樹4二叉樹的存儲結構5二叉樹的遍歷6線索二叉樹1樹的基本概念2樹的存儲結構3二叉樹4二叉樹

6.1

樹的基本概念

樹是由n0個結點組成的有窮集合(不妨用D表示)以及結點之間關系組成的集合構成的結構。當n=0時，稱該樹為空樹；在任何一棵非空的樹中，有一個特殊的結點tD，稱之為該樹的根結點；其余結點D–{t}被分割成m>0個不相交的子集D1,D2,…,Dm,其中每一個子集Di又為一棵樹，分別稱之為t的子樹。遞歸定義一.樹的定義6.1樹的基本概念樹是由n0個結點JIHGFEACXBA的第1棵子樹A的第3棵子樹A的第2棵子樹二.樹(邏輯上)的特點1.有且僅有一個結點沒有前驅結點,該結點為樹的根結點。2.除了根結點外,每個結點有且僅有一個直接前驅結點。3.包括根結點在內，每個結點可以有多個后繼結點。JIHGFEACXBA的第1棵子樹A的第3棵子樹A的第2棵子JIHGFEACXB4.

樹形表示法

借助自然界中一棵倒置的樹的形狀來表示數據元素之間層次關系的方法。JIHGFEACXB4.樹形表示法借1.

結點的度：2.

樹的度：3.

葉結點：4.

分支結點:5.

層次的定義:JIHGFEACXB該結點擁有的子樹的數目。樹中結點度的最大值。度為0的結點.度非0的結點.

根結點為第一層,若某結點在第i層,

則其孩子結點(若存在)為第i+1層.四.基本名詞術語第1層第2層第3層1.結點的度：3.葉結點：5.層次的定義:JIHGFE7.

樹林(森林):m0棵不相交的樹組成的樹的集合.8.

樹的有序性:6.

樹的深度:樹中結點所處的最大層次數.

若樹中結點的子樹的相對位置不能隨意改變,則稱該樹為有序樹，否則稱該樹為無序樹。JIHGFEACXB深度為3的樹7.樹林(森林):m0棵不相交的樹組成的樹的集合.8二叉樹的基本形態：(空)根根左子樹根右子樹根左子樹右子樹

6.2

二叉樹二叉樹的基本形態：(空)根根左根右根左右6.2二叉樹二.兩種特殊形態的二叉樹

若一棵二叉樹中的結點,或者為葉結點，或者具有兩棵非空子樹,并且葉結點都集中在二叉樹的最下面一層.這樣的二叉樹為滿二叉樹.1.滿二叉樹

若一棵二叉樹中只有最下面兩層的結點的度可以小于2,并且最下面一層的結點(葉結點)都依次排列在該層從左至右的位置上。這樣的二叉樹為完全二叉樹.2.完全二叉樹二.兩種特殊形態的二叉樹若一棵二叉樹中的1.一棵非空二叉樹的第i層最多有2i–1個結點(i1)。三.二叉樹的性質2.

深度為h的非空二叉樹最多有2h-1個結點.3.

若非空二叉樹有n0個葉結點,有n2個度為2的結點,

則n0=n2+1

4.

具有n個結點的完全二叉樹的深度h=

log2n

+1.1.一棵非空二叉樹的第i層最多有2i–1個結點(i1)

二叉樹的存儲結構一.二叉樹的順序存儲結構12345678910ABCDEFGHIJBT[1:15]123456789101112131415ABCDEFGHIJ

根據完全二叉樹的性質

,對于深度為h的完全二叉樹,將樹中所有結點的數據信息按照編號的順序依次存儲到一維數組BT[1:2h-1]中,由于編號與數組的下標一一對應,該數組就是該完全二叉樹的順序存儲結構.1.完全二叉樹的順序存儲結構二叉樹的存儲結構一.二叉樹的順序存儲結構1234567812345678910ABCDEFGHIJ111213BT[1:15]123456789101112131415ABCDEFGHJ

IABCDEFGHIJ2.一般二叉樹的順序存儲結構12345678910ABCDEFGHIJ111213BT[

對于一般二叉樹,只須在二叉樹中“添加”一些實際上二叉樹中并不存在的“虛結點”

(可以認為這些結點的數據信息為空),使其在形式上成為一棵“完全二叉樹”,然后按照完全二叉樹的順序存儲結構的構造方法將所有結點的數據信息依次存放于數組BT[1:2h-1]中。對于一般二叉樹,只須在二叉樹中“添加”一些實際上二.二叉樹的鏈式存儲結構(二叉鏈表)鏈結點的構造為lchilddatarchild

其中,data為數據域

lchild

與rchild分別為指向左、右子樹的指針域.ABCDEFGIJABCDEFGJIT^^^^^^^^^^二.二叉樹的鏈式存儲結構(二叉鏈表)鏈結點的構造為lchil6.3.3

二叉樹的遍歷6.3.3二叉樹的遍歷二.前序遍歷二.前序遍歷三.中序遍歷三.中序遍歷四.后序遍歷四.后序遍歷ABCDKFGIJEH前序遍歷序列:

A,B,D,K,J,G,C,F,I,E,H中序遍歷序列:

D,B,G,J,K,A,F,I,E,C,H后序遍歷序列:

D,G,J,K,B,E,I,F,H,C,A按層次遍歷序列:

A,B,C,D,K,F,H,J,I,G,E例ABCDKFGIJEH前序遍歷序列:中序遍歷序列:后序遍歷序6.3.2線索二叉樹1.何謂線索二叉樹？遍歷結果是求得結點的一個線性序列。指向該線性序列“前驅”和“后繼”的指針，稱“線索”；包含“線索”的存儲結構，稱為“線索鏈表”；與其相應的二叉樹，稱為“線索二叉樹”；對二叉樹以某種次序遍歷，使其變為線索二叉樹的過程，稱為“線索化”。6.3.2線索二叉樹1.何謂線索二叉樹？2.線索鏈表中結點的結構在二叉鏈表的結點結構中增加兩個標志域，并規定：lchildLTagdataRTagrchild其中：LTag=0lchild域指示結點的左孩子1lchild域指示結點的前驅RTag=0rchild域指示結點的右孩子1rchild域指示結點的后繼2.線索鏈表中結點的結構在二叉鏈表的結點結構中增加兩個標志域二叉樹二叉線索存儲表示typedefenum{Link,Thread}PointerThr;

//Link==0:指針，Thread==1:線索typedefstructBiThrNode{TElemTypedata;StructBiThrNode*lchild,*rchild;

//左右孩子指針

PointerThrLTag,RTag;//左右標志}BiThrNode,*BiThrTree;二叉樹二叉線索存儲表示typedefenum{Link3.線索二叉樹圖例

線索二叉樹及其存儲結構（a）中序線索二叉樹（b）中序線索鏈表1234567010020131141050161171thrt0

13.線索二叉樹圖例線索二叉樹及其存儲結構1234567如何在線索樹中找結點的后繼？結合中序線索樹若其右標志為“1”，右鏈是線索，右鏈直接指示了結點的后繼；若其右標志為“0”，右鏈是指針，其后繼為右子樹中最左下的結點。1234567如何在線索樹中找結點的后繼？結合中序線索樹1234567如何在線索樹中找結點的前驅？結合中序線索樹

若其左標志為“1”，左鏈為線索，直接指示其前驅；若其左標志為“0”，左子樹中最右下的結點為其前驅。1234567如何在線索樹中找結點的前驅？結合中序線索樹1234567線索鏈表的中序遍歷算法StatusIOTraver_T(BiThrTreeT,Status(*Visit)(TElemTypee)){//T指向頭結點，頭結點的左鏈lchild指向根結點，中序遍歷

//二叉線索樹T的非遞歸算法，對每個數據元素調用函數Visit。

p=T->lchild;//p指向根結點

while(p!=T){//空樹或遍歷結束時，p==Twhile(p->LTag==Link)p=p->lchild;if(!Visit(p->data))returnERROR;//訪問其左子樹為空的結點

while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;Visit(p->data);}//訪問后繼結點

p=p->rchild;}returnOK;}//IOTraver_T010020131141050161171T011線索鏈表的中序遍歷算法010020131146.4.2森林和二叉樹的轉換1.樹和二叉樹的對應關系由于二叉樹和樹都可用二叉鏈表作為存儲結構，則以二叉鏈表作為媒介可導出樹與二叉樹之間的一個對應關系。6.4.2森林和二叉樹的轉換1.樹和二叉樹的對應關系數據結構二叉樹ppt課件樹轉換為二叉樹方法：1）對每個孩子進行從左到右的排序；2）在兄弟之間加一條連線；3）對每個結點，除了左孩子外，去除其與其余孩子之間的聯系；4）以根結點為軸心，將整個樹順時針轉45°。樹轉換為二叉樹方法：1）對每個孩子進行從左到右的排序；ABCDEGHFIaABCDEGHFIbABCDEGHFIcABCDEGHFIdABCDEGHFIaABCDEGHFIbABCDEGHFIc2.森林和二叉樹的對應關系從樹的二叉鏈表表示的定義可知，任何一棵和樹對應的二叉樹，其右子樹必空。若把森林中第二棵樹的根結點看成是第一棵樹的根結點的兄弟，則同樣可導出森林和二叉樹的對應關系。2.森林和二叉樹的對應關系數據結構二叉樹ppt課件BCDEGHFIaBCDEGHFIbBCDEGHFIcBCDEGHFIdBCDEGHFIaBCDEGHFIbBCDEGHFIcBCD已知條件：森林和二叉樹的對應關系設森林F=(T1,T2,…,Tn);T1=(root，t11,t12,…,t1m);

二叉樹B=(LBT,Node(root),RBT);由森林轉換成二叉樹的轉換規則為:若F=Φ，則B=Φ;否則，由Root(T1)對應得到Node(root);

由(t11,t12,…,t1m)對應得到LBT;

由(T2,T3,…,Tn)對應得到RBT。由二叉樹轉換為森林的轉換規則為:若B=Φ,則F=Φ;否則，由Node(root)對應得到Root(T1);

由LBT對應得到(t11,t12,…，t1m);T1除根以外所構成的森林由RBT對應得到(T2,T3,…,Tn)；除T1之外的森林已知條件：森林和二叉樹的對應關系設6.4.3樹和森林的遍歷1.樹的遍歷：有三條搜索路徑先根(序)遍歷：若樹不空，則先訪問根結點，然后依次先根遍歷各棵子樹。后根(序)遍歷：若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結點。按層次遍歷：若樹不空，則自上而下自左至右訪問樹中每個結點。6.4.3樹和森林的遍歷1