二叉樹

定義：

　　來自于百度百科。

在計算機科學中，二叉樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實現二叉查找樹和二叉堆。 二叉樹的每個結點至多只有二棵子樹(不存在度大于2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2^{i-1}個結點；深度為k的二叉樹至多有2^k-1個結點；對任何一棵二叉樹T，如果其終端結點數為n_0，度為2的結點數為n_2，則n_0=n_2+1。 一棵深度為k，且有2^k-1個節點的二叉樹，稱為滿二叉樹。這種樹的特點是每一層上的節點數都是最大節點數。而在一棵二叉樹中，除最后一層外，若其余層都是滿的，并且最后一層或者是滿的，或者是在右邊缺少連續若干節點，則此二叉樹為完全二叉樹。具有n個節點的完全二叉樹的深度為log2n+1。深度為k的完全二叉樹，至少有2^(k-1)個節點，至多有2^k-1個節點。

類型

(1)完全二叉樹——若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第h層有葉子節點，并且葉子結點都是從左到右依次排布，這就是完全二叉樹。 (2)滿二叉樹——除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。 (3)平衡二叉樹——平衡二叉樹又被稱為AVL樹（區別于AVL算法），它是一棵二叉排序樹，且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。

二叉樹性質

(1) 在非空二叉樹中，第i層的結點總數不超過 ? , i>=1； (2) 深度為h的二叉樹最多有 ? 個結點(h>=1)，最少有h個結點； (3) 對于任意一棵二叉樹，如果其葉結點數為N0，而度數為2的結點總數為N2，則N0=N2+1； (4) 具有n個結點的完全二叉樹的深度為 ? （注：[ ]表示向下取整） (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，則無右兒子。

遍歷順序

遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規則和順序走遍二叉樹的所有結點，使每一個結點都被訪問一次，而且只被訪問一次。由于二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。 設L、D、R分別表示遍歷左子樹、訪問根結點和遍歷右子樹， 則對一棵二叉樹的遍歷有三種情況：DLR（稱為先根次序遍歷），LDR（稱為中根次序遍歷），LRD （稱為后根次序遍歷）。 在接下來的篇章里我們會涉及二叉樹的算法。

coding交流群：226704167，愿和各位一起進步！

微信公眾號：

轉載于:https://www.cnblogs.com/lip0121/p/9013343.html

總結

以上是生活随笔為你收集整理的数据结构与算法 —— 二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

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