【正文】 0 0 0 0 0 0 0 0 0 8 9 0 0 0 0 0 0 第一節(jié) 樹的存儲結構 二、孩子表示法（順序存儲） 二、孩子表示法（順序存儲） define MAX_TREE_SIZE 100 typedef struct PTNode { TElemType data。 //右子樹線索化 } }//InThreading 第二節(jié) 線索二叉樹 第六章 樹和二叉樹 樹和森林 一、雙親表示法（順序存儲） R A D E F C B G K H R 1 A 0 B 0 C 0 D 1 E 1 F 3 G 6 H 6 K 6 0 1 2 3 4 5 6 7 8 9 數(shù)組下標 : * 便于涉及雙親的操作； * 求結點的孩子時需要遍歷整棵樹。 } return OK。 //建頭結點 Thrtrchild=Thrt。 struct BiThrNode *lchild,*rchild。 }//CreateBiTree 第一節(jié) 遍歷二叉樹 lchild data rchild T ch 構造二叉鏈表 A B C D G E F 按下列次序輸入字符 : ABC DE G F (其中 表示空格字符 ) 可建立如右圖的二叉鏈表 . 第一節(jié) 遍歷二叉樹 ? 遍歷是非線性結構的線性化操作保留遍歷過程的順序信息。T) { scanf(“%c”,amp。 return ERROR。 //雙親指針 } TriTNode, *TriTree。 第二節(jié) 二叉樹的性質 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ù) typedef TElemType SqBiTree[MAX_TREE_SIZE]。 } ADT BinaryTree 第一節(jié) 二叉樹的定義 ? 性質 1 在二叉樹的第 i 層上至多有 2i1 個結點 (i≥1)。T, p, LR, c)。 初始條件：二叉樹 T 存在。 操作結果： 后序遍歷 T，對每個結點調(diào)用函數(shù) visit 一次且僅一次。 操作結果： 先序遍歷 T，對每個結點調(diào)用函數(shù) visit 一次且僅一次。 操作結果：返回 e 的 左兄弟 。 操作結果：返回 e 的 左孩子 。 Value(T, e)。 初始條件：二叉樹 T 存在。T, definition)。 二叉樹或為 空樹 ，或是由一個 根結點 加上 兩棵 分別稱為 左子樹 和 右子樹的、 互不交的 二叉樹 組成。p, i)。 操作結果：將樹 T 清為空樹 。 操作結果：按某種次序對 T 的每個結點調(diào)用函數(shù) visit() 一次且至多一次。 LeftChild(T, cur_e)。 初始條件：樹 T 存在。 操作結果：銷毀樹 T。 操作結果：構造空樹 T。 兄弟（ sibling）： 同一個雙親的孩子之間互為兄弟。 結點的度（ degree of node）： 一個結點的子樹個數(shù)。數(shù)據(jù)結構 常靜 Email: 第六章 樹和二叉樹 二叉樹 樹的定義和基本術語 遍歷二叉樹和線索二叉樹 樹和森林 第六章 樹和二叉樹 樹的定義和基本術語 樹的例子（ 1）： 第一節(jié) 樹的定義 樹的例子（ 2）： 第一節(jié) 樹的定義 1．樹的定義 樹 (Tree)是 n(n≥0)個有限數(shù)據(jù)元素的集合。 終端結點（ terminal node） (葉子（ leaf ) ）： 度為 0的結點。 堂兄弟： 雙親在同一層的結點互為堂兄弟。 CreateTree(amp。 第三節(jié) 樹的抽象數(shù)據(jù)類型 ? TreeEmpty(T)。 操作結果：返回 T 的根。 初始條件：樹 T 存在， cur_e 是 T 中某個結點。一旦 visit() 失敗，則操作失敗。 InsertChild(amp。 初始條件：樹 T 存在， p 指向 T 中某個結點， 1≤i≤p 指結點的度。 A B C D E F G H K 根結點 左子樹 右子樹 二叉樹的五種基本形態(tài)： N 空樹 只含根結點 N N N L R R 右子樹為空樹 L 左子樹為空樹 左右子樹均不為空樹 ADT BinaryTree { 數(shù)據(jù)對象 ： D 是具有相同特性的數(shù)據(jù)元素的集合。 初始條件： definition 給出二叉樹 T 的定義。 操作結果：若 T為空二叉樹，則返回 TRUE，否則返回 FALSE。 初始條件：二叉樹 T 存在， e 是 T 中某個結點。若 e 無左孩子，則返回 空 。若 e 是其雙親的左孩子或無左兄弟，則返回 空 。一旦 visit() 失敗，則操作失敗。一旦 visit() 失敗，則操作失敗。 操作結果：將二叉樹 T 清為空樹 。 初始條件：二叉樹 T 存在， p 指向 T 中某個結點，LR 為 0 或 1，非空二叉樹 c 與 T 不相交且右子樹為空。 ? 性質 2 深度為 k的二叉樹中至多含有 2k1 個結點， (k≥1)。 // 0號單元存儲根結點 SqBiTree bt。 parent lchild data rchild 結點結構 : C 語言的類型描述如下 : 第三節(jié) 二叉樹的存儲結構 第六章 樹和二叉樹 遍歷二叉樹和線索二叉樹 按某條搜索路徑巡訪樹中每個結點，使得每個結點均被訪問一次，而且僅被訪問一次。 }else return OK。ch)。 ? 線索二叉樹的表示 : ? 若結點有左子樹 ， 則其 LCHILD域指示其左孩子 ，否則令 LCHILD域指示其前驅； ? 若結點有右子樹 ， 則其 RCHILD域指示其右孩子 ，否則令 RCHILD域指示其后繼 。 //左右孩子指針 PointerTag LTag,RTag。 //右指針回指 if (!T)Thrtlchild=Thrt。 }//InOrderThreading 第二節(jié) 線索二叉樹 中序遍歷進行中序線索化 void InThreading(BiThrTree p){ // 一個全程指針 pre if (p){ InThreading(plchild)。 第一節(jié) 樹的存儲結構 //樹的雙親表存儲表示 // define MAX_TREE_SIZE 100 typedef struct PTNode { TElemType data。 int child1。 R A B / C D / E / F G / H / K / 1 2 3 / 4 5 / 6 / 7 8 9 / [ ]。 //孩子鏈表頭指針 }CTBox。 ? (1)若 F為空 ， 即 m=0,則 B為空樹； ? (2)若 F非空 ， 即 m0， 則 B的根 root即為森林中第一棵樹的根 ROOT(T1)； ? B的左子樹 LB是從 T1中根結點的子樹森林F1={T11,T12, … ,T1m1}轉換而成的二叉樹 。 二、中序遍歷森林： 若森林非空，則 （ 1）中序遍歷第一棵樹的根結點的子樹森林； （ 2）訪問森林中第一棵樹的根結點； （ 3）中序遍歷除去第一棵樹之后的森林。 這棵樹便是赫夫曼樹 。 這種編碼的特點 : 譯碼簡單且具有唯一性，但編碼長度并不是最短的。 赫夫曼編碼的構造方法 ： 第二節(jié) 赫夫曼編碼 例如 ： 假設有一個電文字符集中有 8個字符，每個字符 的使用頻率分別為 {, ,}， 現(xiàn)以此為例設計赫夫曼編碼。 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))。 cd[n1]=“\0”； for(i=1。cd[start])； } free(cd)。二叉樹的 線索化過程是 基于 對二叉樹進行 遍歷 ，而線索二叉樹上的 線索又為相應的遍歷提供 了 方便 。建立存儲結構是進行其它操作的前提，因此讀者應 掌握 1 至 2 種 建立 二叉樹和樹的 存儲結構的方法 。 2. 熟悉二叉樹的各種 存儲結構 的特點及適用范圍。i++){ start=n1； for(c=i,f=HT[i].parent。i=n。//動態(tài)分配數(shù)組存儲 樹 Typedef char **Huffmancode。 ?使用頻度較 高 的字符分配一個相對比較 短 的編碼， ?使用頻度較 低 的字符分配一個比較 長 的編碼。在設計編碼時需要遵守兩個原則： （ 1）發(fā)送方傳輸?shù)亩M制編碼，到接收方解碼后必須具有 唯一性 ，即解碼結果與發(fā)送方發(fā)送的電文完全一樣； （ 2）發(fā)送的二進制編碼 盡可能地短 。 ? 樹的路徑長度 : 樹的路徑長度是從樹根到每一結點的路徑長度之和 。={T2,T3, … ,Tm} 轉換而成的二叉樹 . 第二節(jié) 森林與二叉樹的轉換 二、