【正文】 tOrderTraverse(T, visit())。 操作結(jié)果： 后序遍歷 T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù) visit 一次且僅一次。 第一節(jié) 二叉樹(shù)的定義 ? LevelOrderTraverse(T, visit())。 操作結(jié)果： 層序遍歷 T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù) visit 一次且僅一次。 ClearBiTree(amp。 初始條件：二叉樹(shù) T 存在。 Assign(amp。e, value)。 操作結(jié)果：結(jié)點(diǎn) e 賦值為 value。T, p, LR, c)。 ? 操作結(jié)果： 根據(jù) LR 為 0 或 1，插入 c 為 T 中 p 所指結(jié)點(diǎn)的左或右子樹(shù)。 DeleteChild(amp。 初始條件：二叉樹(shù) T 存在， p 指向 T 中某個(gè)結(jié)點(diǎn)，LR 為 0 或 1。 } ADT BinaryTree 第一節(jié) 二叉樹(shù)的定義 ? 性質(zhì) 1 在二叉樹(shù)的第 i 層上至多有 2i1 個(gè)結(jié)點(diǎn) (i≥1)。 ? 性質(zhì) 3 對(duì)任何一棵二叉樹(shù) T，如果其終端結(jié)點(diǎn)數(shù)為 n0，度為2的結(jié)點(diǎn)數(shù)為 n2，則 n0 =n2+ 1 第二節(jié) 二叉樹(shù)的性質(zhì) a b c d e f g h i j 兩類(lèi) 特殊 的二叉樹(shù)： 滿(mǎn)二叉樹(shù) ： 指的是深度為 k且含有 2k1個(gè)結(jié)點(diǎn)的二叉樹(shù)。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 a b c d e f g h i j 注意編號(hào)規(guī)則 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 滿(mǎn)二叉樹(shù) 完全二叉樹(shù) ? 特點(diǎn)： （ 1） 滿(mǎn)二叉樹(shù)是完全二叉樹(shù)，完全二叉樹(shù)不一定是滿(mǎn)二叉樹(shù)。 （ 3） 在完全二叉樹(shù)中，若某個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它一定沒(méi)有右孩子，即該結(jié)點(diǎn)必是葉結(jié)點(diǎn)。 第二節(jié) 二叉樹(shù)的性質(zhì) a b c d e f g h i j k l 1 2 3 4 5 6 7 8 9 10 11 12 define MAX_TREE_SIZE 100 // 二叉樹(shù)的最大結(jié)點(diǎn)數(shù) typedef TElemType SqBiTree[MAX_TREE_SIZE]。 一、 二叉樹(shù)的順序存儲(chǔ)表示 第三節(jié) 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 例如 : A B C D F A B C D E F 0 1 2 3 4 5 2 5 1 3 6 編號(hào) i 下標(biāo) i1 第三節(jié) 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) E 4 例如 : A B C D E F A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 13 2 5 1 14 3 7 編號(hào) i 下標(biāo) i1 第三節(jié) 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 二叉鏈表 三叉鏈表 二、 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示 第三節(jié) 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) Data lchild data rchild parent lchild data rchild A D E B C F ? ? ? ? ? ? ? root lchild data rchild 結(jié)點(diǎn)結(jié)構(gòu) : 1. 二叉鏈表 第三節(jié) 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) typedef struct BiTNode { // 結(jié)點(diǎn)結(jié)構(gòu) TElemType data。 // 左右孩子指針 } BiTNode, *BiTree。 struct TriTNode *lchild, *rchild。 //雙親指針 } TriTNode, *TriTree。 遍歷二叉樹(shù)： 第一節(jié) 遍歷二叉樹(shù) A B C D G E F 若二叉樹(shù)為空樹(shù)，則空操作；否則， （ 1）訪問(wèn)根結(jié)點(diǎn)； （ 2）先序遍歷左子樹(shù)； （ 3）先序遍歷右子樹(shù)。 return ERROR。 }//PreOrderTraverse 第一節(jié) 遍歷二叉樹(shù) A B C D E F G D L R T D L R D L R A B E D L R D L R DLR DLR C F D G 先序遍歷結(jié)果 : A B C D E F G T 若二叉樹(shù)為空樹(shù)，則空操作；否則， （ 1）中序遍歷左子樹(shù)； （ 2）訪問(wèn)根結(jié)點(diǎn)； （ 3）中序遍歷右子樹(shù)。 return ERROR。 }//InOrderTraverse 第一節(jié) 遍歷二叉樹(shù) A B C D E F G L D R T L D R L D R A B E L D R L D R LDR LDR C F D G 中序遍歷結(jié)果 : B D C A G F E T 若二叉樹(shù)為空樹(shù)，則空操作；否則， （ 1）后序遍歷左子樹(shù)； （ 2）后序遍歷右子樹(shù)； （ 3）訪問(wèn)根結(jié)點(diǎn)。 return ERROR。 }//PostOrderTraverse 第一節(jié) 遍歷二叉樹(shù) A B C D E F G H K 例如 : 先序 序列 : A B C D E F G H K 中序 序列 : B D C A H G K F E 后序 序列 : D C B H K G F E A 第一節(jié) 遍歷二叉樹(shù) 例： 已知結(jié)點(diǎn)的先序序列和中序序列，求整棵二叉樹(shù)。T) { scanf(“%c”,amp。 if (ch==??) T=NULL。 Tdata = ch 。 CreateBiTree(Trchild)。 }//CreateBiTree 第一節(jié) 遍歷二叉樹(shù) lchild data rchild T ch 構(gòu)造二叉鏈表 A B C D G E F 按下列次序輸入字符 : ABC DE G F (其中 表示空格字符 ) 可建立如右圖的二叉鏈表 . 第一節(jié) 遍歷二叉樹(shù) ? 遍歷是非線(xiàn)性結(jié)構(gòu)的線(xiàn)性化操作保留遍歷過(guò)程的順序信息。 第二節(jié) 線(xiàn)索二叉樹(shù) 線(xiàn)索二叉樹(shù)結(jié)點(diǎn)的結(jié)構(gòu) : 0 lchild域指示其左孩子 ? ltag ={ 1 lchild域指示其前驅(qū) 0 rchild域指示其右孩子 ? rtag ={ 1 rchild域指示其后繼 ? 線(xiàn)索二叉樹(shù) ? 線(xiàn)索化 ? 線(xiàn)索鏈表 ? 線(xiàn)索 data lchild rchild rtag ltag 第二節(jié) 線(xiàn)索二叉樹(shù) 中序線(xiàn)索二叉樹(shù) + a * e / f b d c NIL NIL b * 1 1 + / f 0 0 e 第二節(jié) 線(xiàn)索二叉樹(shù) data lchild rchild rtag ltag a+b*cde/f 中序線(xiàn)索二叉樹(shù) + a * e / f b d c NIL NIL 第二節(jié) 線(xiàn)索二叉樹(shù) a+b*cde/f 中序線(xiàn)索二叉樹(shù)中查找結(jié)點(diǎn)的后繼和前驅(qū) : ? 如何在中序線(xiàn)索二叉樹(shù)中找結(jié)點(diǎn)的后繼： – rtag = 1時(shí) ， rchild所指的結(jié)點(diǎn)即為后繼； – rtag =0時(shí) ， 其后繼為遍歷其右子樹(shù)時(shí)的第一個(gè)結(jié)點(diǎn)（ 最左下結(jié)點(diǎn) ） 。 ? 如何在中序線(xiàn)索二叉樹(shù)中找結(jié)點(diǎn)的前驅(qū)： – ltag = 1時(shí) ， lchild所指的結(jié)點(diǎn)即為前驅(qū)； – ltag = 0時(shí) ， 其前驅(qū)為遍歷其左子樹(shù)時(shí)的最后一個(gè)結(jié)點(diǎn) （ 最右下結(jié)點(diǎn) ） 。 第二節(jié) 線(xiàn)索二叉樹(shù) 例如 : 將下列二叉鏈表改為中序線(xiàn)索鏈表 Info A B C D E F G H I J K L M NLtagLchild 2 4 6 0 7 0 10 0 12 13 0 0 0 0RtagRchild 3 5 0 0 8 9 11 0 0 0 14 0 0 01 2 3 4 5 6 7 8 9 10 11 12 13 14 第二節(jié) 線(xiàn)索二叉樹(shù) 0 0 0 1 0 1 0 1 0 0 1 1 1 1 5 上例樹(shù)的形態(tài) Info Ltag Lchild Rtag RchildA 0 2 0 3B 0 4 0 5C 0 6 1 ThrtD 1 Thrt 1 2E 0 7 0 8F 1 1 0 9G 0 10 0 11H 1 5 1 1I 0 12 1 3J 0 13 1 7K 1 7 0 14L 1 6 1 9M 1 2 1 10N 1 11 1 5Thrt 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B D E F C H I G K J M N L 中序線(xiàn)索二叉樹(shù) // 二叉樹(shù)的二叉線(xiàn)索存儲(chǔ)表示 typedef enum {Link,Thread} PointerTag。 struct BiThrNode *lchild,*rchild。 //左右標(biāo)志 }BiThrNode, *BiThrTree。Thrt, BiThrTree T) { // Thrt指向頭結(jié)點(diǎn)。 ThrtLTag=Link。 //建頭結(jié)點(diǎn) Thrtrchild=Thrt。 //若二叉樹(shù)空，則左指針回指 else{ Thrtlchild=T。 InThreading(T)。 preRTag=Thread。 }