树是一种非线性的数据结构。树，它是若干结点的集合，是由唯一的根和若个棵互不相交的子树组成的。其中，每一棵子树又是一棵树，也是由唯一的根结点和若干棵互不相交的子树组成的。由此可知，树的定义是递归的，即在树的定义中又用到了树的定义。要注意的是，树的结点数目可以为0，当为0时，这棵树称为一棵空树，这是一种特殊情况。
1）总结点数等于总分支数加1。
2）
m
m
m叉树第i层上最多有
m
i
−
1
m^{i-1}
mi−1个结点
（
i
≥
1
）
（i\geq1）
（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）总结点数等于总分支数加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/2\rfloor
⌊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)/2\rfloor
⌊(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