【正文】 當(dāng)左子樹遍歷結(jié)束后，從棧中彈出，訪問(wèn)，再遍歷右子樹 ? 后序遍歷： 1）設(shè)定一個(gè)指針，指向 最近訪問(wèn)過(guò)的結(jié)點(diǎn)。 printf(%c,Tdata)。 遍歷結(jié)果（后綴表達(dá)式） a b c d * + e f / 后序遍歷二叉樹的遞歸算法 void PostOrderTraverse(BiTree T){ if (T) { PostOrderTraverse(Tlchild)。 在逆波蘭式中，自左到右依次掃描：是操作數(shù)，則依次進(jìn)棧；遇到運(yùn)算符。 InOrderTraverse(Trchild)。 遍歷結(jié)果（中綴表達(dá)式） a + b * c d e / f 中序遍歷 (Inorder Traversal) 表達(dá)式語(yǔ)法樹 中序遍歷二叉樹的遞歸算法 void InOrderTraverse(BiTree T){ if (T) { InOrderTraverse(Tlchild)。 PreOrderTraverse(Trchild)。 先序遍歷二叉樹的遞歸算法 void PreOrderTraverse(BiTree T){ if (T){ printf(%c,Tdata)。 設(shè) 訪問(wèn)根結(jié)點(diǎn) 記作 D 遍歷根的左子樹 記作 L 遍歷根的右子樹 記作 R 則可能的遍歷次序有 先序 DLR DRL 逆先序 中序 LDR RDL 逆中序 后序 LRD RLD 逆后序 先序遍歷 (Preorder Traversal) 先序遍歷二叉樹算法的框架是 ? 若二叉樹為空，則空操作； ? 否則 ?訪問(wèn)根結(jié)點(diǎn) (D)； ?先序遍歷左子樹 (L)； ?先序遍歷右子樹 (R)。 二叉樹鏈表表示的示例 3. 靜態(tài)二叉鏈表和靜態(tài)三叉鏈表 預(yù)先開辟空間，用數(shù)組表示 leftChild, rightChild—— 數(shù)組元素的下標(biāo) 遍歷二叉樹 (Traversing Binary Tree) p128 所謂樹的遍歷，就是按某種次序訪問(wèn)樹中的結(jié)點(diǎn)，要求每個(gè)結(jié)點(diǎn)訪問(wèn)一次且僅訪問(wèn)一次。 Struct BiTNode *lchild,*rchild。 由于一般二叉樹必須仿照完全二叉樹那樣存儲(chǔ)，可能會(huì)浪費(fèi)很多存儲(chǔ)空間，單支樹就是一個(gè)極端情況。則有以下關(guān)系： ? 若 i == 1, 則 i 是二叉樹的根，無(wú)雙親 若 i 1, 則 i 的雙親為 ?i /2? ? 若 2*i ≤ n, 則 i 的左孩子為 2*i，否則無(wú)左孩子 若 2*i+1 ≤ n, 則 i 的右孩子為 2*i+1，否則無(wú)右孩子 ? 若 i 為偶數(shù) , 且 i != n, 則其右兄弟為 i+1 若 i 為奇數(shù) , 且 i != 1, 則其左兄弟為 i1 ? i 所在層次為 ?log2 i? +1 完全二叉樹的數(shù)組表示 一般二叉樹的數(shù)組表示 二叉樹的存儲(chǔ)結(jié)構(gòu) 1. 順序存儲(chǔ)結(jié)構(gòu)（數(shù)組表示） define MAX_TREE_SIZE 100 typedef TElemType SqBiTree[MAX_TREE_SIZE]。除第 h層外，其它各層 (0?h1)的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h層從右向左連續(xù)缺若干結(jié)點(diǎn)，這就是完全二叉樹。 (i ? 1) [證明用數(shù)學(xué)歸納法 ] 性質(zhì) 2 深度為 k的二叉樹最多有 2k1個(gè)結(jié)點(diǎn)。 ? 結(jié)點(diǎn) (node) ? 結(jié)點(diǎn)的度 (degree) ? 分支 (branch)結(jié)點(diǎn) ? 葉 (leaf)結(jié)點(diǎn) ? 孩子 (child)結(jié)點(diǎn) ? 雙親 (parent)結(jié)點(diǎn) ? 兄弟 (sibling)結(jié)點(diǎn) ? 祖先 (ancestor)結(jié)點(diǎn) ? 子孫 (descendant)結(jié)點(diǎn) ? 結(jié)點(diǎn)所處層次 (level) ? 樹的深度 (depth) ? 樹的度 (degree) ? 有序樹 ? 無(wú)序樹 ? 森林 1）度（次數(shù)、級(jí)） （ 1）結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)所擁有的子數(shù)的個(gè)數(shù) （ 2）樹的度：樹內(nèi)各結(jié)點(diǎn)的度的最大值 2）描述上下及左右的關(guān)系 孩子結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的子樹的根 雙親結(jié)點(diǎn)： P120 兄弟結(jié)點(diǎn)：同一個(gè)雙親的孩子之間互稱兄弟 祖先：結(jié)點(diǎn)的祖先是從根到該結(jié)點(diǎn)所經(jīng)分支上的 所有結(jié)點(diǎn) 子孫： P120結(jié)點(diǎn)的后代 3）層次 （ 1）結(jié)點(diǎn)的層次 （ 2）樹的深度（高度） 2. 樹的基本術(shù)語(yǔ) 樹的基本操作： p119 樹的建立和遍歷 —— 重點(diǎn) 樹的抽象數(shù)據(jù)類型 二叉樹 (Binary Tree) 二叉樹的定義 二叉樹的五種不同形態(tài) 一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。 如果 n = 0，稱為空樹； 如果 n 0，則 : ? 有一個(gè)特定的稱之為 根 (root)的結(jié)點(diǎn)，它只有后繼，但沒(méi)有前驅(qū)； ? 除根以外的其它結(jié)點(diǎn)劃分為 m (m ? 0)個(gè)互不相交的有限集合 T0, T1, …, Tm1，每個(gè)集合本身又是一棵樹，并且稱之為根的 子樹 (subTree)。樹的定義和基本術(shù)語(yǔ) 二叉樹 (Binary Tree) 二叉樹的存儲(chǔ)結(jié)構(gòu) 遍歷二叉樹 (Binary Tree Traversal) 線索化二叉樹 (Threaded Binary Tree) 樹與森林 (Tree amp。 Forest) 赫夫曼樹 (Huffman Tree) 二叉樹的計(jì)數(shù) 樹的定義和基本術(shù)語(yǔ) 1. 樹的定義 樹是由 n (n ? 0)個(gè)結(jié)點(diǎn)組成的有限集合。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè) 直接 前驅(qū)，但可以有0個(gè)或多個(gè)后繼。 特點(diǎn)： 1）每個(gè)結(jié)點(diǎn)的度 ≤2； 2）是有序樹 基本操作： p121~p123 二叉樹的建立和遍歷 二叉樹的抽象數(shù)據(jù)類型 性質(zhì) 1 若二叉樹的層次從 1開始 , 則在二叉樹的第 i 層最多有 2i1個(gè)結(jié)點(diǎn)。 (k ? 1) [證明用求等比級(jí)數(shù)前 k項(xiàng)和的公式 ] 性質(zhì) 3 對(duì)任何一棵二叉樹 , 如果其葉結(jié)點(diǎn)個(gè)數(shù)為 n0, 度為 2的非葉結(jié)點(diǎn)個(gè)數(shù)為 n2, 則有 n0＝ n2＋ 1 二叉樹的性質(zhì) 證明： 若設(shè)度為 1的結(jié)點(diǎn)有 n1個(gè)，總結(jié)點(diǎn)個(gè)數(shù)為 n，總邊數(shù)為 e，則根據(jù)二叉樹的定義， n = n0 + n1 + n2 e = 2n2 + n1 = n 1 因此，有 2n2 + n1 = n0 + n1 + n2 1 n2 = n0 1 n0 = n2 + 1 同理： 三次樹： n0=1+n2+2n3 四次樹： n0=1+n2+2n3+3n4 … K次樹： n0=1+n2+2n3+…+(k 1)nk 定義 1 滿二叉樹 (Full Binary Tree) 定義 2 完全二叉樹 (Complete Binary Tree) 若設(shè)二叉樹的深度為 h，則共有 h層。 性質(zhì) 4 具有 n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 ?log2n? +1 證明： 設(shè)完全二叉樹的深度為 k，則有 2k1 1 n ? 2k 1 2k1 ? n 2k 取對(duì)數(shù) k1 ? log2n k 因?yàn)?k為整數(shù)，所以 k = ?log2n? +1 說(shuō)明：常出現(xiàn)在選擇題中 性質(zhì) 5 如果將一棵有 n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序 (自頂向下，同一層自左向右）連續(xù)編號(hào) 1, 2, …, n，然后按此結(jié)點(diǎn)編號(hào)將樹中各結(jié)點(diǎn)順序地存放于一個(gè)一維數(shù)組中 , 并簡(jiǎn)稱編號(hào)為 i的結(jié)點(diǎn)為結(jié)點(diǎn) i (1 ? i ? n)。 SqBiTree bt。 單支樹 typedef struct BiTNode{ //二叉鏈表的定義 TElemType data。 }BiTNode, *BiTree。 遍歷的結(jié)果： 產(chǎn)生一個(gè)關(guān)于結(jié)點(diǎn)的線性序列。 遍歷結(jié)果（前綴表達(dá)式） + a * b c d / e f 在波蘭式中，自左到右依次掃描：連續(xù)出現(xiàn) 2個(gè)操作數(shù)時(shí)，將其前面的運(yùn)算符退出，對(duì)該兩操作數(shù)進(jìn)行這兩個(gè)操作數(shù)前面的運(yùn)算符的運(yùn)算，運(yùn)