二叉樹遍歷及其算法主講人:程玉勝2008.06.17《數(shù)據(jù)結(jié)構(gòu)》申報精品課程錄像1/39內(nèi)容提要

復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展遍歷非遞歸算法

復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展遍歷非遞歸算法2/39復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展遍歷非遞歸算法復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展遍歷非遞歸算法內(nèi)容提要3/39(一)

二叉樹的定義度不大于2，且子樹有左右之分，不能顛倒二叉樹的5種基本形態(tài)DDLDLRDR(a)(b)(c)(d)(e)復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展遍歷非遞歸算法4/39(一)

二叉樹性質(zhì)應(yīng)用(1)如果一棵二叉樹有10個葉子結(jié)點，有8個結(jié)點僅有左孩子，12個結(jié)點僅有右孩子，問該二叉樹有多少個結(jié)點？復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展遍歷非遞歸算法思考解易知：n=n0+n1+n2已知：n0＝10，n1＝8＋12＝20P124，性質(zhì)3知：n2＝n0-1=9所以，n=10＋20＋9＝395/39(一)

二叉樹性質(zhì)應(yīng)用(2）已知完全二叉樹有100個結(jié)點，則該二叉樹有多少個葉子結(jié)點？復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展遍歷非遞歸算法思考解1P124，性質(zhì)4知：樹的深度1＋log2100＝7P124，性質(zhì)2知：上面6層結(jié)點數(shù)26-1=63所以，第7層有100－63＝37個葉子它們是第6層中19個結(jié)點的孩子，因此第6層中沒有孩子的結(jié)點是32－19＝13所以，葉子結(jié)點數(shù)37＋13＝50第6層26-1=326/39(一)

二叉樹性質(zhì)應(yīng)用(2）已知完全二叉樹有100個結(jié)點，則該二叉樹有多少個葉子結(jié)點？復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展遍歷非遞歸算法思考解2P124，性質(zhì)5知：編號100的結(jié)點父親是100/2=50因此從51～100是葉子結(jié)點所以，葉子結(jié)點數(shù)100－50＝50i2i+12ii/27/39內(nèi)容提要

復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展遍歷非遞歸算法復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展遍歷非遞歸算法8/39

復(fù)習(xí)

二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展遍歷非遞歸算法

復(fù)習(xí)

二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展遍歷非遞歸算法內(nèi)容提要9/39(二)

二叉樹存儲結(jié)構(gòu)(1)

復(fù)習(xí)

二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展遍歷非遞歸算法順序存儲結(jié)構(gòu)abcdabcd…二叉鏈表存儲結(jié)構(gòu)typedefchardatatypetypedef

struct

BiTNode{datatypedata;

struct

BiTNode*lchild,*rchild;//左右指針}10/39(二)

二叉樹存儲結(jié)構(gòu)(2)

復(fù)習(xí)

二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展遍歷非遞歸算法二叉鏈表存儲結(jié)構(gòu)a^b^c^^d^圖有多少個空指針？5在n個結(jié)點的二叉鏈表中，空(^)指針數(shù)有多少個？思考解n個結(jié)點,共有2n個指針其中,n-1個結(jié)點有父親（根除外）所以，2n-(n－1）=n+1n+111/39(二)

二叉樹遍歷方法

復(fù)習(xí)

二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展遍歷非遞歸算法遍歷二叉樹定義：指按照某種順序訪問二叉樹的每個結(jié)點一次且僅被“訪問”一次。常見“訪問”的方法：voidvisit(datatypee){printf(e);}//實際使用時，加上格式控制符DLR遍歷時，限定先左后右：

LDR；DLR；LRD12/39(二)

先序遍歷算法

復(fù)習(xí)

二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展遍歷非遞歸算法

先序(DLR)遍歷

(2)遍歷左子樹(L)(3)遍歷右子樹(R)

(1)訪問根結(jié)點(D)

voidPreOrder(struct

BiTNode*T){if(T!=NULL)

visit(T->data);

PreOrder(T->lchild);

PreOrder(T->rchild);}

13/39(二)

中序遍歷算法

復(fù)習(xí)

二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展遍歷非遞歸算法

中序(LDR)遍歷

(1)遍歷左子樹(L)(3)遍歷右子樹(R)

(2)訪問根結(jié)點(D)

voidInOrder(struct

BiTNode*T){if(T!=NULL)

InOrder(T->lchild);

visit(T->data);

InOrder(T->rchild);}

14/39(二)

后序遍歷算法

復(fù)習(xí)

二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展遍歷非遞歸算法

后序(LRD)遍歷

(1)遍歷左子樹(L)(2)遍歷右子樹(R)

(3)訪問根結(jié)點(D)

voidPostOrder(struct

BiTNode*T){if(T!=NULL)

PostOrder(T->lchild);

PostOrder(T->rchild);

visit(T->data);}

15/39內(nèi)容提要

復(fù)習(xí)

二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展遍歷非遞歸算法

復(fù)習(xí)

二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展遍歷非遞歸算法16/39

復(fù)習(xí)二叉樹遍歷及算法

遍歷序列求解遍歷算法的拓展遍歷非遞歸算法

復(fù)習(xí)二叉樹遍歷及算法

遍歷序列求解遍歷算法的拓展遍歷非遞歸算法內(nèi)容提要17/39(三)

由二叉樹求序列

復(fù)習(xí)二叉樹遍歷及算法

遍歷序列求解遍歷算法的拓展遍歷非遞歸算法給出右圖的遍歷結(jié)果序列例1abcefd中序遍歷：

(1)a

LR先序遍歷：abdcef后序遍歷：dbfeca

(2)

Lba

L

ca

LR結(jié)果：dbaefc18/39(三)

由序列求二叉樹(1)

復(fù)習(xí)二叉樹遍歷及算法

遍歷序列求解遍歷算法的拓展遍歷非遞歸算法已知先序和中序結(jié)果，構(gòu)造二叉樹先序：abcdefghij中序：cdbfeaihgj例2由先序結(jié)果，二叉樹根為a

acdbfeihgj解abgcdfejih19/39(三)

由序列求二叉樹(2)

復(fù)習(xí)二叉樹遍歷及算法

遍歷序列求解遍歷算法的拓展遍歷非遞歸算法先序和后序結(jié)果，能構(gòu)造唯一的二叉樹嗎？思考20/39(三)

算法實現(xiàn)

復(fù)習(xí)二叉樹遍歷及算法

遍歷序列求解遍歷算法的拓展遍歷非遞歸算法（1）建立二叉樹struct

BiTNode*CreateBiTree(void){charch;struct

BiTNode*T;ch=getchar();if(ch=='@')T=NULL;else{T=(struct

BiTNode*)malloc(sizeof(struct

BiTNode));T->data=ch;T->lchild=CreateBranchTree();T->rchild=CreateBranchTree();}returnT;}}

上機(jī)實現(xiàn)步驟：21/39(三)

算法實現(xiàn)

復(fù)習(xí)二叉樹遍歷及算法

遍歷序列求解遍歷算法的拓展遍歷非遞歸算法（2）主程序中調(diào)用main(){struct

BiTNode*head;printf("pleaseinputthenode\n:");head=CreateBranchTree();printf("\n

pre_Order:");pre_Order(head);

printf("\n

mid_Order:");mid_Order(head);

printf("\nlast_Order:");last_Order(head);

getch();}算法實現(xiàn)步驟：[程序演示]22/39內(nèi)容提要

復(fù)習(xí)二叉樹遍歷及算法

遍歷序列求解遍歷算法的拓展遍歷非遞歸算法

復(fù)習(xí)二叉樹遍歷及算法

遍歷序列求解遍歷算法的拓展遍歷非遞歸算法23/39

復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解

遍歷算法的拓展遍歷非遞歸算法

復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解

遍歷算法的拓展遍歷非遞歸算法內(nèi)容提要24/39

復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解

遍歷算法的拓展遍歷非遞歸算法(四)

拓展“訪問”(1)設(shè)計算法按先序次序輸出二叉樹T中所有葉子結(jié)點的值。例3

voidPreOrder(struct

BiTNode*T){if(T!=NULL)

visit(T->data);

PreOrder(T->lchild);

PreOrder(T->rchild);}

解相同：均為先序輸出不同：此題有條件輸出，葉子的條件是??If(T->lchild==NULL&&T->rchild==NULL)

visit(T->data);25/39

復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解

遍歷算法的拓展遍歷非遞歸算法(四)

拓展“訪問”(2)設(shè)計算法按后序次序輸出二叉樹T中前k個結(jié)點的值。例4解相同：均為后序輸出不同：此題有條件輸出，前k個結(jié)點的條件是??

n=n+1;If(n<=k)

visit(T->data);

voidPostOrder(struct

BiTNode*T){if(T!=NULL)

PostOrder(T->lchild);

PostOrder(T->rchild);

visit(T->data);}26/39

復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解

遍歷算法的拓展遍歷非遞歸算法(四)

遍歷算法拓展(1)設(shè)計算法求解給定二叉樹的高度。例5解(1)如果T為空，則高度為0；(2)否則，其高度是左右子樹中高度的最大值＋1int

PostTreeDepth(struct

BiTNode*bt){int

hl,hr,max;if(bt!=NULL){hl=PostTreeDepth(bt->LChild);hr=PostTreeDepth(bt->RChild);max=hl>hr?hl:hr;return(max+1);}elsereturn(0);}后序遍歷27/39

復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解

遍歷算法的拓展遍歷非遞歸算法(四)

遍歷算法拓展(2)設(shè)計算法按照先序次序依次輸出二叉樹結(jié)點值及其所在的層次。例6解先序遍歷的拓展如果知道當(dāng)前結(jié)點的層次，那么就知道其孩子結(jié)點的層次，因此，在先序遍歷算法中增加層次參數(shù)voidPrintTree(struct

BiTNode*bt,int

nLayer){if(bt==NULL)return;printf("(%c,%d)",bt->data,nLayer);PrintTree(bt->LChild,nLayer+1);PrintTree(bt->RChild,nLayer+1);}28/39

復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解

遍歷算法的拓展遍歷非遞歸算法(四)

遍歷算法綜合程序1、求二叉樹結(jié)點數(shù)2、求二叉樹葉子結(jié)點數(shù)思考[程序演示]綜合程序29/39內(nèi)容提要

復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解

遍歷算法的拓展遍歷非遞歸算法

復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解

遍歷算法的拓展遍歷非遞歸算法30/39

復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展

遍歷非遞歸算法

復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展

遍歷非遞歸算法內(nèi)容提要31/39(五)

中序遞歸過程回顧下圖的中序遍歷結(jié)果例7

復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展

遍歷非遞歸算法abcefd32/39(五)

中序遞歸過程mid()表示中序算法中序：dbaefc

mid(a)mid(b)amid(c)mid(d)mid(^)bmid(^)dmid(^)mid(e)cmid(^)mid(^)emid(f)fmid(^)mid(^)

復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展

遍歷非遞歸算法33/39

復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展

遍歷非遞歸算法(五)堆棧變化過程par0par0pbr1par0pbr1pdr1par0pbr1輸出d……34/39

復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展

遍歷非遞歸算法(五)非遞歸算法實現(xiàn)[程序演示]P129,動態(tài)創(chuàng)建35/39

復(fù)習(xí)二叉樹遍歷及算法遍歷序列求解遍歷算法的拓展