datastructureinc樹(shù)狀結(jié)構(gòu)(已修改)
2025-10-10 21:45 本頁(yè)面
【正文】 Data Structure in C ─ 樹(shù)狀結(jié)構(gòu) 1 大綱 ? 樹(shù)狀結(jié)構(gòu) ─ 專有名詞 ? 樹(shù)狀結(jié)構(gòu) ─ 表示法 ? 二元樹(shù) ? 二元搜尋樹(shù) ? 引線二元樹(shù) ? 堆積 2 樹(shù)狀結(jié)構(gòu) ─專有名詞 ? 專有名詞 ? 節(jié)點(diǎn) (node)與邊 (edge) ? 祖先 (ancestor)節(jié)點(diǎn)與子孫 (descendant)節(jié)點(diǎn) ? 父節(jié)點(diǎn) (parent node)與子節(jié)點(diǎn) (children node) ? 兄弟節(jié)點(diǎn) (sibling node) ? 非終點(diǎn)節(jié)點(diǎn) (nonterminal node) ? 終點(diǎn)節(jié)點(diǎn) (terminal node)或樹(shù)葉節(jié)點(diǎn) (leaf node) ? 分支度 (degree) ? 階度 (level) ? 高度 (path) ANMLKJIHGFEDCB1234階度A是 K的祖先節(jié)點(diǎn)， K是 A的子孫節(jié)點(diǎn) A是 B, C, D的父節(jié)點(diǎn)， B, C, D是 A的子節(jié)點(diǎn) B, C, D為兄弟節(jié)點(diǎn) J, K, L, G, M, N, I是終點(diǎn)節(jié)點(diǎn)，其餘的節(jié)點(diǎn)就是非終點(diǎn)節(jié)點(diǎn) A的分支度為 3 對(duì) B而言，高度為 2，深度為 1 4 樹(shù)狀結(jié)構(gòu) ─專有名詞 (續(xù) ) ? 樹(shù)與林 (Forest)的關(guān)係 ? 林是由 n = 0個(gè)不同的互斥樹(shù) (disjoint trees)所組合而成的，若將樹(shù)根移去將形成樹(shù)林 AKJECBIHDONGMLF5 樹(shù)狀結(jié)構(gòu) ─ 表示法 ? 圖形表示法 (p. 3) ? 串列表示法 ? 將圖形化的樹(shù)狀結(jié)構(gòu)寫(xiě)成一個(gè)串列 ? Ex. 將 (A(B(E(J), F(K, L)), C(G), D(H(M, N), I)) ? 左子 右弟表示法 ? 每一個(gè)節(jié)點(diǎn)需要兩個(gè)鏈結(jié) (或指標(biāo) )欄位，左欄位連結(jié)子節(jié)點(diǎn)，右欄位連結(jié)兄弟節(jié)點(diǎn) ? 左子 右弟 (left childright sibling)表示法 dat a l i nk 1 l i nk 2 ... l i nk ndataleft c hild right sibling6 樹(shù)狀結(jié)構(gòu) ─ 表示法 (續(xù) ) ? 每一個(gè)節(jié)點(diǎn)僅有一個(gè)最左 (left most)子節(jié)點(diǎn)及一個(gè)近右 (closest right)兄弟節(jié)點(diǎn) ? 子節(jié)點(diǎn)及兄弟節(jié)點(diǎn)在樹(shù)中的順序並不重要 ANMLKJIHGFEDCB7 樹(shù)狀結(jié)構(gòu) ─ 表示法 (續(xù) ) ? 以分支度為 2的樹(shù)表示 ? 將左子 右弟表示法的樹(shù)狀結(jié)構(gòu)順時(shí)鐘方向旋轉(zhuǎn) 45度即可 ANMLKJIHGFEDCB8 二元樹(shù) ? 二元樹(shù) (binary tree) ? 二元樹(shù)是由節(jié)點(diǎn)所組成的有限集合，這個(gè)集合若不是空集合就是由樹(shù)根及分別是右子樹(shù)(right subtree)及左子樹(shù) (left subtree) ? 特點(diǎn) (與其他一般樹(shù)的不同 )： ? 二元樹(shù)的節(jié)點(diǎn)個(gè)數(shù)可以是零 (一般樹(shù)一定要有一個(gè)節(jié)點(diǎn) ) ? 二元樹(shù)有排列順序的關(guān)係 (一般樹(shù)則沒(méi)有 ) ? 二元樹(shù)中每一節(jié)點(diǎn)的分支度至多為 2 (一般樹(shù)無(wú)限制 ) 9 二元樹(shù) (續(xù) ) ADCBAKJGFECBIHDAKJECBIHDONGMLF左斜樹(shù) (left skewed tree) 完整二元樹(shù) (plete binary tree) 滿枝二元樹(shù) (fully binary tree) 10 二元樹(shù) (續(xù) ) ? 特性： ? 一棵二元樹(shù)在第 i階度的最多節(jié)點(diǎn)數(shù)為 2i1， i=1 ? 一棵階度 (或深度 )為 k的二元樹(shù)， 2k1， k=1 ? 一棵二元樹(shù)，若 n0表示所有的樹(shù)葉節(jié)點(diǎn)， n2表示所有分支度為 2的節(jié)點(diǎn)， n0=n2+1 ? 表示法 ? 一維陣列表示法 ? 優(yōu)點(diǎn)：處理容易，若為滿枝二元樹(shù)，則相當(dāng)節(jié)省空間 ? 缺點(diǎn)：若為歪斜樹(shù)，則相當(dāng)浪費(fèi)空間；一般而言，較鏈結(jié)串列表示法浪費(fèi)空間 11 二元樹(shù) (續(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 I J K L M N O1stl evel2ndl evel3rdl evel4t hl evel(1) (15 )(14 )(13 )(12 )(11 )(10 )(9)(8)(7)(6)(5)(4)(3)(2)? 鏈結(jié)表示法 ? 優(yōu)點(diǎn)：插入與刪除一個(gè)節(jié)點(diǎn)相當(dāng)容易 ? 缺點(diǎn)：很難找到該節(jié)點(diǎn)的父節(jié)點(diǎn) (parent) ? 解決方式：在節(jié)點(diǎn)的結(jié)構(gòu)上增加一欄 PARENT， 指向其父節(jié)點(diǎn)的位置 typedef struct node *tree_pointer。 typedef struct node { int data。 tree_pointer left_child, right_child。 }。 AB CD E F GH I J K13 二元樹(shù) (續(xù) ) ? 二元樹(shù)追蹤 (traversal) ? 即走訪樹(shù)中的每一個(gè)節(jié)點(diǎn)，且每個(gè)節(jié)點(diǎn)恰好被尋訪一次 ? 追蹤方式： ? 中序追蹤 (inorder)： 先拜訪左子樹(shù) (L： 向左移動(dòng) )，然後拜訪節(jié)點(diǎn) (V： 例如，列印資料 )，再拜訪右子樹(shù) (R：向右移動(dòng) ) ? 前序追蹤 (preorder)： 先拜訪節(jié)點(diǎn) (V) ， 然後拜訪左子樹(shù) (L) ，再拜訪右子樹(shù) (R) ? 後序追蹤 (postorder)： 先拜訪左子樹(shù) (L) ， 然後拜訪右子樹(shù) (R) ，再拜訪節(jié)點(diǎn) (V) +CBD%E*A/中序追蹤： A/B%C*D+E 前序追蹤： +*/A%BCDE 後序追蹤： ABC%/D*E+ void inorder(Node type *tree) { if (tree != NULL){ inorder(treellink)。 printf(“%d”, treedata)。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1