datastructureinc樹狀結(jié)構(gòu)-全文預(yù)覽
【正文】 arch_re_l(nodellink)。)。 } /* 節(jié)點(diǎn)不為樹葉節(jié)點(diǎn)的狀況 */ if(del_nodellink != NULL || del_noderlink != NULL) del_node = replace(del_node)。 } return node。 node = root。 else node = noderlink。 if(root == NULL) /* 當(dāng)根節(jié)點(diǎn)為 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) ? 即走訪樹中的每一個(gè)節(jié)點(diǎn)，且每個(gè)節(jié)點(diǎn)恰好被尋訪一次 ? 追蹤方式： ? 中序追蹤 (inorder)： 先拜訪左子樹 (L： 向左移動(dòng) )，然後拜訪節(jié)點(diǎn) (V： 例如，列印資料 )，再拜訪右子樹 (R：向右移動(dòng) ) ? 前序追蹤 (preorder)： 先拜訪節(jié)點(diǎn) (V) ， 然後拜訪左子樹 (L) ，再拜訪右子樹 (R) ? 後序追蹤 (postorder)： 先拜訪左子樹 (L) ， 然後拜訪右子樹 (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)。Data Structure in C ─ 樹狀結(jié)構(gòu) 1 大綱 ? 樹狀結(jié)構(gòu) ─ 專有名詞 ? 樹狀結(jié)構(gòu) ─ 表示法 ? 二元樹 ? 二元搜尋樹 ? 引線二元樹 ? 堆積 2 樹狀結(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)或樹葉節(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 樹狀結(jié)構(gòu) ─專有名詞 (續(xù) ) ? 樹與林 (Forest)的關(guān)係 ? 林是由 n = 0個(gè)不同的互斥樹 (disjoint trees)所組合而成的，若將樹根移去將形成樹林 AKJECBIHDONGMLF5 樹狀結(jié)構(gòu) ─ 表示法 ? 圖形表示法 (p. 3) ? 串列表示法 ? 將圖形化的樹狀結(jié)構(gòu)寫成一個(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 樹狀結(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)在樹中的順序並不重要 ANMLKJIHGFEDCB7 樹狀結(jié)構(gòu) ─ 表示法 (續(xù) ) ? 以分支度為 2的樹表示 ? 將左子 右弟表示法的樹狀結(jié)構(gòu)順時(shí)鐘方向旋轉(zhuǎn) 45度即可 ANMLKJIHGFEDCB8 二元樹 ? 二元樹 (binary tree) ? 二元樹是由節(jié)點(diǎn)所組成的有限集合，這個(gè)集合若不是空集合就是由樹根及分別是右子樹(right subtree)及左子樹 (left subtree) ? 特點(diǎn) (與其他一般樹的不同 )： ? 二元樹的節(jié)點(diǎn)個(gè)數(shù)可以是零 (一般樹一定要有一個(gè)節(jié)點(diǎn) ) ? 二元樹有排列順序的關(guān)係 (一般樹則沒有 ) ? 二元樹中每一節(jié)點(diǎn)的分支度至多為 2 (一般樹無限制 ) 9 二元樹 (續(xù) ) ADCBAKJGFECBIHDAKJECBIHDONGMLF左斜樹 (left skewed tree) 完整二元樹 (plete binary tree) 滿枝二元樹 (fully binary tree) 10 二元樹 (續(xù) ) ? 特性： ? 一棵二元樹在第 i階度的最多節(jié)點(diǎn)數(shù)為 2i1， i=1 ? 一棵階度 (或深度 )為 k的二元樹， 2k1， k=1 ? 一棵二元樹，若 n0表示所有的樹葉節(jié)點(diǎn)， n2表示所有分支度為 2的節(jié)點(diǎn)， n0=n2+1 ? 表示法 ? 一維陣列表示法 ? 優(yōu)點(diǎn)：處理容易，若為滿枝二元樹，則相當(dāng)節(jié)省空間 ? 缺點(diǎn)：若為歪斜樹，則相當(dāng)浪費(fèi)空間；一般而言，較鏈結(jié)串列表示法浪費(fèi)空間 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
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1