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

術(shù)語

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

根：樹和子樹的“頂點(diǎn)”（Root）

度：節(jié)點(diǎn)擁有的子樹數(shù)量稱為節(jié)點(diǎn)的度（Degree）；樹的度是指樹內(nèi)個(gè)結(jié)點(diǎn)的度的最大值

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

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

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

父節(jié)點(diǎn)：對(duì)應(yīng)子節(jié)點(diǎn)上一層(level)節(jié)點(diǎn)稱為該節(jié)點(diǎn)的雙親（Parent）

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

節(jié)點(diǎn)的祖先：是從根到該結(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)

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

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

深度：樹中結(jié)點(diǎn)的最大層次數(shù)，稱為樹的深度或高度（Depth or Height）

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

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

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

最大樹（最小樹）：每個(gè)結(jié)點(diǎn)的值都大于（小于）或等于其子結(jié)點(diǎn)（如果有的話）值的樹

二叉樹

二叉樹（Binary Tree）是一種特殊的有序樹型結(jié)構(gòu)。

特點(diǎn)：

（1）每個(gè)節(jié)點(diǎn)至多有兩棵子樹；

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

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

性質(zhì)：

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

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

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

特殊二叉樹

滿二叉樹：

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

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

完全二叉樹：

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

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

完全二叉樹性質(zhì)：

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

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

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

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

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

其他特殊二叉樹

排序二叉樹

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

平衡二叉樹

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

退化樹

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

斜二叉樹

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

霍夫曼樹

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

B樹

一種對(duì)讀寫操作進(jìn)行優(yōu)化的自平衡的二叉樹查找，能夠保持?jǐn)?shù)據(jù)有序，擁有多余兩個(gè)子樹

堆 heap

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

二叉樹的遍歷

指如何按某種搜索路徑巡防樹中的每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。

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

以滿二叉樹為例：

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

先序遍歷

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

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

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

中序遍歷

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

否則（1）中序遍歷左子樹；（2）訪問根結(jié)點(diǎn)；（3）中序遍歷右子樹。

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

后序遍歷

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

否則（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點(diǎn)。

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

層序遍歷

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

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

非滿二叉樹的遍歷結(jié)果：

________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é)果中 ' 只是標(biāo)記相對(duì)于滿二叉樹缺失的子節(jié)點(diǎn)，實(shí)際結(jié)果并不展現(xiàn)。

Python 實(shí)現(xiàn)二叉樹

用Python簡單實(shí)現(xiàn)如下二叉樹的遍歷功能，并列出層數(shù)和所有葉子：

______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()

運(yùn)行結(jié)果：

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: # 實(shí)為層數(shù)，相當(dāng)于樓房高度地面一層從0計(jì)算高度
4
Leaves:
H I J K L M

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

二叉樹第三方庫 binarytree

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

Requirements: Python 3.6+

Installation:
> pip install binarytree

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

簡單實(shí)例

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

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() 隨機(jī)二叉樹

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)備實(shí)戰(zhàn)這個(gè)第三方庫 binarytree ！

本文的續(xù)篇來了，請(qǐng)點(diǎn)以下鏈接：

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