第Python二叉樹初識(新手也秒懂!)目錄樹術語二叉樹特殊二叉樹滿二叉樹：完全二叉樹：完全二叉樹性質：其他特殊二叉樹二叉樹的遍歷先序遍歷中序遍歷后序遍歷層序遍歷Python實現二叉樹二叉樹第三方庫binarytree使用環境與安裝簡單實例總結

樹

樹（Tree）是n(n0)個節點的有限集。

在任意一棵樹中：

（1）有且僅有一個特定的稱為根（Root）的節點；

（2）當n＞1時，其余節點可分m(m＞0)為個互不相交的有限集T1,T2,...,Tm；

其中每一個集合本身又是一棵樹，并且稱為根的子樹（SubTree）。

Tree:

--------------------

Height=4Leves=5Root

Degree=3Size=26↙

___________________17____________NodeLevel1

//\↙

26______2___9__-ChildLevel2

/\\//\

___019_3___6___2115Level3

//\/\/\

7_16_24_810423Level4

/\//\/\/\

5112813127291822Level5

__________...LeafLeftChildRightChild

術語

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

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

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

分支節點：度不為0的節點

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

子節點：結點的子樹的根稱為該節點的孩子（Child）

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

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

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

節點的子孫：以某結點為根的子樹中的所有節點

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

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

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

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

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

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

二叉樹

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

特點：

（1）每個節點至多有兩棵子樹；

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

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

性質：

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

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

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

特殊二叉樹

滿二叉樹：

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

______12_______

/\

__3____5__

/\/\

_76_911

/\/\/\/\

完全二叉樹：

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

________3______

/\

___11_____4__

/\/\

147913

/\/\/

25861

完全二叉樹性質：

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

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

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

（2）如果2in，則節點i無左孩子；否則其左孩子是節點2i；

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

其他特殊二叉樹

排序二叉樹

二叉查找樹（BinarySearchTree），也稱二叉搜索樹或有序二叉樹

平衡二叉樹

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

退化樹

退化樹是每個節點都只有一個孩子的樹，孩子或左或右，或稱病態樹

斜二叉樹

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

霍夫曼樹

帶權路徑最短的二叉樹稱為哈夫曼樹或最優二叉樹

B樹

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

堆heap

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

二叉樹的遍歷

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

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

以滿二叉樹為例：

_______1________

/\

__2_____3___

/\/\

45_6_7

/\/\/\/\

89101112131415

先序遍歷

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

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

遍歷結果：1[2[489][51011]][3[61213][71415]根左右

中序遍歷

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

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

遍歷結果：[[849]2[10511]]1[[12613]3[14715]]左根右

后序遍歷

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

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

遍歷結果：[[894][10115]2][[12136][14157]3]1左右根

層序遍歷

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

遍歷結果：1[23][4567][89101112131415]

非滿二叉樹的遍歷結果：

________1________

/\

__2______3

/\/\

4_567

\/\/\

910111215

先序：1[2[49][51011]][3[612][715]]

中序：[49]2[10511]1[126]3[715]

后序：[[94][10115]2][[126][157]3]1

層序：1[23][4567][910111215]

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

Python實現二叉樹

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

______A______

/\

__B____C__

/\/\

DEFG

/\/\\\

HIJKLM

代碼如下：

classNode():

def__init__(self,data=None,left=None,right=None):

self.data=data

self.left=left

self.right=right

defPreorder(self):

ifself.dataisnotNone:

print(self.data,end='')

ifself.leftisnotNone:

self.left.Preorder()

ifself.rightisnotNone:

self.right.Preorder()

defInorder(self):

ifself.leftisnotNone:

self.left.Inorder()

ifself.dataisnotNone:

print(self.data,end='')

ifself.rightisnotNone:

self.right.Inorder()

defPostorder(self):

ifself.leftisnotNone:

self.left.Postorder()

ifself.rightisnotNone:

self.right.Postorder()

ifself.dataisnotNone:

print(self.data,end='')

defHeight(self):

ifself.dataisNone:

return0

elifnotany([self.left,self.right]):

return1

elifall([notself.left,self.right]):

returnself.right.Height()+1

elifall([self.left,notself.right]):

returnself.left.Height()+1

else:

returnmax(self.left.Height(),self.right.Height())+1

defLeaves(self):

ifsel