树是一种非线性的数据结构。树，它是若干结点的集合，是由唯一的根和若个棵互不相交的子树组成的。其中，每一棵子树又是一棵树，也是由唯一的根结点和若干棵互不相交的子树组成的。由此可知，树的定义是递归的，即在树的定义中又用到了树的定义。要注意的是，树的结点数目可以为0，当为0时，这棵树称为一棵空树，这是一种特殊情况。
树的基本术语- 结点：A、B、C等都是结点，结点不仅包含数据元素，而且包含指向子树的分支。例如，A结点不仅包含数据元素A，而且包含3个指向子树的指针。
- 结点的度：结点拥有的子树个数或者分支的个数。例如，A结点有3棵子树，所以A结点的度为3。
- 树的度：树中各结点度的最大值。如例子中结点度最大为3（A、D结点），最小为0（F、G、I、J 、K、L、M结点），所以树的度为3。
- 叶子结点：又叫作终端结点，指度为0的结点，如F、G，I、J、K、L、M结点都是叶子结点
- 非终端结点：又叫作分支结点，指度不为0的结点，如A、B、C、D、E，H结点都是非终端结点。除了根结点之外的非终端结点，也叫作内部结点，如B、C、D、E、H结点都是内部结点。
- 孩子：结点的子树的根，如A结点的孩子为B、C、D。
- 双亲：与孩子的定义对应，如B，C、D结点的双亲都是A
- 兄弟：同一个双亲的孩子之间互为兄弟。如B、C、D互为兄弟，因为它们都是A结点的孩子。
- 祖先：从根到某结点的路径上的所有结点，都是这个结点的祖先。如K的祖先是A，B，E，因为从A到K的路径为A-B-E-K。
- 子孙：以某结点为根的子树中的所有结点，都是该结点的子孙。如D的子孙为H、I、J、M。
- 层次：从根开始，根为第一层，根的孩子为第二层，根的孩子的孩子为第三层，以此类推。
- 树的高度（或者深度），树中结点的最大层次——如例子中的树共有4层，所以高度为4。
- 结点的深度和高度：
1）结点的深度是从根结到该结点路径上的结点个数。
2）从某结点往下走可能到达多个叶子结点，对应了多条通往这些叶子结点的路径，其中最长的那条路径的长度即为该结点在树中的高度，如结点D的高度为3、就是从D到M的路径长度
3）根结点的高度为树的高度，如结点A，其高度为4，是从A到K（L，M）这条路径的长度，也是整棵树的高度。 - 堂兄弟：双亲在同一层的结点互为堂兄弟。如G和H互为堂兄弟，因为G的双亲是C，H的双亲是D。C和D在同一层上，注意和兄弟的概念的区分。
- 有序树：树中结点的子树从左到右是有次序的，不能交换，这样的树叫作有序树。
- 无序树：树中结点的子树没有顺序，可以任意交换，这样的树叫作无序树。
- 丰满树：丰满树即理想平衡树，要求除最底层外，其他层都是满的。
- 森林：若干棵互丕相交的树的集合。例于中如果把根A去掉，剩下的3棵子树互不相交，它们组成一个森林。
- 顺序存储——适用于满二叉树或完全二叉树
- 链式存储
1）总结点数等于总分支数加1。
2）
m
m
m叉树第i层上最多有
m
i
−
1
m^{i-1}
mi−1个结点
（
i
≥
1
）
（igeq1）
（i≥1）。
3）高为
h
h
h的
m
m
m叉树至多有
(
m
h
−
1
)
/
(
m
−
1
)
(m^{h}-1)/(m-1)
(mh−1)/(m−1)个结点，即满
m
m
m叉树前
h
h
h层有
(
m
h
−
1
)
/
(
m
−
1
)
(m^{h}-1)/(m-1)
(mh−1)/(m−1)个结点。
4）具有
n
n
n个结点“
m
m
m叉树最小高度”或“完全
m
m
m叉树的高度”为
⌈
log
m
[
n
(
m
−
1
)
+
1
]
⌉
lceil {log_m{[n(m-1)+1]}}rceil
⌈logm[n(m−1)+1]⌉。
1）每个结点最多只有两个子树，即二叉树中结点的度只能为0，1，2。
2）子树有左右顺序之分，不能颠倒。
- 满二叉树：在一棵二叉树中，如果所有的分支结点都有左孩子和右孩子结点，并且叶子结点都集中在二叉树的最下一层，则这样的二义树称为满二叉树。
- 完全二叉树：对满二叉树进行编号，约定编号从1开始，从上到下，自左至右进行。如果对一个深度为k，有n个结点的二叉树进行编号后，各结点的编号与深度为k的满二叉树中相同位置上的结点的编号均相同，那么这棵二叉树就是一棵完全二叉树。
1）总结点数等于总分支数加1。
2）二叉树第
i
i
i 层上最多有
2
i
−
1
2^{i-1}
2i−1个结点（i>=1）。
3）高为
h
h
h 的二叉树至多有
2
h
−
1
2^{h}-1
2h−1个结点，即满二叉树前
h
h
h 层有
2
h
−
1
2^{h}-1
2h−1个结点。
4）具有
n
n
n 个结点“二叉树最小高度”或“完全二叉树的高度”为
⌈
log
2
(
n
+
1
)
⌉
lceil {log_2{(n+1)}}rceil
⌈log2(n+1)⌉
5）有
n
n
n 个结点的完全二叉树，对各结点从上到下，从左到右依次编号为（1~n），则第
i
i
i 号结点：
父节点
⌊
i
/
2
⌋
lfloor i/2rfloor
⌊i/2⌋，左孩子
2
i
2i
2i，右孩子
2
i
+
1
2i+1
2i+1，所在层次
⌈
log
2
(
i
+
1
)
⌉
lceil {log_2{(i+1)}}rceil
⌈log2(i+1)⌉。
若从零开始编号，则第
i
i
i 号结点：父节点
⌊
(
i
−
1
)
/
2
⌋
lfloor (i-1)/2rfloor
⌊(i−1)/2⌋，左孩子
2
i
+
1
2i+1
2i+1，右孩子
2
i
+
2
2i+2
2i+2，所在层次
⌈
log
2
(
i
+
2
)
⌉
lceil {log_2{(i+2)}}rceil
⌈log2(i+2)⌉。
class TreeNode():
def __init__(self,data,left=None,right=None):
self.data = data
self.left = left
self.right = right
二叉树的插入（建立）
下面的代码以节点插入的方式，建立了一棵如图所示的二叉树
class TreeNode():
def __init__(self,data,left=None,right=None):
self.data = data
self.left = left
self.right = right
def insertLeft(self,newNode):
if self.left == None:
self.left = TreeNode(newNode)
else :
return False
def insertRight(self,newNode):
if self.right == None:
self.right = TreeNode(newNode)
else :
return False
def moverightchild(self):
return self.right
def moveleftchild(self):
return self.left
def getRightchild(self):
if self.right != None:
return self.right.data
else:
return None
def getLeftchild(self):
if self.left != None:
return self.left.data
else:
return None
def getrootvalue(self):
return self.data
r = TreeNode('a')
r.insertLeft('b')
r.insertRight('g')
k = r.moveleftchild()
k.insertLeft('c')
k.insertRight('d')
m = k.moverightchild()
m.insertLeft('e')
m.insertRight('f')
w = r.moverightchild()
w.insertLeft('h')
print(r.getrootvalue())
print(r.getLeftchild())
print(r.getRightchild())
print(k.getrootvalue())
print(k.getLeftchild())
print(k.getRightchild())
print(m.getrootvalue())
print(m.getLeftchild())
print(m.getRightchild())
print(w.getrootvalue())
print(w.getLeftchild())
print(w.getRightchild())
二叉树的遍历
先序遍历
递归方式：
def preOrderTravel(p):
if p != None:
print(p.data) #visit p
preOrderTravel(p.left)
preOrderTravel(p.right)
以上面建立的二叉树为例，先序遍历，查看结果
print("pre order is:")
preOrderTravel(r)
pre order is: a b c d e f g h中序遍历
递归方式：
def inOrderTravel(p):
if p != None:
inOrderTravel(p.left)
print(p.data) # visit p
inOrderTravel(p.right)
同样以上面建立的二叉树为例，中序遍历，查看结果
print("in order is:")
inOrderTravel(r)
in order is: c b e d f a h g后序遍历
递归方式
def postOrderTravel(p):
if p != None:
postOrderTravel(p.left)
postOrderTravel(p.right)
print(p.data) # visit p
同样以上面建立的二叉树为例，后序遍历，查看结果
print("post order is:")
postOrderTravel(r)
post order is: c e f d b h g a层次遍历
def levelTravel(p):
queue = []
if p != None:
queue.append(p)
while queue:
node = queue.pop(0)
print(node.data)
if node.left != None:
queue.append(node.left)
if node.right != None:
queue.append(node.right)
同样以上面建立的二叉树为例，层次遍历，查看结果
print('level order is:')
levelTravel(r)
level order is: a b g c d h e f
