數(shù)據(jù)結(jié)構(gòu)第六章樹和二叉樹-展示頁
2024-10-29 15:26本頁面
【正文】 的有限集 T1, T2 ,?, Tm ，其中每個集合本身又是一棵樹，并且稱為根的子樹(SubTree)。 ? 內(nèi)部結(jié)點 :除根外的結(jié)點 ? 孩子：結(jié)點的子樹的根 ? 雙親：孩子的直接前驅(qū) A B C D E F G H I J K L M 1層 2層 4層 3層 Height= 4 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 65 樹的概念與基本術(shù)語 ? 兄弟：同一雙親的孩子 ? 子孫：以某結(jié)點為根的 樹中的所有結(jié)點 ? 祖先：從根到該結(jié)點 所經(jīng)分支上的所有結(jié)點 ? 層次：根結(jié)點為第一層，其孩子為第二層，依此類推 ? 深度：樹中結(jié)點的最大層次 ? 森林：互不相交的樹的集合。 3. 由二叉樹的定義可知，任何結(jié)點的度小于 2，因此，第 i層上的結(jié)點數(shù)最多為第 i1層上的兩倍，即 2*2i2=2i1 證畢 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 68 二叉樹 ? 二叉樹性質(zhì)２： 深度為 k的二叉樹至多有 2k1個結(jié)點 證明： 1. 由性質(zhì)１，已知第 i層上結(jié)點數(shù)最多為 2i1 2. k ∑ 2 i1 = 2k1 i=1 證畢 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 69 二叉樹 ? 二叉樹性質(zhì)３： 如果二叉樹終端結(jié)點數(shù)為 n0，度為 2的結(jié)點數(shù)為 n2，則 n0=n2+1 證明： 1. 設(shè) n1是度為 1的結(jié)點，則總結(jié)點數(shù) n= n0+n1+n2 2. 設(shè) B為二叉樹的分支數(shù)，除根結(jié)點外，每個結(jié)點有且只有一個分支，因此 n=B+1 3. 每個分支皆由度為 1或 2的結(jié)點發(fā)出， B=n1+2n2 4. n=B+1=(n1+2n2)+1 = n0+n1+n2，因此 n0=n2+1 證畢 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 610 二叉樹 ? 滿二叉樹： ? 一個深度為 k且有 2k1個結(jié)點的二叉樹 ? 每層上的結(jié)點數(shù)都是最大數(shù) ? 可以自上而下、自左至右連續(xù)編號 8 9 10 11 12 13 14 15 4 5 6 7 2 3 1 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 611 二叉樹 ? 完全二叉樹： ? 當(dāng)且僅當(dāng)每一個結(jié)點都與深度相同的滿二叉樹中編號從 1到 n的結(jié)點一一對應(yīng)的二叉樹 ? 葉子結(jié)點只在最大兩層上出現(xiàn) ? 左子樹深度與右子樹深度相等或大１ 8 9 10 11 12 4 5 6 7 2 3 1 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 612 二叉樹 ? 完全二叉樹 (性質(zhì)４ )： 具有 n個結(jié)點的完全二叉樹 ,其深度為 log2n +1 證明：設(shè) k為深度，由二叉樹性質(zhì)２，已知 2k11 ＜ n ≤ 2 k1 即 2k1 ≤ n ＜ 2k 即 k = log2n +1 8 9 10 11 12 4 5 6 7 2 3 1 x : 表示向下取整，值為 不大于 x的最大整數(shù) 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 613 ? 完全二叉樹 (性質(zhì) ５ )： ? 在完全二叉樹中，結(jié)點 i的雙親為 i/2 ? 結(jié)點 i的左孩子 LCHILD(i)=2i ? 結(jié)點 i的右孩子 RCHILD(i)=2i+1 二叉樹 8 9 10 11 12 4 5 6 7 2 3 1 2i 2i+1 2i+2 2i+3 i i+1 i/2 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 614 二叉樹 ? 二叉樹的存儲結(jié)構(gòu) ? 順序存儲結(jié)構(gòu) ：用一個一維數(shù)組來存儲二叉樹的各個結(jié)點 ? C語言表示 define MAX_TREE_SIZE 100 //二叉樹的最大結(jié)點數(shù) typedef TElemType SqBiTree[MAX_TREE_SIZE]。 ? 顯然，二叉樹的結(jié)點必須按某種次序分別存入數(shù)組的各個單元，這種次序應(yīng)能反映結(jié)點間的邏輯關(guān)系，否則二叉樹上的各種基本運(yùn)算在順序存儲結(jié)構(gòu)上很難實現(xiàn)。 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 615 二叉樹 ? 完全二叉樹的順序表示 例 : 對應(yīng)的順序存儲結(jié)構(gòu) : 將編號為 i的結(jié)點存入一維數(shù)組的第 i個單元 (下標(biāo)為 i1) 8 9 10 4 5 6 7 2 3 1 9 8 7 6 5 4 3 2 1 0 10 9 8 7 6 5 4 3 2 1 下標(biāo) → 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 616 ? 非完全二叉樹的順序表示 例 : 對應(yīng)的順序存儲結(jié)構(gòu) : 一維數(shù)組的 21單元中只用上了 7個 .最壞情況下 ,一個深度為 k且只有 k個結(jié)點的單支樹 ,卻需要長度為 2k1的一維數(shù)組 ? 總結(jié) ? 順序存儲結(jié)構(gòu)適合存儲完全二叉樹 ? 對于非完全二叉樹，采用鏈?zhǔn)酱鎯Y(jié)構(gòu)更合適 二叉樹 A B D C E G F
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1