Tree:
--------------------
Height=4 Leves=5 Root
Degree=3 Size=26 ↙
___________________17____________    Node           Level1
/ / \ ↙
26______ 2 ___9__ ←- Child       Level2
/ \ \ / / \
___0 19 _3___ 6 ___21 15               Level3
/ / \ / \ / \
7 _16 _24 _8 10 4 23           Level4
/ \ / / \ / \ / \
5 11 28 13 1 27 29 18 22       Level5
↑ ↑
↑___↑_______↑... Leaf Left Child Right Child

術語

節(jié)點：包含一個數據元素及若干指向其子樹的分支，又的譯成“結點”（Node）

根：樹和子樹的“頂點”（Root）

度：節(jié)點擁有的子樹數量稱為節(jié)點的度（Degree）；樹的度是指樹內個結點的度的最大值

分支節(jié)點：度不為0的節(jié)點

葉子：沒有子樹的節(jié)點，即它的度為0 （Leaf）

子節(jié)點：結點的子樹的根稱為該節(jié)點的孩子（Child）

父節(jié)點：對應子節(jié)點上一層(level)節(jié)點稱為該節(jié)點的雙親（Parent）

兄弟結點：同一父節(jié)點的子節(jié)點，互稱兄弟（Sibling）

節(jié)點的祖先：是從根到該結點所經分支上的所有節(jié)點

節(jié)點的子孫：以某結點為根的子樹中的所有節(jié)點

層：從根開始，根為第一層，根的孩子為第二層...（Level）

深度：樹中結點的最大層次數，稱為樹的深度或高度（Depth or Height）

森林：是很多互不相交的樹的集合（Forest）

無序樹：樹中任意節(jié)點的子節(jié)點之間沒有順序關系，這種樹稱為無序樹，也稱為自由樹

有序樹：樹中任意節(jié)點的子節(jié)點之間有順序關系，這種樹稱為有序樹

最大樹（最小樹）：每個結點的值都大于（小于）或等于其子結點（如果有的話）值的樹

二叉樹

二叉樹（Binary Tree）是一種特殊的有序樹型結構。

特點：

（1）每個節(jié)點至多有兩棵子樹；

（2）二叉樹的子樹有左右之分；

（3）子樹的次序不能任意顛倒（有序樹）。

性質：

（1）在二叉樹的第i層上至多有2^(i-1)個節(jié)點(i>=1)；

（2）深度為k的二叉樹至多有2^k-1個節(jié)點(k>=1)；

（3）對任何一棵二叉樹，如果其葉子節(jié)點數為N0,度為2的結點數為N2，則N0=N2+1。

特殊二叉樹

滿二叉樹：

所有層的節(jié)點都達到最大數量，葉子除外的所有節(jié)點都有兩個子節(jié)點，所有葉子都在最底一層(k)且數目為2^(k - 1)。即深度k且有2^k - 1個節(jié)點(葉子“長”滿最后一層)，或稱完美二叉樹（Perfect Binary Tree）

______12_______
/ \
__3__ __5__
/ \ / \
_7 6 _9 11
/ \ / \ / \ / \
13 8 1 4 10 2 0 14

完全二叉樹：

如果刪除最底一層的所有葉子它就是滿二叉樹，即除了最后一層，每層節(jié)點都達到最大數量，即有深度k的個節(jié)點數在左閉右開【2^(k-1)+1,2^k-1】區(qū)間內。（Complete Binary Tree）

________3______
/ \
___11___ __4__
/ \ / \
14 7 9 13
/ \ / \ /
2 5 8 6 1

完全二叉樹性質：

1. 具有N個節(jié)點的完全二叉樹的深度為[log2 N]+1，其中[x]為高斯函數，截尾取整。

2. 如果對一棵有n個節(jié)點的完全二叉樹的節(jié)點按層序編號（從第一層到最后一層，每層從左到右），則對任一節(jié)點，有：

（1）如果i=1，則節(jié)點i是二叉樹的根，無雙親；如果i>1,則其雙親節(jié)點為[i/2]；

（2）如果2i>n，則節(jié)點i無左孩子；否則其左孩子是節(jié)點2i；

（3）如果2i+1>n，則節(jié)點i無右孩子；否則其右孩子是節(jié)點2i+1。

其他特殊二叉樹

排序二叉樹

二叉查找樹（Binary Search Tree），也稱二叉搜索樹或有序二叉樹

平衡二叉樹

左右子樹的高度差不大于1的二叉樹，且一定有：它的左、右子樹也都是平衡二叉樹（Self-Balancing Binary Search Tree）

退化樹

退化樹是每個節(jié)點都只有一個孩子的樹，孩子或左或右，或稱病態(tài)樹

斜二叉樹

一種特殊的退化樹，其中全部節(jié)點只有左孩子或右孩子，分別稱左斜二叉樹和右斜二叉樹，功能基本上退化到和鏈表一樣了

霍夫曼樹

帶權路徑最短的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹

B樹

一種對讀寫操作進行優(yōu)化的自平衡的二叉樹查找，能夠保持數據有序，擁有多余兩個子樹

堆 heap

binary heap 是一種完全二叉樹，除了最底層的葉子節(jié)點之外，是填滿的；而且最底層的葉子節(jié)點從左至右是連續(xù)的，不得有空隙。最大堆（最小堆）就是最大（最小）的完全二叉樹。

二叉樹的遍歷

指如何按某種搜索路徑巡防樹中的每個結點，使得每個結點均被訪問一次，而且僅被訪問一次。

常見的遍歷方法有：先序遍歷，中序遍歷，后序遍歷，層序遍歷；一般都使用遞歸算法來實現。

以滿二叉樹為例：

_______1________
/ \
__2__ ___3___
/ \ / \
4 5 _6 _7
/ \ / \ / \ / \
8 9 10 11 12 13 14 15

先序遍歷

若二叉樹為空，為空操作；

否則（1）訪問根節(jié)點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。

遍歷結果： 1 [2 [4 8 9] [5 10 11]] [3 [6 12 13] [7 14 15] “根左右”

中序遍歷

若二叉樹為空，為空操作；

否則（1）中序遍歷左子樹；（2）訪問根結點；（3）中序遍歷右子樹。

遍歷結果： [[8 4 9] 2 [10 5 11]] 1 [[12 6 13] 3 [14 7 15]] “左根右”

后序遍歷

若二叉樹為空，為空操作；

否則（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結點。

遍歷結果： [[8 9 4] [10 11 5] 2] [[12 13 6] [14 15 7] 3] 1 “左右根”

層序遍歷

若二叉樹為空，為空操作；否則從上到下、從左到右按層次進行訪問。

遍歷結果： 1 [2 3] [4 5 6 7] [8 9 10 11 12 13 14 15]

非滿二叉樹的遍歷結果：

________1________
/ \
__2___ ___3
/ \ / \
4 _5 6 7
\ / \ / \
9 10 11 12 15

先序：1 [2 [4 ' 9] [5 10 11]] [3 [6 12 '] [7 ' 15]]

中序：[' 4 9] 2 [10 5 11] 1 [12 6 '] 3 [' 7 15]

后序：[[' 9 4] [10 11 5] 2] [[12 ' 6] [' 15 7] 3] 1

層序：1 [2 3] [4 5 6 7] [' 9 10 11 12 ' ' 15]

注：結果中 ' 只是標記相對于滿二叉樹缺失的子節(jié)點，實際結果并不展現。

Python 實現二叉樹

用Python簡單實現如下二叉樹的遍歷功能，并列出層數和所有葉子：

______A______
/ \
__B__ __C__
/ \ / \
D E F G
/ \ / \ \ \
H I J K L M

代碼如下：

class Node():
 
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
 
    def Preorder(self):
        if self.data is not None:
            print(self.data, end=' ')
        if self.left is not None:
            self.left.Preorder()
        if self.right is not None:
            self.right.Preorder()
 
    def Inorder(self):
        if self.left is not None:
            self.left.Inorder()
        if self.data is not None:
            print(self.data, end=' ')
        if self.right is not None:
            self.right.Inorder()
 
    def Postorder(self):
        if self.left is not None:
            self.left.Postorder()
        if self.right is not None:
            self.right.Postorder()
        if self.data is not None:
            print(self.data, end=' ')
 
    def Height(self):
        if self.data is None:
            return 0
        elif not any([self.left, self.right]):
            return 1
        elif all([not self.left, self.right]):
            return self.right.Height()+1
        elif all([self.left, not self.right]):
            return self.left.Height()+1
        else:
            return max(self.left.Height(), self.right.Height())+1
 
    def Leaves(self):
        if self.data is None:
            return None
        elif not any([self.left, self.right]):
            print(self.data, end=' ')
        elif all([not self.left, self.right]):
            self.right.Leaves()
        elif all([self.left, not self.right]):
            self.left.Leaves()
        else:
            self.left.Leaves()
            self.right.Leaves()
 
 
bt = Node('A')
 
bt.left = Node('B')
bt.right = Node('C')
 
bt.left.left = Node('D')
bt.left.right = Node('E')
bt.right.left = Node('F')
bt.right.right = Node('G')
 
bt.left.left.left = Node('H')
bt.left.left.right = Node('I')
bt.left.right.left = Node('J')
bt.left.right.right = Node('K')
 
bt.right.left.right = Node('L')
bt.right.right.right = Node('M')
 
print('Perorder:')
bt.Preorder()
 
print('\nInorder:')
bt.Inorder()
 
print('\nPostorder:')
bt.Postorder()
 
print('\nTree Height:\n',bt.Height())
 
print('\nLeaves:')
bt.Leaves()

運行結果：

Perorder:
A B D H I E J K C F L G M
Inorder:
H D I B J E K A F L C G M
Postorder:
H I D J K E B L F M G C A
Tree Height: # 實為層數，相當于樓房高度地面一層從0計算高度
4
Leaves:
H I J K L M

要實現二叉樹完整的所有功能，代碼肯定巨長無比。還是找一個優(yōu)秀的第三方庫比較明智?。?！

二叉樹第三方庫 binarytree

使用環(huán)境與安裝

Requirements: Python 3.6+

Installation:
> pip install binarytree

For conda users:
> conda install binarytree -c conda-forge

簡單實例

binarytree.Node() 二叉樹節(jié)點

from binarytree import Node
 
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.right = Node(4)
 
print(root)
 
# 或者： root.pprint()
#
#      __1
#     /   \
#    2     3
#     \
#      4
#

binarytree.tree() 隨機二叉樹

from binarytree import tree
bt = tree(is_perfect=True)
bt.pprint()
 
#    
#              _______14______
#             /               \
#         ___13__            __8__
#        /       \          /     \
#      _9         0        6       3
#     /  \       / \      / \     / \
#    10   12    5   7    4   2   1   11
#

下一篇準備實戰(zhàn)這個第三方庫 binarytree ！

本文的續(xù)篇來了，請點以下鏈接：

——初步探索二叉樹的第三方庫 binarytree