《數(shù)據(jù)結(jié)構(gòu)（C語言描述）（第2版）》教學(xué)課件4-08二叉鏈表的建立

1、2016數(shù)據(jù)結(jié)構(gòu)Data structure二叉鏈表的建立0.8講授：劉斌二叉鏈表的建立常州信息職業(yè)技術(shù)學(xué)院02三、鏈表的插入03二叉鏈表的建立0.8BCDEFGHAABCGHDEFroot教學(xué)目標(biāo)12基于先序和中序遍歷序列建立二叉鏈表04基于帶虛結(jié)點(diǎn)先序遍歷序列建立二叉鏈表三、鏈表的插入04二叉鏈表的建立0.8二叉鏈表的建立已知二叉樹的先序（或后序）遍歷序列和中序遍歷序列已知二叉樹的帶虛結(jié)點(diǎn)的先序（或后序）遍歷序列可以唯一確定一顆二叉樹。05二叉鏈表的建立0.81基于先序和中序遍歷序列建立二叉鏈表（1）算法思路 設(shè)T為指向二叉樹根指針的指針，分別用字符指針PRO和INO指向二叉樹的先序序列和

2、中序序列，n為二叉樹結(jié)點(diǎn)的個(gè)數(shù)，它們作為建立二叉鏈表函數(shù)的參數(shù)。 如果當(dāng)前結(jié)點(diǎn)數(shù)n為0，則將當(dāng)前根指針置為NULL，即建立一棵空子樹；中序遍歷序列為：D G B H E A F C先序遍歷序列為：A B D G E H C F05二叉鏈表的建立0.81基于先序和中序遍歷序列建立二叉鏈表（1）算法思路 如果當(dāng)前結(jié)點(diǎn)數(shù)n大于0，先建立根結(jié)點(diǎn)，再查找當(dāng)前根在中序序列INO中的位置m，確定當(dāng)前根左子樹先序序列的起始元素PRO1，中序序列的起始元素INO0，右子樹先序序列的起始元素PROm+1，中序序列的起始元素INOm+1； 最后分別建立當(dāng)前根的左子樹和右子樹。中序遍歷序列為：D G B H E A

3、F C先序遍歷序列為：A B D G E H C F06二叉鏈表的建立0.8（2）具體算法void CreateBinTreePI(BinTree *T,char *PRO,char *INO,int n)/基于先序和中序建立二叉鏈表int m=0; /記錄根結(jié)點(diǎn)在中序序列中的位置if(n=0)*T=NULL;else*T=(BinTNode*)malloc(sizeof(BinTNode);/生成根結(jié)點(diǎn)，確定實(shí)參指針的指向(*T)-data=PRO0; while(INOm!=PRO0)/查找根結(jié)點(diǎn)在中序序列的下標(biāo)m+;CreateBinTreePI(&(*T)-lchild,PRO+1,I

4、NO,m);/建立左子樹 CreateBinTreePI(&(*T)-rchild,PRO+m+1,INO+m+1,n-m-1);/建立右子樹中序遍歷序列為：D G B H E A F C先序遍歷序列為：A B D G E H C F07二叉鏈表的建立0.82基于帶虛結(jié)點(diǎn)先序遍歷序列建立二叉鏈表（1）算法思路 設(shè)T為指向二叉樹根指針的指針，作為建立二叉鏈表函數(shù)的參數(shù)，用外部字符指針PRO指向二叉樹帶虛結(jié)點(diǎn)先序序列。 如果PRO當(dāng)前指向的字符是虛結(jié)點(diǎn)，則將當(dāng)前根指針置為NULL，即建立一棵空子樹；如果PRO當(dāng)前指向的字符不是虛結(jié)點(diǎn)，先建立根結(jié)點(diǎn)，再分別建立當(dāng)前根的左子樹和右子樹。帶虛結(jié)點(diǎn)的先序遍歷為：ABDGEHC F08二叉鏈表的建立0.8（2）具體算法void CreateBinTreeP(BinTree *T)/基于帶虛結(jié)點(diǎn)先序序列建立二叉鏈表if(*PRO=)*T=NULL;PRO+;else *T=(BinTNode *)malloc(sizeof(BinTNode);/生成根結(jié)點(diǎn)，確定實(shí)參指針的指向(*T)-data=*PRO+;CreateBinTreeP(&(*T)-lchild);/建