武漢軟件工程職業(yè)學(xué)院數(shù)據(jù)結(jié)構(gòu)講義第12講-樹和2叉樹(編輯修改稿)
2025-07-26 13:34 本頁面
【文章內(nèi)容簡介】 有圖4－2－2（a）可知，根結(jié)點(diǎn)在第1層上，這層結(jié)點(diǎn)數(shù)最多為1個，即20個；顯然第2層上最多有2個結(jié)點(diǎn)，即21個；……；假設(shè)第i－1層結(jié)點(diǎn)最多有2i－2個，且每個結(jié)點(diǎn)最多有兩個孩子，那么第i層上結(jié)點(diǎn)最多有22i－2＝2i－1個。性質(zhì)2 深度為k（k≥1）的二叉樹至多有2 k－1個結(jié)點(diǎn)。根據(jù)性質(zhì)1，顯然深度為k的二叉樹的結(jié)點(diǎn)總數(shù)至多為： 性質(zhì)3 在任意二叉樹中，若葉子結(jié)點(diǎn)（即度為零的結(jié)點(diǎn)）個數(shù)為n0，度為1的結(jié)點(diǎn)數(shù)為n1，度為2的結(jié)點(diǎn)個數(shù)為n2，那么有：n0＝n2＋1。設(shè)n代表二叉樹結(jié)點(diǎn)總數(shù)，那么 n＝n0＋n1＋n2 （） 由于有n個結(jié)點(diǎn)的二叉樹總分支數(shù)為n－1條，于是得 n－1＝0n0＋1n1＋2n2 （）將式（）代入式（）,得 n0＝n2＋1在研究后面的性質(zhì)之前，先介紹兩種特殊形態(tài)的二叉樹：滿二叉樹和完全二叉樹。一棵深度為k并且含有2k－1個結(jié)點(diǎn)的二叉樹稱為滿二叉樹，這種數(shù)的特點(diǎn)是每層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)，如圖4－2－2（a）所示。對滿二叉樹的結(jié)點(diǎn)可以從根結(jié)點(diǎn)開始自上向下，自左向右順序編號，圖4－2－2（a）中每個結(jié)點(diǎn)斜上角的數(shù)字即是該結(jié)點(diǎn)的編號。深度為k，含有n個結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每個結(jié)點(diǎn)的編號與相應(yīng)滿二叉樹結(jié)點(diǎn)順序編號從1到n相對應(yīng)時，則稱此二叉樹為完全二叉樹，如圖4－2－2（b）所示。而圖4－2－2（c）則不是完全二叉樹。4 5 6 7 E F DAB C D E F G12 3AB CD E F 12 34 5 6AB C12 34 5 6（a）滿二叉樹 （b）完全二叉樹 （c）非完全二叉樹 圖4－2－2 滿二叉樹和完全二叉樹性質(zhì)4 具有n個結(jié)點(diǎn)的完全二叉樹，其深度為＋1（其中表示不大于x的最大整數(shù)）。性質(zhì)5 若對有n個結(jié)點(diǎn)的完全二叉樹進(jìn)行順序編號（
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1