第6章樹和二叉樹2

1、一、一、 二叉樹的順序存儲表示二叉樹的順序存儲表示 (P126)(P126)#define MAX_TREE_SIZE 100 / 二叉樹的最大結(jié)點(diǎn)數(shù)二叉樹的最大結(jié)點(diǎn)數(shù)typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0 0號單元存儲根結(jié)點(diǎn)號單元存儲根結(jié)點(diǎn) SqBiTree btSqBiTree bt; ;ABDF1235714ECA B D C E F0 1 2 3 4 5 A B D 0 C 0 E 0 0 0 0 0 0 F 00 1 2 3 4 5 6 7 8 9 10 11 12 13 146.2.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)ABDC根據(jù)二

2、叉樹的性質(zhì)根據(jù)二叉樹的性質(zhì)2： 深度為深度為 k 的二叉樹中至多含有的二叉樹中至多含有2k -1個結(jié)點(diǎn)。個結(jié)點(diǎn)。 順序存儲結(jié)構(gòu)僅適用于完全二叉樹。順序存儲結(jié)構(gòu)僅適用于完全二叉樹。 因?yàn)?，在最壞的情況下，一個深度為因?yàn)?，在最壞的情況下，一個深度為 k 且只有且只有 k 個結(jié)點(diǎn)的個結(jié)點(diǎn)的單支樹（樹中不存在度為單支樹（樹中不存在度為 2 的結(jié)點(diǎn)）卻需要長度為的結(jié)點(diǎn)）卻需要長度為2k-1的一維的一維數(shù)組。數(shù)組。A B 0 C 0 0 0 D 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 9 10 11 12 13 146.2.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)二、二叉樹的鏈?zhǔn)酱鎯Ρ硎?/p>

3、二、二叉樹的鏈?zhǔn)酱鎯Ρ硎?、二叉鏈表（、二叉鏈表（P126）typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指針左右孩子指針 BiTNode, *BiTree; lchild data rchildACBDA/B/D/C/左右孩子直接表示左右孩子直接表示雙親隱含表示雙親隱含表示6.2.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)2三叉鏈表三叉鏈表typedef struct TriTNode TElemType data; struct TriTNode *lchild, *rchild; /

4、左右孩子指針左右孩子指針 struct TriTNode *parent; / 雙親指針雙親指針 TriTNode, *TriTree;A/B/D/C/6.2.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)3雙親鏈表雙親鏈表typedef struct BPTNode /結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemType data; int *parent; / 指向雙親的指針指向雙親的指針 char LRTag; / 左、右孩子標(biāo)志域左、右孩子標(biāo)志域 BPTNode；typedef struct /樹結(jié)構(gòu)樹結(jié)構(gòu) BPTNode nodesMAX_TREE_SIZE;/初始分配空間初始分配空間 int num_nod

5、e; / 結(jié)點(diǎn)數(shù)目結(jié)點(diǎn)數(shù)目 int root;/根結(jié)點(diǎn)的位置根結(jié)點(diǎn)的位置 BPTree；6.2.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)ABDCdataparentLRtagABCD0123010-1LLRR4線索鏈表線索鏈表雙親鏈表雙親鏈表(靜態(tài)鏈表靜態(tài)鏈表) 含有含有n n個結(jié)點(diǎn)的二叉樹，在二叉鏈表存儲結(jié)構(gòu)中，共有個結(jié)點(diǎn)的二叉樹，在二叉鏈表存儲結(jié)構(gòu)中，共有2n2n個指針域，已經(jīng)使用的有個指針域，已經(jīng)使用的有n-1n-1個指針域，有個指針域，有n+1n+1個指針域未利個指針域未利用。用。6.2.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹n6.3.1

6、遍歷二叉樹遍歷二叉樹n遍歷是數(shù)據(jù)結(jié)構(gòu)最基本的操作，許多操作可以在遍歷基礎(chǔ)上遍歷是數(shù)據(jù)結(jié)構(gòu)最基本的操作，許多操作可以在遍歷基礎(chǔ)上實(shí)現(xiàn)。實(shí)現(xiàn)。n二叉樹的遍歷：按某條搜索路徑巡訪二叉樹中的結(jié)點(diǎn)，使得二叉樹的遍歷：按某條搜索路徑巡訪二叉樹中的結(jié)點(diǎn)，使得每個結(jié)點(diǎn)均被訪問一次，而且僅被每個結(jié)點(diǎn)均被訪問一次，而且僅被訪問訪問一次。一次。 遍歷的結(jié)果：產(chǎn)生一個關(guān)于結(jié)點(diǎn)的線性序列。遍歷的結(jié)果：產(chǎn)生一個關(guān)于結(jié)點(diǎn)的線性序列。只有一條搜索路徑。只有一條搜索路徑。每個結(jié)點(diǎn)有兩個后繼，則存在按什么每個結(jié)點(diǎn)有兩個后繼，則存在按什么樣的搜索路徑遍歷的問題？樣的搜索路徑遍歷的問題？二叉樹（非線性結(jié)構(gòu)）：二叉樹（非線性結(jié)構(gòu)）：線

7、性結(jié)構(gòu)：線性結(jié)構(gòu)：兩種基本策略兩種基本策略n廣度遍歷廣度遍歷n深度遍歷深度遍歷 如何訪問二叉樹的每個結(jié)點(diǎn)，如何訪問二叉樹的每個結(jié)點(diǎn)， 而且每個結(jié)點(diǎn)僅被訪問一次？而且每個結(jié)點(diǎn)僅被訪問一次？ABCDEF6.3.1 遍歷二叉樹遍歷二叉樹廣度遍歷策略廣度遍歷策略n層次遍歷方法：從上到下、從左到右訪問各結(jié)點(diǎn)層次遍歷方法：從上到下、從左到右訪問各結(jié)點(diǎn)n適用于順序存儲結(jié)構(gòu)適用于順序存儲結(jié)構(gòu)存儲結(jié)構(gòu)存儲結(jié)構(gòu)0 01 12 23 34 45 56 67 78 8A A B B CC D D E E F F遍歷結(jié)果遍歷結(jié)果：A B C D E FABCDEF深度遍歷策略深度遍歷策略n二叉樹由根、左子樹、右子樹三部

8、分組成二叉樹由根、左子樹、右子樹三部分組成ABCDEFG二叉樹的遍歷可以分解為：二叉樹的遍歷可以分解為：訪問根（訪問根（D）遍歷左子樹（遍歷左子樹（L）遍歷右子樹（遍歷右子樹（R）有六種遍歷方法：有六種遍歷方法：D L R，L D R，L R D，D R L，R D L，R L D約定先左后右約定先左后右, ,有三種遍歷方法有三種遍歷方法: : 分別稱為先序遍歷、中序遍歷、后序遍歷分別稱為先序遍歷、中序遍歷、后序遍歷 例：先序遍歷右圖所示的二叉樹，例：先序遍歷右圖所示的二叉樹，所得先序遍歷序列所得先序遍歷序列： A A, B, D, E, G, C, F, B, D, E, G, C, F先序

9、遍歷先序遍歷（DLR）n先序遍歷（先序遍歷（DLR）思想）思想若二叉樹非空，則依次進(jìn)行以下操作：若二叉樹非空，則依次進(jìn)行以下操作： （1）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)； （2）先序遍歷左子樹；）先序遍歷左子樹； （3）先序遍歷右子樹）先序遍歷右子樹。ABCDEFGA AB BC CD DE EF FG GA AB BC CD DE EF FG GA A, B, D, E, G, C, F, B, D, E, G, C, F先序遍歷先序遍歷（DLR）例：中序遍歷右圖所示的二叉樹，例：中序遍歷右圖所示的二叉樹，所得中序遍歷序列所得中序遍歷序列： D,B,G,E,A,C,F中序遍歷中序遍歷（LDR）n中

10、序遍歷（中序遍歷（LDR）思想）思想若二叉樹非空，則依次進(jìn)行以下操作：若二叉樹非空，則依次進(jìn)行以下操作： （1）中序遍歷左子樹；）中序遍歷左子樹； （2）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)； （3）中序遍歷右子樹）中序遍歷右子樹。ABCDEFGA AB BC CD DE EF FG GA AB BC CD DE EF FG G D,B,G,E,D,B,G,E,A A,C,F,C,F中序遍歷中序遍歷（LDR）后序遍歷后序遍歷（LRD）例：后序遍歷右圖所示的二叉樹，例：后序遍歷右圖所示的二叉樹，所得后序遍歷序列所得后序遍歷序列： D, G, E, B, F, C,D, G, E, B, F, C,A An后

11、序遍歷（后序遍歷（LRD）思想）思想若二叉樹非空，則依次進(jìn)行以下操作：若二叉樹非空，則依次進(jìn)行以下操作： （1）后序遍歷左子樹；）后序遍歷左子樹； （2）后序遍歷右子樹）后序遍歷右子樹； （3）訪問根結(jié)點(diǎn)。）訪問根結(jié)點(diǎn)。ABCDEFGA AB BC CD DE EF FG GA AB BC CD DE EF FG GD, G, E, B, F, C, D, G, E, B, F, C, A A后序遍歷后序遍歷（LRD）2007-1 試題試題n對下圖所示的二叉樹進(jìn)行后序遍歷（左子樹、對下圖所示的二叉樹進(jìn)行后序遍歷（左子樹、右子樹、根結(jié)點(diǎn)）的結(jié)果是右子樹、根結(jié)點(diǎn)）的結(jié)果是 （42） 。（42）A.

12、 5 2 3 4 6 1 B. 5 2 3 4 1 6 C. 2 6 4 1 3 5 D. 2 5 6 4 3 15 52 23 34 41 16 6由二叉樹的先序序列和中序序列可唯一地確定一棵二叉樹。由二叉樹的先序序列和中序序列可唯一地確定一棵二叉樹。根根左左右右根根左左右右根根左左右右先序序列先序序列中序序列中序序列例：例： 先序序列先序序列 ABHFDECKG 和中序序列和中序序列 HBDFAEKCG , 構(gòu)造二叉樹。構(gòu)造二叉樹。二叉樹的根二叉樹的根： A該二叉樹的左子樹上的結(jié)點(diǎn)有該二叉樹的左子樹上的結(jié)點(diǎn)有：該二叉樹的右子樹上的結(jié)點(diǎn)有該二叉樹的右子樹上的結(jié)點(diǎn)有：HBDFEKCG6.3.1

13、 遍歷二叉樹遍歷二叉樹例：例： 先序序列先序序列 ABHFDECKG ABHFDECKG 和中序序列和中序序列 HBDFAEKCG , HBDFAEKCG , 構(gòu)造二叉樹。構(gòu)造二叉樹。先序先序+ +中序中序 或或 后序后序+ +中序，均可唯一地確定一棵二叉樹中序，均可唯一地確定一棵二叉樹6.3.1 遍歷二叉樹遍歷二叉樹2002 試題試題n假設(shè)一棵二叉樹的后序遍歷序列為假設(shè)一棵二叉樹的后序遍歷序列為D G J H E B I F C A，中序遍歷序列為，中序遍歷序列為D B G E H J A C I F，則其先序遍歷序列，則其先序遍歷序列為為 。 A）A B C D E F G H I J B

14、）A B D E G H J C F I C）A B D E G H J F I C D）A B D E G J H C F IABDEGHJCFI二二叉叉樹樹遍遍歷歷的的遞遞歸歸算算法法void Preorder (BiTree T, void( *visit)(TElemType& e) / 先序遍歷二叉樹先序遍歷二叉樹 if (T) visit(T-data); / 訪問結(jié)點(diǎn)訪問結(jié)點(diǎn) Preorder(T-lchild, visit); / 遍歷左子樹遍歷左子樹 Preorder(T-rchild, visit); / 遍歷右子樹遍歷右子樹 void Inorder (BiTre

15、e T, void( *visit)(TElemType& e) / 中序遍歷二叉樹中序遍歷二叉樹 if (T) Inorder(T-lchild, visit); / 遍歷左子樹遍歷左子樹 visit(T-data); / 訪問結(jié)點(diǎn)訪問結(jié)點(diǎn) Inorder(T-rchild, visit); / 遍歷右子樹遍歷右子樹 6.3.1 遍歷二叉樹遍歷二叉樹遍歷二叉樹的非遞歸算法遍歷二叉樹的非遞歸算法n先序遍歷先序遍歷：將右子樹根結(jié)點(diǎn)入棧：將右子樹根結(jié)點(diǎn)入棧n中序遍歷中序遍歷：在遍歷左子樹之前，先把根結(jié)點(diǎn)入棧，當(dāng)左子：在遍歷左子樹之前，先把根結(jié)點(diǎn)入棧，當(dāng)左子樹遍歷結(jié)束后，從棧中彈出，訪問，再

16、遍歷右子樹樹遍歷結(jié)束后，從棧中彈出，訪問，再遍歷右子樹n后序遍歷后序遍歷： 1）設(shè)定一個指針，指向最近訪問過的結(jié)點(diǎn)。在退棧取出）設(shè)定一個指針，指向最近訪問過的結(jié)點(diǎn)。在退棧取出根結(jié)點(diǎn)時，需判斷：若根結(jié)點(diǎn)的右子樹為空，或它的右子根結(jié)點(diǎn)時，需判斷：若根結(jié)點(diǎn)的右子樹為空，或它的右子樹非空，但已遍歷完畢，即它的右子樹根結(jié)點(diǎn)恰好是最近樹非空，但已遍歷完畢，即它的右子樹根結(jié)點(diǎn)恰好是最近一次訪問過的結(jié)點(diǎn)時，應(yīng)該遍歷該根結(jié)點(diǎn)。反之，該根結(jié)一次訪問過的結(jié)點(diǎn)時，應(yīng)該遍歷該根結(jié)點(diǎn)。反之，該根結(jié)點(diǎn)應(yīng)重新入棧，先遍歷它的右子樹。點(diǎn)應(yīng)重新入棧，先遍歷它的右子樹。 2）還可同時設(shè)定一個標(biāo)記，指示該根結(jié)點(diǎn)是第一次還是）還可同時

17、設(shè)定一個標(biāo)記，指示該根結(jié)點(diǎn)是第一次還是第二次入棧第二次入棧6.3.1 遍歷二叉樹遍歷二叉樹先遍歷算法的非遞歸描述：先遍歷算法的非遞歸描述：（1 1）先序遍歷訪問的第一個結(jié)點(diǎn)是根結(jié)）先序遍歷訪問的第一個結(jié)點(diǎn)是根結(jié)點(diǎn)點(diǎn)；（2 2）先走到的結(jié)點(diǎn)的右子樹后訪問，訪）先走到的結(jié)點(diǎn)的右子樹后訪問，訪問結(jié)點(diǎn)的結(jié)構(gòu)是棧；問結(jié)點(diǎn)的結(jié)構(gòu)是棧；（3 3）?？盏臅r候，說明遍歷結(jié)束，沒有）?？盏臅r候，說明遍歷結(jié)束，沒有還沒有被訪問的右子樹存在。還沒有被訪問的右子樹存在。ABCDEFC E6.3.1 遍歷二叉樹遍歷二叉樹#define maxsize 100typedef struct Bitree Elemmaxsiz

18、e; int top;SqStack;void PreOrderUnrec(Bitree t) SqStack s; StackInit(s); p=t; while (p!=null | !StackEmpty(s) while (p!=null) /遍歷左子樹遍歷左子樹 visite(p-data); push(s,p); p=p-lchild; /endwhile if (!StackEmpty(s) /通過下一次循環(huán)中的內(nèi)嵌通過下一次循環(huán)中的內(nèi)嵌whilewhile實(shí)現(xiàn)右子樹遍歷實(shí)現(xiàn)右子樹遍歷 p=pop(s); p=p-rchild; /endif /endwhile /PreOrd

19、erUnrecABCDEF6.3.1 遍歷二叉樹遍歷二叉樹先序遍歷的非遞歸算法先序遍歷的非遞歸算法中序遍歷算法的非遞歸描述：中序遍歷算法的非遞歸描述：（1 1）中序遍歷訪問的第一個）中序遍歷訪問的第一個結(jié)點(diǎn)是左子樹為空的結(jié)點(diǎn)結(jié)點(diǎn)是左子樹為空的結(jié)點(diǎn)；（2 2）先走到的后訪問，訪問）先走到的后訪問，訪問結(jié)點(diǎn)的結(jié)構(gòu)是棧；結(jié)點(diǎn)的結(jié)構(gòu)是棧；ABCDEFGHKp（3 3）棧空的時候，說明遍歷）?？盏臅r候，說明遍歷結(jié)束，沒有還沒有被訪問的結(jié)束，沒有還沒有被訪問的右子樹存在。右子樹存在。入棧入棧AB/CD6.3.1 遍歷二叉樹遍歷二叉樹 #define maxsize 100typedef struct Bi

20、tree Elemmaxsize; int top;SqStack;void InOrderUnrec(Bitree t) SqStack s; StackInit(s); p=t; while (p!=null | !StackEmpty(s) while (p!=null) /遍歷左子樹遍歷左子樹 push(s,p); p=p-lchild; /endwhile if (!StackEmpty(s) p=pop(s); visite(p-data); /訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) p=p-rchild; /通過下一次循環(huán)實(shí)現(xiàn)右子樹遍歷通過下一次循環(huán)實(shí)現(xiàn)右子樹遍歷 /endif /endwhile

21、 /InOrderUnrec中序遍歷的非遞歸算法中序遍歷的非遞歸算法ABCDEF6.3.1 遍歷二叉樹遍歷二叉樹 后序遍歷時，每遇到一個結(jié)點(diǎn)，先把它推入棧中，讓后序遍歷時，每遇到一個結(jié)點(diǎn)，先把它推入棧中，讓PopTimPopTim=0=0。在遍歷其。在遍歷其左子樹前，改結(jié)點(diǎn)的左子樹前，改結(jié)點(diǎn)的PopTimPopTim=1=1，將其左孩子推入棧中。在遍歷完左子樹后，還，將其左孩子推入棧中。在遍歷完左子樹后，還不能訪問該結(jié)點(diǎn)，必須繼續(xù)遍歷右子樹，此時改結(jié)點(diǎn)的不能訪問該結(jié)點(diǎn)，必須繼續(xù)遍歷右子樹，此時改結(jié)點(diǎn)的PopTimPopTim=2=2，并把其右孩，并把其右孩子推入棧中。在遍歷完右子樹后，結(jié)點(diǎn)才退

22、棧訪問。子推入棧中。在遍歷完右子樹后，結(jié)點(diǎn)才退棧訪問。后序遍歷的非遞歸算法描述后序遍歷的非遞歸算法描述6.3.1 遍歷二叉樹遍歷二叉樹void PostOrderUnrec(Bitree t) SqStack s; stacknode x; StackInit(s); p=t; do while (p!=null) /遍歷左子樹遍歷左子樹 x.ptr = p; x.tag = L; /標(biāo)記為左子樹標(biāo)記為左子樹 push(s,x); p=p-lchild; while (!StackEmpty(s) & s.Elems.top.tag=R) x = pop(s); p = x.ptr;

23、visite(p-data); /tag為為R，表示右子樹訪問完畢，故訪問根結(jié)點(diǎn)表示右子樹訪問完畢，故訪問根結(jié)點(diǎn) if (!StackEmpty(s) s.Elems.top.tag =R; /遍歷右子樹遍歷右子樹 p=s.Elems.top.ptr-rchild; while (!StackEmpty(s);/PostOrderUnrec 后后序序遍遍歷歷的的非非遞遞歸歸算算法法#define maxsize 100typedef enumL,R tagtype;typedef struct Bitree ptr; tagtype tag;stacknode;typedef struct s

24、tacknode Elemmaxsize; int top;SqStack;遍歷的第一個和最后一個結(jié)點(diǎn)遍歷的第一個和最后一個結(jié)點(diǎn)第一個結(jié)點(diǎn)：第一個結(jié)點(diǎn)：先序：根結(jié)點(diǎn)；先序：根結(jié)點(diǎn)；中序：沿著左鏈走，找到一個沒有左孩子的結(jié)點(diǎn)；中序：沿著左鏈走，找到一個沒有左孩子的結(jié)點(diǎn)；后序：從根結(jié)點(diǎn)出發(fā)，沿著左鏈走，找到一個既沒有左孩子又沒有后序：從根結(jié)點(diǎn)出發(fā)，沿著左鏈走，找到一個既沒有左孩子又沒有右孩子的結(jié)點(diǎn)。右孩子的結(jié)點(diǎn)。最后一個結(jié)點(diǎn)：最后一個結(jié)點(diǎn)：中序：從根結(jié)點(diǎn)出發(fā)，沿著右鏈走，找到一個沒有右孩子的結(jié)點(diǎn)；中序：從根結(jié)點(diǎn)出發(fā)，沿著右鏈走，找到一個沒有右孩子的結(jié)點(diǎn)；后序：根結(jié)點(diǎn)。后序：根結(jié)點(diǎn)。先序：從根結(jié)點(diǎn)出

25、發(fā)，沿著右鏈走，找到一個沒有右孩子的結(jié)點(diǎn)；如先序：從根結(jié)點(diǎn)出發(fā)，沿著右鏈走，找到一個沒有右孩子的結(jié)點(diǎn)；如果該結(jié)點(diǎn)有左孩子，再沿著其左孩子的右鏈走，以此類推，直到找到一果該結(jié)點(diǎn)有左孩子，再沿著其左孩子的右鏈走，以此類推，直到找到一個沒有孩子的結(jié)點(diǎn)。個沒有孩子的結(jié)點(diǎn)。6.3.1 遍歷二叉樹遍歷二叉樹遍歷算法的應(yīng)用舉例遍歷算法的應(yīng)用舉例1、統(tǒng)計二叉樹中葉子結(jié)點(diǎn)的個數(shù)、統(tǒng)計二叉樹中葉子結(jié)點(diǎn)的個數(shù)（1 1）空樹）空樹 0 0（2 2）葉子結(jié)點(diǎn)）葉子結(jié)點(diǎn) 1 1（3 3）不是葉子結(jié)點(diǎn)，左右子樹存在）不是葉子結(jié)點(diǎn)，左右子樹存在 左子樹葉子結(jié)點(diǎn)數(shù)左子樹葉子結(jié)點(diǎn)數(shù)+ +右子樹葉子結(jié)點(diǎn)數(shù)右子樹葉子結(jié)點(diǎn)數(shù)ABCDE

26、int CountLeaf (BiTree T) if (T =NULL) return 0; else if (T-lchild=NULL & T-rchild=NULL) return 1; else return( CountLeaf(T-lchild) +CountLeaf(T- rchild); / if / CountLeafint Size(BiTree T) if (T=NULL) return 0; else return 1 + Size (T-lchild ) + Size ( T-rchild);ABCDE2、求二叉樹的深度、求二叉樹的深度(后序遍歷后序遍歷)Depth=0Depth=1Depth= Max(d1,d2)+1d1d2求二叉樹結(jié)點(diǎn)個數(shù)求二叉樹結(jié)點(diǎn)個數(shù)遍歷算法的應(yīng)用舉例遍歷算法的應(yīng)用舉例int Depth (BiTree T ) if ( !T ) depthval = 0; else dept