Python二叉樹初識(新手也秒懂!)

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

樹

樹（Tree）是n(n0)個(gè)節(jié)點(diǎn)的有限集。

在任意一棵樹中：

（1）有且僅有一個(gè)特定的稱為根（Root）的節(jié)點(diǎn)；

（2）當(dāng)n＞1時(shí)，其余節(jié)點(diǎn)可分m(m＞0)為個(gè)互不相交的有限集T1,T2,...,Tm；

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

Tree:

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

Height=4Leves=5Root

Degree=3Size=26↙

___________________17____________NodeLevel1

//\↙

26______2___9__-ChildLevel2

/\\//\

___019_3___6___2115Level3

//\/\/\

7_16_24_810423Level4

/\//\/\/\

5112813127291822Level5

__________...LeafLeftChildRightChild

術(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)：對應(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ù)，稱為樹的深度或高度（DepthorHeight）

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

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

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

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

二叉樹

二叉樹（BinaryTree）是一種特殊的有序樹型結(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）對任何一棵二叉樹，如果其葉子節(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)(葉子長滿最后一層)，或稱完美二叉樹（PerfectBinaryTree）

______12_______

/\

__3____5__

/\/\

_76_911

/\/\/\/\

完全二叉樹：

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

________3______

/\

___11_____4__

/\/\

147913

/\/\/

25861

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

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

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

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

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

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

其他特殊二叉樹

排序二叉樹

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

平衡二叉樹

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

退化樹

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

斜二叉樹

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

霍夫曼樹

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

B樹

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

堆heap

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

二叉樹的遍歷

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

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

以滿二叉樹為例：

_______1________

/\

__2_____3___

/\/\

45_6_7

/\/\/\/\

89101112131415

先序遍歷

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

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

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

中序遍歷

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

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

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

后序遍歷

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

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

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

層序遍歷

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

遍歷結(jié)果：1[23][4567][89101112131415]

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

________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]

注：結(jié)果中只是標(biāo)記相對于滿二叉樹缺失的子節(jié)點(diǎn)，實(shí)際結(jié)果并不展現(xiàn)。

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

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

______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