在計算機科學中，二叉樹是每個結點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實現二叉查找樹和二叉堆。

一棵深度為k，且有2^k-1個節點的二叉樹，稱為滿二叉樹。這種樹的特點是每一層上的節點數都是最大節點數。而在一棵二叉樹中，除最后一層外，若其余層都是滿的，并且最后一層或者是滿的，或者是在右邊缺少連續若干節點，則此二叉樹為完全二叉樹。具有n個節點的完全二叉樹的深度為floor(log2n)+1。深度為k的完全二叉樹，至少有2k-1個葉子節點，至多有2k-1個節點。

二叉樹性質

(1) 在非空二叉樹中，第i層的結點總數不超過, i>=1；

(2) 深度為h的二叉樹最多有個結點(h>=1)，最少有h個結點；

(3) 對于任意一棵二叉樹，如果其葉結點數為N0，而度數為2的結點總數為N2，則N0=N2+1；

(4) 具有n個結點的完全二叉樹的深度為（注：[ ]表示向下取整）

推薦課程：PHP教程。

(5)有N個結點的完全二叉樹各結點如果用順序方式存儲，則結點之間有如下關系：

若I為結點編號則 如果I>1，則其父結點的編號為I/2；

如果2*I<=N，則其左孩子（即左子樹的根結點）的編號為2*I；若2*I>N，則無左孩子；

如果2*I+1<=N，則其右孩子的結點編號為2*I+1；若2*I+1>N，則無右孩子。

(6)給定N個節點，能構成h(N)種不同的二叉樹。

h(N)為卡特蘭數的第N項。h(n)=C(2*n，n)/(n+1)。

(7)設有i個枝點，I為所有枝點的道路長度總和，J為葉的道路長度總和J=I+2i [2]

基本概念

二叉樹是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹有五種基本形態：

(1)空二叉樹——如圖(a)；

(2)只有一個根結點的二叉樹——如圖(b)；

(3)只有左子樹——如圖(c)；

(4)只有右子樹——如圖(d)；

(5)完全二叉樹——如圖(e)。

注意：盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。 [1]

類型

(1)完全二叉樹——若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第h層有葉子結點，并且葉子結點都是從左到右依次排布，這就是完全二叉樹。

(2)滿二叉樹——除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。

(3)平衡二叉樹——平衡二叉樹又被稱為AVL樹（區別于AVL算法），它是一棵二叉排序樹，且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。

辨析

二叉樹不是樹的一種特殊情形，盡管其與樹有許多相似之處，但樹和二叉樹有兩個主要差別：

1. 樹中結點的最大度數沒有限制，而二叉樹結點的最大度數為2；

2. 樹的結點無左、右之分，而二叉樹的結點有左、右之分。

以上就是二叉樹的基本性質的詳細內容，更多請關注風君子博客其它相關文章！

總結

以上是生活随笔為你收集整理的二叉树的基本性质(完全二叉树的性质)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。