【正文】 arch_re_l(nodellink)。)。 } /* 節(jié)點不為樹葉節(jié)點的狀況 */ if(del_nodellink != NULL || del_noderlink != NULL) del_node = replace(del_node)。 } return node。 node = root。 else node = noderlink。 if(root == NULL) /* 當根節(jié)點為 NULL的狀況 */ root = ptr。 } ptr = (struct student *) malloc(sizeof(struct student))。 printf(“%d”, treedata)。 preorder(treellink)。 AB CD E F GH I J K13 二元樹 (續(xù) ) ? 二元樹追蹤 (traversal) ? 即走訪樹中的每一個節(jié)點，且每個節(jié)點恰好被尋訪一次 ? 追蹤方式： ? 中序追蹤 (inorder)： 先拜訪左子樹 (L： 向左移動 )，然後拜訪節(jié)點 (V： 例如，列印資料 )，再拜訪右子樹 (R：向右移動 ) ? 前序追蹤 (preorder)： 先拜訪節(jié)點 (V) ， 然後拜訪左子樹 (L) ，再拜訪右子樹 (R) ? 後序追蹤 (postorder)： 先拜訪左子樹 (L) ， 然後拜訪右子樹 (R) ，再拜訪節(jié)點 (V) +CBD%E*A/中序追蹤： A/B%C*D+E 前序追蹤： +*/A%BCDE 後序追蹤： ABC%/D*E+ void inorder(Node type *tree) { if (tree != NULL){ inorder(treellink)。Data Structure in C ─ 樹狀結構 1 大綱 ? 樹狀結構 ─ 專有名詞 ? 樹狀結構 ─ 表示法 ? 二元樹 ? 二元搜尋樹 ? 引線二元樹 ? 堆積 2 樹狀結構 ─專有名詞 ? 專有名詞 ? 節(jié)點 (node)與邊 (edge) ? 祖先 (ancestor)節(jié)點與子孫 (descendant)節(jié)點 ? 父節(jié)點 (parent node)與子節(jié)點 (children node) ? 兄弟節(jié)點 (sibling node) ? 非終點節(jié)點 (nonterminal node) ? 終點節(jié)點 (terminal node)或樹葉節(jié)點 (leaf node) ? 分支度 (degree) ? 階度 (level) ? 高度 (path) ANMLKJIHGFEDCB1234階度A是 K的祖先節(jié)點， K是 A的子孫節(jié)點 A是 B, C, D的父節(jié)點， B, C, D是 A的子節(jié)點 B, C, D為兄弟節(jié)點 J, K, L, G, M, N, I是終點節(jié)點，其餘的節(jié)點就是非終點節(jié)點 A的分支度為 3 對 B而言，高度為 2，深度為 1 4 樹狀結構 ─專有名詞 (續(xù) ) ? 樹與林 (Forest)的關係 ? 林是由 n = 0個不同的互斥樹 (disjoint trees)所組合而成的，若將樹根移去將形成樹林 AKJECBIHDONGMLF5 樹狀結構 ─ 表示法 ? 圖形表示法 (p. 3) ? 串列表示法 ? 將圖形化的樹狀結構寫成一個串列 ? Ex. 將 (A(B(E(J), F(K, L)), C(G), D(H(M, N), I)) ? 左子 右弟表示法 ? 每一個節(jié)點需要兩個鏈結 (或指標 )欄位，左欄位連結子節(jié)點，右欄位連結兄弟節(jié)點 ? 左子 右弟 (left childright sibling)表示法 dat a l i nk 1 l i nk 2 ... l i nk ndataleft c hild right sibling6 樹狀結構 ─ 表示法 (續(xù) ) ? 每一個節(jié)點僅有一個最左 (left most)子節(jié)點及一個近右 (closest right)兄弟節(jié)點 ? 子節(jié)點及兄弟節(jié)點在樹中的順序並不重要 ANMLKJIHGFEDCB7 樹狀結構 ─ 表示法 (續(xù) ) ? 以分支度為 2的樹表示 ? 將左子 右弟表示法的樹狀結構順時鐘方向旋轉 45度即可 ANMLKJIHGFEDCB8 二元樹 ? 二元樹 (binary tree) ? 二元樹是由節(jié)點所組成的有限集合，這個集合若不是空集合就是由樹根及分別是右子樹(right subtree)及左子樹 (left subtree) ? 特點 (與其他一般樹的不同 )： ? 二元樹的節(jié)點個數(shù)可以是零 (一般樹一定要有一個節(jié)點 ) ? 二元樹有排列順序的關係 (一般樹則沒有 ) ? 二元樹中每一節(jié)點的分支度至多為 2 (一般樹無限制 ) 9 二元樹 (續(xù) ) ADCBAKJGFECBIHDAKJECBIHDONGMLF左斜樹 (left skewed tree) 完整二元樹 (plete binary tree) 滿枝二元樹 (fully binary tree) 10 二元樹 (續(xù) ) ? 特性： ? 一棵二元樹在第 i階度的最多節(jié)點數(shù)為 2i1， i=1 ? 一棵階度 (或深度 )為 k的二元樹， 2k1， k=1 ? 一棵二元樹，若 n0表示所有的樹葉節(jié)點， n2表示所有分支度為 2的節(jié)點， n0=n2+1 ? 表示法 ? 一維陣列表示法 ? 優(yōu)點：處理容易，若為滿枝二元樹，則相當節(jié)省空間 ? 缺點：若為歪斜樹，則相當浪費空間；一般而言，較鏈結串列表示法浪費空間 11 二元樹 (續(xù) ) A B C D1stl evel2ndl evel3rdl evel4t hl evel(1) (15 )(14 )(13 )(12 )(11 )(10 )(9)(8)(7)(6)(5)(4)(3)(2)A B C D E F G H I J K1stl evel2ndl evel3rdl evel4t hl evel(1) (15 )(14 )(13 )(12 )(11 )(10 )(9)(8)(7)(6)(5)(4)(3)(2)A B C D E F G H