第2節(jié)二叉樹及其基本性質(zhì)-文庫吧
2025-04-22 10:58 本頁面
【正文】 的基本特性 ?性質(zhì) 1 ： 在二叉樹的第 i 層上至多有 2i1 個結(jié)點(diǎn)。 (i≥1) 證明： 用歸納法證明之 ?i=1時，只有一個根結(jié)點(diǎn)， 2i1=20=1 是對的 。 ?假設(shè)對所有 j(1?ji)命題成立，即第 j層上至多有 2j1 個結(jié)點(diǎn) 那么，第 i1層至多有 2i2 個結(jié)點(diǎn) 又二叉樹每個結(jié)點(diǎn)的度至多為 2 ? 第 i層上最大結(jié)點(diǎn)數(shù)是第 i1層的 2倍，即 2 2i2=2i1 故命題得證 167。 二叉樹及其基本性質(zhì) 性質(zhì) 2 ： 深度為 k 的二叉樹上至多含 2k1 個結(jié)點(diǎn)（ k≥1）。 證明： 深度為 k的二叉樹是指二叉樹共有 k層。 由性質(zhì) 1，可得深度為 k 的二叉樹最大結(jié)點(diǎn)數(shù)是 211+221+…+2 k1=2k1 122)(1
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1