第2節(jié)二叉樹及其基本性質(zhì)(留存版)
【正文】 叉樹，度為 0的葉子結(jié)點總是比度為 2 的結(jié)點多一個，則必存在關(guān)系式： n0 = n2+1。 二叉樹及其基本性質(zhì) 1 2 3 11 4 5 8 9 12 13 6 7 10 14 15 性質(zhì) 5： 若對含 n 個結(jié)點的完全二叉樹從上到下且從左至右進行 1 至 n 的編號，則對完全二叉樹中任意一個編號為 i 的結(jié)點： (1) 若 i=1，則該結(jié)點是二叉樹的根，無雙親，否則，編號為 i/2 的結(jié)點為其雙親結(jié)點； (2) 若 2in，則該結(jié)點無左孩子，否則，編號為 2i 的結(jié)點為其左孩子結(jié)點； (3) 若 2i+1n，則該 結(jié)點無右孩子結(jié)點， 否則，編號為 2i+1 的 結(jié)點為其右孩子結(jié)點。 ?假設(shè)對所有 j(1?ji)命題成立，即第 j層上至多有 2j1 個結(jié)點 那么，第 i1層至多有 2i2 個結(jié)點 又二叉樹每個結(jié)點的度至多為 2
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1