1、遍歷非遞歸算法1第1頁，共116頁，2022年，5月20日，19點55分，星期三2遞歸函數的主要優(yōu)點是可以把算法寫的比使用非遞歸函數時更清晰更簡潔，而且某些問題，特別是與人工智能有關的問題，更適宜用遞歸方法。遞歸的另一個優(yōu)點是，遞歸函數不會受到懷疑，較非遞歸函數而言，某些人更相信遞歸函數。第2頁，共116頁，2022年，5月20日，19點55分，星期三3以先序遍歷為例：void PreOrder (BiTree T) if (T) coutdata ;PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild); ABCDEFHG第3頁，共116頁

2、，2022年，5月20日，19點55分，星期三4ABCDEFHGBDGNULLDNULLGCEFHFHNULLGNULLNULLNULLNULLHENULLNULL第4頁，共116頁，2022年，5月20日，19點55分，星期三5遍歷二叉樹的非遞歸算法需用到棧，順序棧的定義如下：#define size 100 typedef struct Type data size ; int top ； SqStack ；第5頁，共116頁，2022年，5月20日，19點55分，星期三61.先序非遞歸遍歷：(1) 初始化一個堆棧(2) 把根結點入棧(3) 當堆棧非空時，循環(huán): A. 出棧取一個結點指針，

3、訪問該結點; B. 若該 結點右子樹非空，右子樹指針入棧(4) 左端到盡頭后,若該 棧非空，右子樹出棧 第6頁，共116頁，2022年，5月20日，19點55分，星期三7先序遍歷的非遞歸算法Status InorderTraverse(BiTree T )/ 采用二叉鏈表存儲結構. 先序遍歷二叉樹T的非遞歸算法 。 InitStack(S); p=T; while(p|!StackEmpty(S) while(p)/訪問當前結點，右子進棧，遍歷左子樹 coutdata ; if(p-rchild!=null) Push(S，p-rchild); p=p-lchild; if(StackEmpt

4、y(S)=0)/根指針退棧，遍歷右子樹 Pop(S，p); 第7頁，共116頁，2022年，5月20日，19點55分，星期三8步驟指針P棧Stack內容訪問結點值初態(tài)A1BCA2DGB3D4G5CFG6E C7F E8F9FACBFEDGwhile(p)/訪問當前結點，右子進棧，遍歷左子樹 cout data ; if(p-rchild!=null) Push(S，p-rchild); p=p-lchild; if(StackEmpty(S)=0)/根指針退棧，遍歷右子樹 Pop(S，p);第8頁，共116頁，2022年，5月20日，19點55分，星期三92.中序非遞歸遍歷：在遍歷左子樹之前，

5、先把根結點入棧，當左子樹遍歷結束后，從棧中彈出，訪問，再遍歷右子樹第9頁，共116頁，2022年，5月20日，19點55分，星期三10void InOrder(BiTree T)/ 采用二叉鏈表存儲結構。先序遍歷二叉樹T的非遞歸算法。 InitStack(S);Push(S，T); /根指針進棧 while(p | !StackEmpty(S) while( p!=NULL ) Push(S，p); /向左走到盡頭 p=p-lchild ; if(!StackEmpty(S) Pop(S，p); coutdata ; /訪問結點 p=p-rchild); /向右一步 中序遍歷的非遞歸算法1第1

6、0頁，共116頁，2022年，5月20日，19點55分，星期三11步驟指針P棧Stack內容訪問結點值初態(tài)A1ABA2BDBA3DDBA4DBA5DGBAD6GGBA7GBA8GBAG9BA10BAB11A12ACA13CEC14EECACBFEDG while( p!=NULL ) Push(S，p); /向左走到盡頭 p=p-lchild ; if(!StackEmpty(S) Pop(S，p); coutdata ; /訪問結點 p=p-rchild); /向右一步 第11頁，共116頁，2022年，5月20日，19點55分，星期三1215EC16ECE17C18CFC19FF20F21

7、FF22ACBFEDG第12頁，共116頁，2022年，5月20日，19點55分，星期三13中序遍歷的非遞歸算法2(算法) 自學Status InorderTraverse(BiTree T，Status(*visit(TElemType e)/ 采用二叉鏈表存儲結構，Visit是對數據元素操作的應用函數。先序遍歷二叉樹T的非遞歸算法，對每個數據元素調用函數Visit。 InitStack(S); p=T; while (p|!StackEmpty(S) if ( p ) /根指針進棧，遍歷左子樹 Push(S，p); p=p-lchild; else /訪問結點，根指針退棧，遍歷右子樹 Po

8、p(S，p); visit(p-data); p=p-rchild; 第13頁，共116頁，2022年，5月20日，19點55分，星期三14步驟指針P棧Stack內容訪問結點值初態(tài)A1BA2DBA3DBA4GBAD5GBA6BAG7AB8CA9EC10EC11CE12FC13F14FACBFEDGif(p) /根指針進棧，遍歷左子樹 Push(S，p); p=p-lchild; else /訪問結點，根指針退棧，遍歷右子樹 Pop(S，p); visit(p-data); p=p-rchild; 第14頁，共116頁，2022年，5月20日，19點55分，星期三153.后序非遞歸遍歷(自學)與

9、前序遍歷和中序遍歷二叉樹的算法不同，在后續(xù)遍歷二叉樹的過程中，對一個結點訪問之前，要兩次經歷這個結點。第一次是由該結點找到其左孩子結點，遍歷其左子樹，遍歷完左子樹后，返回到這個結點。第二次是由該結點找到其右孩子結點，遍歷其右子樹，遍歷完右子樹后，再次返回到結點，這時才能訪問該結點。因此，用非遞歸方法后續(xù)遍歷二叉樹時，也需要設置一個棧結構，用來保存指向所經歷結點的指針。第15頁，共116頁，2022年，5月20日，19點55分，星期三16從上面的分析可知，在后續(xù)遍歷二叉樹時，一個指針要進出棧兩次，第一次出棧的目的是由該指針找到其左孩子結點，對該結點并不做任何處理，因此出棧后需再次進棧，只有在他第

10、二次出棧后，才能訪問該結點。為了區(qū)別同一個結點兩次出棧，設置一個標志flag，令： 1 第一次出棧，結點不能訪問flag= 2 第二次出棧，結點可以訪問第16頁，共116頁，2022年，5月20日，19點55分，星期三17PostOrder( BiTree t )SqStack sMAX;BiTree p;int sign;if( t=NULL ) retrun ;top=-1;p=t;while( !(p=NULL & top = -1)if ( p!=NULL ) s+top.link=p; stop.flag=1; p=p-lchild;第17頁，共116頁，2022年，5月20日，19

11、點55分，星期三18else p=stop.link; sign=stop-.flag; if (sign=1) s+top.link=p; stop.flag=2; p=p-rchild; else printf(“%c”,p-data ); p=NULL; 第18頁，共116頁，2022年，5月20日，19點55分，星期三19第19頁，共116頁，2022年，5月20日，19點55分，星期三204.按層次遍歷二叉樹實現方法為從上層到下層，每層中從左側到右側依次訪問每個結點。下面我們將給出一棵二叉樹及其按層次順序訪問其中每個結點的遍歷序列。 ACBFEDG按層次遍歷該二叉樹的序列為：A B

12、C D E F G H第20頁，共116頁，2022年，5月20日，19點55分，星期三21二叉樹用順序存儲結構表示時，按層遍歷的算法實現：ACBFEDGABCDEFG012345671234567ACBFDGABCD#FG012345671234675第21頁，共116頁，2022年，5月20日，19點55分，星期三22void LevelOreder(SqBiTree BT)for(i=1;i=n;i+) if(BT.elemi!=#) cout BT.elemi);ABCDEFGHIJK第22頁，共116頁，2022年，5月20日，19點55分，星期三23二叉樹用鏈式存儲結構表示時，按層

13、遍歷的算法實現訪問過程描述如下：(1)訪問根結點，并將該結點記錄下來；(2)若記錄的所有結點都已處理完畢，則結束遍歷操作；否則重復下列操作。(3)取出記錄中第一個還沒有訪問孩子的結點，若它有左孩子，則訪問左孩子，并將記錄下來；若它有右孩子，則訪問右孩子，并記錄下來。在這個算法中，應使用一個隊列結構完成這項操作。所謂記錄訪問結點就是入隊操作；而取出記錄的結點就是出隊操作。第23頁，共116頁，2022年，5月20日，19點55分，星期三24這樣一來， 算法就可以描述成下列形式： (1)訪問根結點，并將根結點入隊；(2)當隊列不空時，重復下列操作：a.從隊列退出一個結點；b.若其有左孩子，則訪問左

14、孩子，并將其左孩子入隊；c.若其有右孩子，則訪問右孩子，并將其右孩子入隊；第24頁，共116頁，2022年，5月20日，19點55分，星期三25ABCDEFGHIJK初始化A第一次while循環(huán)BC第二次while循環(huán)CDE第三次while循環(huán)DEFG第四次while循環(huán)EFG第四次while循環(huán)FGHI 第25頁，共116頁，2022年，5月20日，19點55分，星期三26void LevelOrder(BiTree T) if ( T ) exit(0) ; InitQueue(Q); p=T; /初始化 coutdata ; EnQueue(Q，p);/訪問根結點，并將根結點入隊 whi

15、le(!QueueEmpty(Q)/當隊非空時重復執(zhí)行下列操作 DeQueue(Q，p); /出隊 if(p-Lchild) /處理左孩子 coutLchild ; EnQueue(Q，p-Lchild); if(p-Rchild) /處理右孩子 coutRchild ; EnQueue(Q，p-Rchild); 第26頁，共116頁，2022年，5月20日，19點55分，星期三27總結：遍歷的第一個和最后一個結點第一個結點：先序：根結點；中序：后序：最后一個結點：先序：中序：后序：根結點。沿著左鏈走，找到一個沒有左孩子的結點；從根結點出發(fā)，沿著右鏈走，找到一個沒有右孩子的結點；從根結點出發(fā)，

16、沿著右鏈走，找到一個沒有右孩子的結點；沿著左鏈走，找到一個沒有左孩子的結點；第27頁，共116頁，2022年，5月20日，19點55分，星期三28求中序的第一個結點從根結點出發(fā)，沿著左鏈走，找到一個沒有左孩子的結點；的算法：求中序的第一個結點的算法： P=T; while(P-lchild) P=P-lchild; cout data ;第28頁，共116頁，2022年，5月20日，19點55分，星期三29求中序的最后一個結點的算法：從根結點出發(fā)，沿著右鏈走，找到一個沒有右孩子的結點；求中序的最后一個結點的算法：P=T；while(P-rchild) P=P-rchild;coutdata ;

17、第29頁，共116頁，2022年，5月20日，19點55分，星期三30一個程序員的生活第30頁，共116頁，2022年，5月20日，19點55分，星期三31第31頁，共116頁，2022年，5月20日，19點55分，星期三32利用二叉鏈表中的空指針域，存放指向結點在某種遍歷次序下的前趨和后繼結點的指針(這種附加的指針稱為“線索(Thread)”)。這種加上了線索的二叉鏈表稱為線索鏈表，相應的二叉樹稱為線索二叉樹(Threaded BinaryTree)。不同的遍歷有不同的線索樹。根據線索性質的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種。6.4 線索二叉樹第32頁，

18、共116頁，2022年，5月20日，19點55分，星期三33ABCDEFGHINULLNULL中序線索二叉樹第33頁，共116頁，2022年，5月20日，19點55分，星期三34結點的結構：左標志ltag=右標志rtag=0：lchild是指向結點的左孩子的指針0：rchild是指向結點的右孩子的指針1：lchild是指向結點的前驅的左線索1：rchild是指向結點的后繼的右線索lchildltagdatartagrchild第34頁，共116頁，2022年，5月20日，19點55分，星期三35若結點有左孩子，則lchild指示其左孩子，否則lchild中存儲該結點的前驅結點的指針；若結點有右

19、孩子，則rchild指示其右孩子，否則rchild中存儲指向該結點的后繼結點的指針實質：對一個非線性結構進行線性化操作，使每個結點(除第一和最后一個外)在這些線性序列中有且僅有一個直接前驅和直接后繼。第35頁，共116頁，2022年，5月20日，19點55分，星期三36DBEAFHGIC0A00B00C11E11F01D10G01I11H1NULLNULL中序線索鏈表ROOT第36頁，共116頁，2022年，5月20日，19點55分，星期三37注意：圖中的實線表示指針，虛線表示線索。結點D的左線索為空，表示D是中序序列的開始結點，無前趨；結點C的右線索為空，表示C是中序序列的終端結點，無后繼。

20、線索二叉樹中，一個結點是葉結點的充要條件為：左、右標志均是1第37頁，共116頁，2022年，5月20日，19點55分，星期三38ABCDEFGHINULLNULL中序線索二叉樹提問：中序線索二叉樹是物理結構還是邏輯結構？第38頁，共116頁，2022年，5月20日，19點55分，星期三39不帶表頭結點的先序穿線(線索)鏈表0A01B00E11D11F1NULL第39頁，共116頁，2022年，5月20日，19點55分，星期三40不帶表頭結點的后序穿線(線索)鏈表0A01B00E11D11F1NULL非空二叉鏈表第40頁，共116頁，2022年，5月20日，19點55分，星期三41帶表頭結點的

21、中序穿線(線索)鏈表0A01B00E11D11F101ROOT01ROOT(a)空二叉鏈表(b)非空二叉鏈表第41頁，共116頁，2022年，5月20日，19點55分，星期三42從遍歷的第一個結點來看：先序序列中第一個結點必為根結點，中、后序序列中第一個結點的左孩子定為空從遍歷的最后一個結點來看：先、中序序列中最后一個結點的右孩子必為空，后序序列中最后一個結點一定為根結點線索二叉樹的作用：對于遍歷操作，線索樹優(yōu)于非線索樹；遍歷線索樹不用設棧步驟：1)找遍歷的第一個結點2)不斷地找遍歷到的結點的后繼結點，直到樹中各結點都遍歷到為止，結束。遍歷線索二叉樹第42頁，共116頁，2022年，5月20日

22、，19點55分，星期三43遍歷中序線索二叉樹(帶頭結點)P134算法6.5Status InorderTraverse_Thr(BiThrTree T，Status(*Visit)(TElemType e)/T指向頭結點，頭結點的左鏈lchild指向根結點，可參見線索化算法，中序遍歷二叉線索樹T的非遞歸算法 p=T-lchild;/p指向根結點while(p!=T)/空樹或遍歷結束時，p=T while (p-LTag=Link) p=p-lchild; if(!visit(p-data) return ERROR； /訪問其左子樹為空的結點 while (p-rchild!=T &p-RTa

23、g=Thread) p=p-rchild; Visit(p-data)/訪問后繼結點 p=p-rchild; return OK;/InOrderTraverse_Thr第43頁，共116頁，2022年，5月20日，19點55分，星期三44BDECFHIKGJLA(1)while (p-LTag=Link) p=p-lchild;(2)if(!visit(p-data) return ERROR；/訪問其左子樹為空的結點 (3)while(p-rchild!=T&p-RTag=Thread) /訪問后繼結點 p=p-rchild; Visit(p-data); (4)p=p-rchild;NU

24、LLNULLpp1p2p3p4p5p6p7p8p9p10p11p12p13p14p15第44頁，共116頁，2022年，5月20日，19點55分，星期三45BDECFHIKGJLA(1)while (p-LTag=Link) p=p-lchild;(2)if(!visit(p-data) return ERROR；/訪問其左子樹為空的結點 (3)while(p-rchild!=T&p-RTag=Thread) /訪問后繼結點 p=p-rchild; Visit(p-data); (4)p=p-rchild;NULLNULLP怎樣移動p第45頁，共116頁，2022年，5月20日，19點55分，

25、星期三46if (currentRTag =Thread) 后繼為 currentrchildelse /currentRTag =Link 后繼為中序遍歷其右子樹時訪問的第一個結點(即其右子樹最左下的結點) 尋找當前結點*current在中序下的后繼ABDECFHIKGJL中序后繼線索二叉樹DBGJEACHLKFI第46頁，共116頁，2022年，5月20日，19點55分，星期三47if (currentLTag =Thread)前驅為currentlchild else /currentLTag =Link 前驅為中序遍歷其左子樹時最后訪問的一個結點(即其左子樹最右下的結點) 尋找當前結點

26、在中序下的前驅ABDECFHIKGJL中序前驅線索二叉樹中序序列：DBGJEACHLKFI第47頁，共116頁，2022年，5月20日，19點55分，星期三48if(currentRTag =Thread) 后繼為 currentrchildelse /currentRTag=Link后繼為其左孩子，若無左孩子，則后繼為其右孩子 尋找當前結點*current在先序下的后繼先序線索二叉樹先序序列ABDEGJCFHKLIABDECFHIKGJL第48頁，共116頁，2022年，5月20日，19點55分，星期三49if (currentLTag =Thread)前驅為currentlchild el

27、se /currentLTag=Link 前驅為： 若為根結點，則無前驅； 若結點無左兄弟，則其前驅為其父結點 若結點有左兄弟。則其前驅為先序遍歷其左兄弟子樹時訪問的最后一個結點 尋找當前結點在先序下的前驅先序線索二叉樹先序序列ABDEGJCFHKLIABDECFHIKGJL第49頁，共116頁，2022年，5月20日，19點55分，星期三50if(currentRTag =Thread) 后繼為currentrchildelse/currentRTag =Link 后繼為：若為根結點，則無后繼； 若結點無右兄弟，則其后繼為其父結點 若結點有右兄弟。則其后繼為后序遍歷其右兄弟子樹時訪問的第一個

28、結點 尋找當前結點*current在后序下的后繼后序線索二叉樹后序序列： DJGEBLKHIFCAABDECFHIKGJL第50頁，共116頁，2022年，5月20日，19點55分，星期三51if(currentLTag =Thread)前驅為currentlchild else/currentLTag =Link前驅為其右孩子，若無右孩子，則前驅為其左孩子 尋找當前結點在后序下的前驅后序線索二叉樹后序序列： DJGEBLKHIFCAABDECFHIKGJL第51頁，共116頁，2022年，5月20日，19點55分，星期三第52頁，共116頁，2022年，5月20日，19點55分，星期三536

29、.4.2.森林與二叉樹的轉換將一棵樹轉換成二叉樹的方法：樹 二叉樹將一棵樹轉換成二叉樹實際上就是將這棵樹用孩子兄弟表示法存儲即可，此時，樹中的每個結點最多有兩個指針：一個指針指向第一個孩子，另一個指針指向右側第一個兄弟。當你將這兩個指針看作是二叉樹中的左孩子指針和孩子右指針時，就是一棵二叉樹了。特點：一棵樹轉換成二叉樹后，根結點沒有右孩子。 將森林轉換成二叉樹的方法與一棵樹轉換成二叉樹的方法類似，只是把森林中所有樹的根結點看作兄弟關系，并對其中的每棵樹依依地進行轉換。森林 二叉樹 第53頁，共116頁，2022年，5月20日，19點55分，星期三54森林與二叉樹的對應關系(a)三棵樹的森林：

30、T1 T2 T3ACDEFGBIKHJ(b)樹的二叉樹表示(c)森林的二叉樹表示ABCEDFGHIKJABCEDFGHIKJ第54頁，共116頁，2022年，5月20日，19點55分，星期三55樹轉化成二叉樹的簡單方法依據：樹中每個結點最多只有一個最左邊的孩子(長子)和一個右鄰的兄弟。按照這種關系很自然地就能將樹轉換成相應的二叉樹轉換步驟：在同胞兄弟之間加連線；保留結點與第一個孩子之間的連線，去掉其余連線；順時針旋轉45度。以根結點為軸；左孩子不再旋轉。第55頁，共116頁，2022年，5月20日，19點55分，星期三56樹轉換為二叉樹的示例ACDIBFEJHGACDIBFEJHGACDIBF

31、EJHG第56頁，共116頁，2022年，5月20日，19點55分，星期三57(2)森林轉化成二叉樹a.將森林中的每棵樹轉換成對應的二叉樹；b.將森林中已經轉換成的二叉樹的各個根視為兄弟，各兄弟之間自第一棵樹根到最后一棵樹根之間加連線；c.以第一棵樹的根為軸，順時針旋轉45度。森林二叉樹第57頁，共116頁，2022年，5月20日，19點55分，星期三58森林轉換成二叉樹的定義：如果F=T1，T2，Tm是森林，則可按如下規(guī)則轉換成一棵二叉樹B=root，LB，RB。(1)若F為空，即m=0，則對應的二叉樹B為空二叉樹。(2)若F不空，則對應二叉樹B的根root(B)是F中第一棵樹T1的根roo

32、t(T1)；其左子樹為B(T11，T12，T1m)，其中，T11，T12，T1m是root(T1)的子樹；其右子樹為B(T2，T3，Tn)，其中，T2，T3，Tn是除T1外其它樹構成的森林。第58頁，共116頁，2022年，5月20日，19點55分，星期三59森林轉換為二叉樹acdbefgihacdbefgihacdbefgihacdbefgih第59頁，共116頁，2022年，5月20日，19點55分，星期三602. 二叉樹轉換為森林如果B=root，LB，RB是一棵二叉樹，則可按如下規(guī)則轉換成森林F=T1，T2，Tm 。(1)如果B為空，則對應的森林F也為空。(2)如果B非空，則F中第一棵

33、樹T1的根為root；T1的根的子樹森林T11，T12，T1m 是由root 的左子樹LB轉換而來，F中除了T1之外，其余的樹組成的森林T2，T3，Tn是由root的右子樹RB轉換而成的森林。二叉樹 森林第60頁，共116頁，2022年，5月20日，19點55分，星期三61課堂作業(yè)：ACDIBFEJHGacdbefgihBCDEFGIHJKLM1.將下面這棵樹轉換成二叉樹。2.將下面的森林轉換成二叉樹。3.下面這棵二叉樹還原。第61頁，共116頁，2022年，5月20日，19點55分，星期三62樹和森林的遍歷一、樹的遍歷(先根遍歷、后根遍歷、層次遍歷)1.先根遍歷：(1)先訪問樹的根結點 (2

34、)然后依次先根遍歷根的每棵子樹2.后根遍歷：(1)先依次后根遍歷每棵子樹(2)然后訪問根結點樹的先根遍歷 轉換后的二叉樹的先序遍歷樹的后根遍歷 轉換后的二叉樹的中序遍歷第62頁，共116頁，2022年，5月20日，19點55分，星期三63ABCDEFGIHJKLM先根遍歷:A BEF CGKL DHIJM后根遍歷:EFB KLGC HIMJD A ABCDEFGIHJKLM先根遍歷:A BEF CGKL DHIJM中根遍歷:EFB KLGC HIMJD A后根遍歷:FEB LKG MJIHDC A 第63頁，共116頁，2022年，5月20日，19點55分，星期三641.先根次序遍歷的規(guī)則：(

35、1)若森林F為空， 返回；(2)否則a.訪問F的第一棵樹的根結點；b.先根次序遍歷第一棵樹的子樹森林；c.先根次序遍歷其它樹組成的森林。二、森林的遍歷ABEF CGKL DHIJMDIHJMABCDEFGIHJKLM第64頁，共116頁，2022年，5月20日，19點55分，星期三65ABCDEFGIHJKLM先根遍歷:A BEF CGKL DHIJM中根遍歷:EFB KLGC HIMJD A后根遍歷:FEB LKG MJIHDC A A森林對應的二叉樹：第65頁，共116頁，2022年，5月20日，19點55分，星期三662.中根次序遍歷的規(guī)則：(1)若森林F為空，返回；(2)否則a.中根次

36、序遍歷第一棵樹的子樹森林；b. 訪問F的第一棵樹的根結點；c.中根次序序遍歷其它樹組成的森林。EFBA KLGC HIMJDDIHJMABCDEFGIHJKLM第66頁，共116頁，2022年，5月20日，19點55分，星期三67BCDEFGIHJKLM先根遍歷:A BEF CGKL DHIJM中根遍歷:EFB KLGC A HIMJD后根遍歷:FEB LKG MJIHDC AA森林對應的二叉樹：ABCDEFGIHJKLM第67頁，共116頁，2022年，5月20日，19點55分，星期三683.后根次序遍歷的規(guī)則:(1)若森林F為空，返回；(2)否則a. 后根次序遍歷第一棵樹的子樹森林；b.

37、后根次序遍歷其它樹組成的森林；c. 訪問F的第一棵樹的根結點。EFB KLGHIMJDC AABCDEFGIHJKLM第68頁，共116頁，2022年，5月20日，19點55分，星期三69ABCDEFGIHJKLM先根遍歷:A BEF CGKL DHIJM中根遍歷:EFB KLGC HIMJD A后根遍歷:FEB LKG MJIHDC A 森林對應的二叉樹：第69頁，共116頁，2022年，5月20日，19點55分，星期三70(4) 廣度優(yōu)先遍歷(層次序遍歷) ：(1)若森林F為空，返回；(2)否則a.依次遍歷各棵樹的根結點；b.依次遍歷各棵樹根結點的所有孩子；c.依次遍歷這些孩子結點的孩子結

38、點。ABCDEFGIHJKLMACD BGHIJ EFKLM第70頁，共116頁，2022年，5月20日，19點55分，星期三71ABCDEFGIHJKLM層次遍歷: A B EC FGD KH LI J M森林對應的二叉樹：第71頁，共116頁，2022年，5月20日，19點55分，星期三726.6 赫夫曼樹 (Huffman Tree)及其應用p144最優(yōu)二叉樹(哈夫曼樹)從樹中一個結點到另一個結點之間的分支構成這兩個結點之間的路徑。 路徑長度 (Path Length)兩個結點之間的路徑長度是連接兩結點的路徑上的分支數。樹的路徑長度是各結點到根結點的路徑長度之和。第72頁，共116頁，2

39、022年，5月20日，19點55分，星期三73具有不同路徑長度的二叉樹(a)的路徑長度：1+1+2+2+2+2+3=13(b)的路徑長度：1+1+2+2+2+3+3=14在結點數目相同的二叉樹中，完全二叉樹的路徑長度最短。1234567812348567第73頁，共116頁，2022年，5月20日，19點55分，星期三74帶權路徑長度 ( Weighted Path Length， WPL )結點的權：在一些應用中，賦予樹中結點的一個有某種意義的實數。樹的帶權路徑長度是樹的各葉結點所帶的權值與該結點到根的路徑長度的乘積的和。具有不同帶權路徑長度的二叉樹(a)WPL=36(b)WPL=46(c)

40、WPL=35777555222444第74頁，共116頁，2022年，5月20日，19點55分，星期三75赫夫曼(Huffman)樹設有n個權值w1，w2，wn，構造一棵有n個葉子結點的二叉樹，第i個葉子的權值為wi，則WPL最小的二叉樹叫最優(yōu)二叉樹(哈夫曼樹)，即帶權路徑長度最短的樹。記作：n其中：權值結點到根的路徑長度第75頁，共116頁，2022年，5月20日，19點55分，星期三76說明葉子上的權值均相同時，完全二叉樹一定是最優(yōu)二叉樹，否則完全二叉樹不一定是最優(yōu)二叉樹。最優(yōu)二叉樹中，權越大的葉子離根越近。最優(yōu)二叉樹的形態(tài)不唯一，WPL最小第76頁，共116頁，2022年，5月20日，1

41、9點55分，星期三77判定樹在很多問題的處理過程中，需要進行大量的條件判斷，這些判斷結構的設計直接影響著程序的執(zhí)行效率。例如，編制一個程序，將百分制轉換成五個等級輸出。大家可能認為這個程序很簡單，并且很快就可以用下列形式編寫出來：if(socre60) printf(“E”);else if(socre70) printf(“D”); else if(score80) printf(“C”); else if(score90) printf(“B”); esle printf(“A”);在實際應用中，往往各個分數段的分布并不是均勻的。下面就是在一次考試中某門課程的各分數段的分布情況： 第77頁

42、，共116頁，2022年，5月20日，19點55分，星期三78等級分數段比例ABCDE059606970798089901000.050.150.400.300.10a60a90a80a70EYNDYNCYNBYNABACDE例：比較次數=5*1+15*2+40*3+30*4+10*4=285假設輸入100個數第78頁，共116頁，2022年，5月20日，19點55分，星期三79a80a70a60a90EYNDYNCYNBYNA比較220次CBAED第79頁，共116頁，2022年，5月20日，19點55分，星期三80a80a70a60a90EYNDYNCYNBYNAif(socre80) i

43、f(score70) if(score60) printf(“E”); else printf(“D”); else printf(“C”);else if(socre=m【例】設待壓縮的數據文件共有100個字符，這些字符均取自字符集C=a，b，c，d，e，f，g，h，等長編碼需要三位二進制數字來表示六個字符，因此，整個文件的編碼長度為300位。第95頁，共116頁，2022年，5月20日，19點55分，星期三96C =a，b，c，d，e，f，g，h則字符串efgbacd可譯為對方接受時，可按三位一分進行譯碼，即 e f g b a c d100，101，110，001，000，010，011

44、 a000b001c010d011e100f101g110h111第96頁，共116頁，2022年，5月20日，19點55分，星期三97當然，在進行電文傳送時，希望電文總長盡可能短，即傳送時間盡可能短。如果對每個字符設計長度不等的編碼，且讓電文中出現次數較多的字符采用盡可能短的編碼，則傳送長度便可減少。(2)變長編碼方案變長編碼方案將頻度高的字符編碼設置短，將頻度低的字符編碼設置較長。【例】設待壓縮的數據文件共有100個字符，這些字符均取自字符集C=a，b，c，d，e，f，其中每個字符在文件中出現的次數(簡稱頻度)如下：第97頁，共116頁，2022年，5月20日，19點55分，星期三98-字

45、符a b c d e f頻度 45 13 12 16 9 5定長編碼000001010 011100 101變長編碼0 101 100 111 1101 1100-1X45+3X13+3X12+3X16+4X9+4X5=224第98頁，共116頁，2022年，5月20日，19點55分，星期三99注意：變長編碼可能使解碼(譯碼)產生二義性。產生該問題的原因是某些字符的編碼可能與其他字符的編碼開始部分(稱為前綴)相同。【例】設E、T、W分別編碼為01、00、0001，則解碼時無法確定信息串0001是ET還是W。第99頁，共116頁，2022年，5月20日，19點55分，星期三100(3)前綴碼方案

46、對字符集進行編碼時，要求字符集中任一字符的編碼都不是其它字符的編碼的前綴，這種編碼稱為前綴(編)碼。利用哈夫曼樹很容易求出給定字符集及其概率(或頻度)分布的最優(yōu)前綴碼。具體做法：(1)用字符ci作為葉子，pi做為葉子ci的權，構造一棵哈夫曼樹，并將樹中左分支和右分支分別標記為0和1；(2)將從根到葉子的路徑上的標號依次相連，作為該葉子所表示字符的編碼。該編碼即為最優(yōu)前綴碼(也稱哈夫曼編碼)。第100頁，共116頁，2022年，5月20日，19點55分，星期三101假設有一個電文字符集中有8個字符a，b，c，d，e，f，g，h，每個字符的使用頻率分別為0.05，0.29，0.07，0.08，0.

47、14，0.23，0.03，0.11，現以此為例設計哈夫曼編碼。哈夫曼編碼設計過程為：(1)為方便計算，將所有字符的頻度乘以100，使其轉換成整型數值集合，得到5，29，7，8，14，23，3，11；(2)以此集合中的數值作為葉子結點的權值構造一棵哈夫曼樹，如圖所示；(3)由此哈夫曼樹生成哈夫曼編碼，如圖所示。第101頁，共116頁，2022年，5月20日，19點55分，星期三102字符字符的使用頻率編碼abcdefgh0.050.290.070.080.140.230.030.1101111011101111110000110010achefg8b52971114233/p>

48、00000100111011011101111011001118010111111第102頁，共116頁，2022年，5月20日，19點55分，星期三103比如，發(fā)送一段編碼：接收方可以準確地通過譯碼得到：ffgebh(00，00，0110，110，10，010)。 最后得出每個字符的編碼為：a0111，b10，c1110，d1111，e110， f00，g0110，h010第103頁，共116頁，2022年，5月20日，19點55分，星期三104假設一串待譯碼的字符串總長為100電文總長為：5*4+29*2+7*4+8*4+14*3+23*2+3*4+11*3=字符字符的使用頻率編碼abcd

49、efgh0.050.290.070.080.140.230.030.1101111011101111110000110010路徑長度權值電文總長=對應的Huffman樹的帶權路徑長度第104頁，共116頁，2022年，5月20日，19點55分，星期三105eg.設給出一段報文：CASTCASTSATATATASA字符集合是C，A，S，T，各個字符出現的頻度(次數)是2，7，4，5。若給每個字符以等長編碼A:00，T:10，C:01，S:11則總編碼長度為：(2+7+4+5)*2=36.若按各個字符出現的概率不同而給予不等長編碼，可望減少總編碼長度。因各字符出現的概率為2/18，7/18，4/1

50、8，5/18，化整為 2，7，4，5，以它們?yōu)楦魅~結點上的權值，建立赫夫曼樹。第105頁，共116頁，2022年，5月20日，19點55分，星期三106左分支賦0，右分支賦1，得赫夫曼編碼(變長編碼)。A:0，T:10，C:110，S:111，它的總編碼長度：7*1+5*2+(2+4)*3=35，比等長編碼的情形要短。總編碼長度正好等于赫夫曼樹的帶權路徑長度WPL。赫夫曼編碼是一種無前綴的編碼。解碼時不會混淆。赫夫曼編碼樹181164247ATCS010110111111第106頁，共116頁，2022年，5月20日，19點55分，星期三107思想方法(自學)給定字符集的哈夫曼樹生成后，求哈夫

51、曼編碼的具體實現過程是：依次以葉子Ti(0in-1)為出發(fā)點，向上回溯至根為止。上溯時走左分支則生成代碼0，走右分支則生成代碼1。注意： 由于生成的編碼與要求的編碼反序，將生成的代碼先從后往前依次存放在一個臨時向量中，并設一個指針start指示編碼在該向量中的起始位置(start初始時指示向量的結束位置)。 當某字符編碼完成時，從臨時向量的start處將編碼復制到該字符相應的位串bits中即可。 因為字符集大小為n，故變長編碼的長度不會超過n，加上一個結束符0，bits的大小應為n+1。第107頁，共116頁，2022年，5月20日，19點55分，星期三108typedef struct un

52、signed int weight;unsigned int parent，lchild，rchild; HTNode， *HuffmanTree;/動態(tài)分配數組存儲Huffman樹typedef char *HuffmanCode;/動態(tài)分配數組存儲Huffman樹Huffman樹和Huffman編碼的存儲表示：第108頁，共116頁，2022年，5月20日，19點55分，星期三109建立赫夫曼樹及求赫夫曼編碼的算法(p147算法6.12)第109頁，共116頁，2022年，5月20日，19點55分，星期三110void HuffmanCoding(HuffmanTree &HT，HuffmanCode &HC，int *w，int n)/w存放n個字符的權值(均0)，構造Huffman樹HT，并求出n個字符的Huffman編碼HC。 HuffmanTree p; char *cd; int i，s1，s2，start; unsigned int c，f; if(n=1) return;/n為字符數目，m為結點數目 int m=2*n-1; HT=(HuffmanTree)mall