Python二叉树初识(新手也秒懂!)

第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