數(shù)據(jù)結構第六章樹和二叉樹-在線瀏覽
2024-12-20 15:26本頁面
【正文】 D C B A F E G 中國科大 《 數(shù)據(jù)結構 》 617 二叉樹 ? 二叉鏈表 ? 結點結構 : 通常每個結點中設置三個域 ,即值域、左指針域和右指針域，其結點結構如下： 其中 data表示值域， lchild和 rchild分別表示左指針域和右指針域，用以分別存儲指向左兒子結點和右兒子結點的指針。 lchild data rchild typedef struct BiTNode { TElemType data。 } BiTNode, *BITree。 lchild data parent rchild 中國科大 《 數(shù)據(jù)結構 》 620 遍歷二叉樹 ? 遍歷二叉樹 ? 定義：二叉樹的遍歷 (Traverse)是指按一定的規(guī)律訪問二叉樹的每個結點，且每個結點只被訪問一次的過程。 ? 本節(jié)僅討論二叉鏈表的遍歷過程。操作次序主要分為三種： 1. 左、根、右；也稱為 中序遍歷、 LDR； 2. 根、左、右；也稱為 先序遍歷、 DLR； 3. 左、右、根；也稱為 后序遍歷、 LRD。 2. 先序 (PreOrder)遍歷：若樹為空，執(zhí)行空操作；否則依次執(zhí)行： ? 訪問根結點 D； ? 先序遍歷左子樹 L； ? 先序遍歷右子樹 R。 中國科大 《 數(shù)據(jù)結構 》 622 遍歷二叉樹 ? 二叉樹遍歷的實現(xiàn) template class T void PreOrder(BiTreeNodeT *t, void Visit(T item)) //使用 Visit(item)函數(shù)前序遍歷二叉樹 t { if(t != NULL) { Visit(tdata)。 PreOrder(tRight(), Visit)。 A D B F C G E 輸出結果： ABDEGCF (第一個輸出節(jié)點必為根節(jié)點 ) 中國科大 《 數(shù)據(jù)結構 》 623 遍歷二叉樹 template class T void InOrder(BiTreeNodeT *t, void Visit(T item)) //使用 Visit(item)函數(shù)中序遍歷二叉樹 t { if(t != NULL) { InOrder(tLeft(), Visit)。 InOrder(tRight(), Visit)。 PostOrder(tRight(), Visit)。 } } 輸出結果： DGEBFCA (最后一個輸出節(jié)點必為根節(jié)點 ) A D B F C G E 中國科大 《 數(shù)據(jù)結構 》 625 遍歷二叉樹 ? 遍歷二叉樹應用 1. 利用后序求結點個數(shù)或樹的高度 2. 利用前序實現(xiàn)二叉樹復制 3. 判斷兩棵樹是否相等 1. Return 1+Size (tlchild) + Size (trchild)。 temp lchile =copy(orignodelchild)。 3. If (a!=NULL amp。 b!=NULL amp。 adata=bdata amp。 equal(alchild=b lchild) amp。 equal(archild=b rchild)) 中國科大 《 數(shù)據(jù)結構 》 626 遍歷二叉樹 ? 根據(jù)先、中序遍歷求序列二叉樹 ：如果已知一棵二叉樹的先序遍歷和中序遍歷序列，則可以惟一確定這棵二叉樹 ? 算法： ，第一個節(jié)點為根節(jié)點 D ，根節(jié)點 D左邊的節(jié)點歸為左子樹，根節(jié)點 D右邊的節(jié)點歸為右子樹 1,2兩步，直到確定二叉樹 中國科大 《 數(shù)據(jù)結構 》 627 遍歷二叉樹 ? 示例：已知一棵二叉樹的 ? 先序遍歷序列為： ABDEGCF， ? 中序遍歷序列為： DBGEAFC， 請畫出這棵二叉樹 ? 解：根據(jù)先序遍歷序列，可知根節(jié)點為 A；再根據(jù)中序遍歷序列可知，左子樹由 DBGE組成，右子樹由 FC組成。 27 A D B F C G E 左子樹 右子樹 中國科大 《 數(shù)據(jù)結構 》 628 遍歷二叉樹 ? 根據(jù)后、中序遍歷求序列二叉樹 ：如果已知一棵二叉樹的后序遍歷和中序遍歷序列，則可以惟一確定這棵二叉樹 ? 算法： ，最后一個節(jié)點為根節(jié)點 D ，根節(jié)點 D左邊的節(jié)點歸為左子樹，根節(jié)點 D右邊的節(jié)點歸為右子樹 1,2兩步，直到確定二叉樹 中國科大 《 數(shù)據(jù)結構 》 629 遍歷二叉樹 ? 示例：已知一棵二叉樹的 ? 后序遍歷序列為： DGEBFCA ， ? 中序遍歷序列為： DBGEAFC， 請畫出這棵二叉樹 ? 解：根據(jù)后序遍歷序列，可知根節(jié)點為 A；再根據(jù)中序遍歷序列可知，左子樹由 DBGE組成，右子樹由 FC組成。 29 A D B F C G E 左子樹
教學課件相關推薦
鄂ICP備17016276號-1