NewsContent"

山東公務員考試網計算機常識-什么是二叉樹

二叉樹是一種很有用的非線性結構。二就樹具有以下兩個特點：

非空二叉樹只有一個根結點；

每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。

由以上特點可以看出，在二叉樹中，每一個結點的度最大為2，即所有子樹（左子樹或右子樹）也均為二叉樹，而樹結構中的每一個結點的度可以是任意的。另外，二叉樹中的每一個結點的子樹被明顯地分為左子樹與右子樹。可以沒有其中的一個，也可以全沒有。

二叉樹的基本性質

性質1：在二叉樹的第K層上，最多有（K≥1）個結點。

性質2：濃度為M的二叉樹最多有2m-1 個結點。

深度為m 的二叉樹是指二叉樹共有m層。

性質3：在任意一棵二叉樹中度為0的結點（即葉子結點）總是比度為2的結點多一個。

性質4：具有n個結點的二叉樹，其深度至少為[ log2n]+1,其中[ log2n]表示取的整數部分。

滿二叉樹與完全二叉樹

滿二叉樹與完全二叉樹是兩種特殊形態的二叉樹。

滿二叉樹

所謂滿二叉樹是指這樣的一種二叉樹；除最后一層外，每一層上的所有結點都有兩個子結點。這就是說，在滿二叉樹中，每一層上的結點數都達到最大值，即在滿二叉樹的第K層上有2K-1個結點，且深度為m的滿二叉樹有2m-1個結點。

完全二叉樹

所謂完全二叉樹是指這樣的二叉樹，除最后一層外，每一層上的結點數均達的最大值；在最后一層上只缺少右邊的若干結點。

列確切地說，如果從根結點起，對二叉樹的結點自上而下、自左至右用自然數進行邊疆編號，則深度為m、且有n 個結點的二叉樹，當且僅當其每一個結點都與深度為m的滿二叉樹中編號從1到n的結點一一對應時，稱之為完全二叉樹。

對于完全二叉樹來說，葉子結點只可能在層次最大的兩層上出現；對于任何一個結點，若其右分支下的子孫結點的最大層次為p，則其左分支下的子孫結點的最大層次或為p，或為p+1。

由滿二叉樹與完全二叉樹的特點可以看出，滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。

完全二叉樹還具有以下兩個性質：

性質5：具有n個結點的完全二叉樹的深度為[ log2n]+1。

性質6：設完全二叉樹共有n個結點。如果從根結點開始，按層序（每一層從左到右）用自然數1，2，…，n給結點進行編號，則對于編號為k （k=1,2,…n）的結點有以下結論：

若k=1，則該結點為根結點，它沒有父結點；若k>1，則該結點的父結點編號為INT(k/2)。

若2k≤n，則編號為k 的結點的左子結點編號為2k ；否則該結點無左子結點（顯然也沒有右子結點）。

若2k+1≤n，則編號為k 的結點的右子結點編號為2k+1；否則該結點無右子結點。

更多精彩資訊請關注查字典資訊網，我們將持續為您更新最新資訊!