【正文】 int r， n。 //雙親位置域 }PTNode。 第一節(jié) 樹的存儲結(jié)構(gòu) //樹的雙親表存儲表示 // define MAX_TREE_SIZE 100 typedef struct PTNode { TElemType data。 //保持 pre指向 p的前驅(qū) InThreading(prchild)。 prerchild=p。plchild=pre。 }//InOrderThreading 第二節(jié) 線索二叉樹 中序遍歷進行中序線索化 void InThreading(BiThrTree p){ // 一個全程指針 pre if (p){ InThreading(plchild)。 //最后一個結(jié)點線索化 Thrtrchild=pre。 //中序遍歷進行中序線索化 prerchild=Thrt。 pre=Thrt。 //右指針回指 if (!T)Thrtlchild=Thrt。 ThrtRTag=Thread。 if (!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit (OVERFLOW)。 第二節(jié) 線索二叉樹 中序遍歷二叉樹 T，并將其中序線索化 : (為了記下遍歷過程中訪問結(jié)點的先后次序，附設一個全程指針 pre) Status InOrderThreading(BiThrTree amp。 //左右孩子指針 PointerTag LTag,RTag。 //Link==0:指針 ,Thread==1:線索 typedef struct BiThrNode { TElemType data。 – 如根結(jié)點 “ ”的前驅(qū)是 “ d” 。 – 如結(jié)點 “ *” 的后繼是 “ c” 。 ? 線索二叉樹的表示 : ? 若結(jié)點有左子樹 ， 則其 LCHILD域指示其左孩子 ，否則令 LCHILD域指示其前驅(qū)； ? 若結(jié)點有右子樹 ， 則其 RCHILD域指示其右孩子 ，否則令 RCHILD域指示其后繼 。 } return OK。 CreateBiTree(Tlchild)。 else { if (!(T=(BiTNode *) malloc(sizeof (BiTNode)))) exit(OVERFLOW)。ch)。 ? 先序序列： A B C D E F G ? 中序序列： C B E D A F G A C B E D F G A B C D E F G A B C F D E G 第一節(jié) 遍歷二叉樹 構(gòu)造二叉鏈表表示的二叉樹的遞歸算法 Status CreateBiTree(BiTree amp。 }else return OK。 后（根）序的遍歷算法： 第一節(jié) 遍歷二叉樹 A B C D G E F C F D B G E A 算法的遞歸描述 Status PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e)) { if (T){ if (PostOrderTraverse(Tlchild,Visit)) if (PostOrderTraverse(Trchild,Visit)) if (Visit(Tdata)) return OK。 }else return OK。 中（根）序的遍歷算法： 第一節(jié) 遍歷二叉樹 A B C D G E F C B D F A G E 算法的遞歸描述 Status InOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){ if (T){ if (InOrderTraverse(Tlchild,Visit)) if (Visit(Tdata)) if (InOrderTraverse(Trchild,Visit)) return OK。 }else return OK。 先（根）序的遍歷算法： 第一節(jié) 遍歷二叉樹 A B C D G E F A B C D F E G 算法的遞歸描述 Status PreOrderTraverse(BiTree T, Status(* Visit)(TElemType e)) { if (T){ if (Visit(Tdata)) if (PreOrderTraverse(Tlchild,Visit)) if (PreOrderTraverse(Trchild,Visit)) return OK。 parent lchild data rchild 結(jié)點結(jié)構(gòu) : C 語言的類型描述如下 : 第三節(jié) 二叉樹的存儲結(jié)構(gòu) 第六章 樹和二叉樹 遍歷二叉樹和線索二叉樹 按某條搜索路徑巡訪樹中每個結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次。 // 左右孩子指針 struct TriTNode *parent。 lchild data rchild 結(jié)點結(jié)構(gòu) : C 語言的類型描述如下 : 第三節(jié) 二叉樹的存儲結(jié)構(gòu) A D E B C F ? ? ? ? ? ? ? root ? 2．三叉鏈表 parent lchild data rchild 結(jié)點結(jié)構(gòu) : 第三節(jié) 二叉樹的存儲結(jié)構(gòu) typedef struct TriTNode { // 結(jié)點結(jié)構(gòu) TElemType data。 struct BiTNode *lchild, *rchild。 // 0號單元存儲根結(jié)點 SqBiTree bt。 第二節(jié) 二叉樹的性質(zhì) ? 性質(zhì) 4 ： 具有 n 個結(jié)點的完全二叉樹的深度為 ? log2 n? +1 第二節(jié) 二叉樹的性質(zhì) 假設 n=4, ? log2 n ? +1= ? log2 4 ? +1=3 1 2 3 4 假設 n=7, ? log2 n ? +1= ? log2 7 ? +1=4 1 2 3 4 5 6 7 8 ? 性質(zhì) 5 若對含 n 個結(jié)點的完全二叉樹從上到下且從左至右進行 1 至 n 的編號，則對完全二叉樹中任意一個編號為 i 的結(jié)點（ 性質(zhì) 1可由性質(zhì) 2， 3推出，證明略 ）： (1) 若 i=1，則該結(jié)點是二叉樹的根，無雙親， 否則，編號為 ?i/2? 的結(jié)點為其 雙親 結(jié)點； (2) 若 2in，則該結(jié)點無左孩子， 否則，編號為 2i 的結(jié)點為其 左孩子 結(jié)點； (3) 若 2i+1n，則該結(jié)點無右孩子結(jié)點， 否則，編號為 2i+1 的結(jié)點為其 右孩子 結(jié)點 。 （ 2） 在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若干結(jié)點后得到的二叉樹仍然是一棵完全二叉樹。 完全二叉樹 ： 樹中所含的 n 個結(jié)點和滿二叉樹中 編號為 1 至 n 的結(jié)點 一一對應。 ? 性質(zhì) 2 深度為 k的二叉樹中至多含有 2k1 個結(jié)點， (k≥1)。 操作結(jié)果：根據(jù) LR 為 0 或 1，刪除 T 中 p 所指結(jié)點的左或右子樹。T, p, LR)。 p 所指結(jié)點原有左或右子樹成為 c 的右子樹。 初始條件：二叉樹 T 存在， p 指向 T 中某個結(jié)點，LR 為 0 或 1，非空二叉樹 c 與 T 不相交且右子樹為空。 第一節(jié) 二叉樹的定義 ? InsertChild(amp。 初始條件：二叉樹 T 存在， e 是 T 中某個結(jié)點。T, amp。 操作結(jié)果：將二叉樹 T 清為空樹 。T)。一旦 visit() 失敗，則操作失敗。 初始條件：二叉樹 T 存在， visit 是對結(jié)點操作的應用函數(shù)。一旦 visit() 失敗，則操作失敗。 初始條件：二叉樹 T存在， visit 是對結(jié)點操作的應用函數(shù)。一旦 visit() 失敗，則操作失敗。 初始條件：二叉樹 T 存在， visit 是對結(jié)點操作的應用函數(shù)。一旦 visit() 失敗，則操作失敗。 初始條件：二叉樹 T 存在 ,visit 是對結(jié)點操作的應用函數(shù)。若 e 是其雙親的右孩子或無右兄弟，則返回 空 。 初始條件：二叉樹 T 存在， e 是 T 的結(jié)點。若 e 是其雙親的左孩子或無左兄弟，則返回 空 。 初始條件：二叉樹 T 存在， e 是 T 中某個結(jié)點。若 e 無右孩子，則返回 空 。 初始條件：二叉樹 T 存在， e 是 T 中某個結(jié)點。若 e 無左孩子，則返回 空 。 初始條件：二叉樹 T 存在， e 是 T 中某個結(jié)點。 操作結(jié)果：若 e是 T的非根結(jié)點，則返回它的雙親，否則返回 空 。 第一節(jié) 二叉樹的定義 ? Parent(T, e)。 初始條件：二叉樹 T 存在， e 是 T 中某個結(jié)點。 操作結(jié)果：返回 T 的根。 Root(T)。 初始條件：二叉樹 T 存在。 操作結(jié)果：若 T為空二叉樹，則返回 TRUE，否則返回 FALSE。 第一節(jié) 二叉樹的定義 ? BiTreeEmpty(T)。 初始條件：二叉樹 T 存在。 {銷毀結(jié)構(gòu) } DestroyBiTree(amp。 初始條件： definition 給出二叉樹 T 的定義。 CreateBiTree(amp。T)。如果左子樹 L 不空，則必存在一個根結(jié)點 ，它是 root 的 左后繼(root, ∈ H)，如果右子樹 R 不空，則必存在一