c語言二叉樹(更新版)
【正文】 是 122)(1 11 ???? ?? ?? kkikiii層的最大結(jié)點(diǎn)數(shù)第二叉樹性質(zhì) ?性質(zhì) 3：對任何一棵二叉樹 T， 如果其終端結(jié)點(diǎn)數(shù)為 n0，度為 2的結(jié)點(diǎn)數(shù)為 n2， 則 n0=n2+1 證明： n1為二叉樹 T中度為 1的結(jié)點(diǎn)數(shù) 因?yàn)椋憾鏄渲兴薪Y(jié)點(diǎn)的度均小于或等于 2 所以：其結(jié)點(diǎn)總數(shù) n=n0+n1+n2 又二叉樹中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都只有一個 分支進(jìn)入 設(shè) B為分支總數(shù)，則 n=B+1 又：分支由度為 1和度為 2的結(jié)點(diǎn)射出， ?B=n1+2n2 于是， n=B+1=n1+2n2+1=n0+n1+n2 ?n0=n2+1 二叉樹性質(zhì) ? 滿二叉樹 –定義： ~12 個結(jié)點(diǎn)的二叉樹稱為且有一棵深度為 ?kk?特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù) ?完全二叉樹 ?定義：深度為 k， 有 n個結(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與深度為 k的滿二叉樹中編號從 1至 n的結(jié)點(diǎn)一一對應(yīng)時，稱為 ~ ?特點(diǎn) ?葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn) ?對任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為 l， 則其左分支下子孫的最大層次必為 l 或 l+1 ?性質(zhì) ?性質(zhì) 4： ? ? 1lo g 2 ?nn 深度為個結(jié)點(diǎn)的完全二叉樹的具有二叉樹性質(zhì) 1 2 3 11 4 5 8 9 12 13 6 7 10 14 15 1 2 3 11 4 5 8 9 12 6 7 10 1 2 3 4 5 6 7 1 2 3 4 5 6 二叉樹性質(zhì) 187。 樹的存儲結(jié)構(gòu) a b c d e f h g i a c d e f g h i b 0 1 2 2 3 5 5 5 1 0 9 6 0 1 2 3 4 5 7 8 9 data parent 0號單元不用或 存結(jié)點(diǎn)個數(shù) 如何找孩子結(jié)點(diǎn) 樹的存儲結(jié)構(gòu) ? 孩子表示法 –多重鏈表：每個結(jié)點(diǎn)有多個指針域，分別指向其子樹的根 187。 TD t[M]。浪費(fèi)空間，適于存滿二叉樹和完全二叉樹 a b c d e f g a b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11 二叉樹的存儲結(jié)構(gòu) ? 鏈?zhǔn)?存儲結(jié)構(gòu) –二叉鏈表 typedef struct node { datatype data。 ?數(shù)據(jù)結(jié)構(gòu)總結(jié) 32
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1