树与树的表示
<big>编译环境:python v3.5.0, mac osx 10.11.4</big>
<big>前述内容:</big>
什么是树(Tree)
客观事物中许多事物存在层次关系,而这种分组层次管理机制有利于高效的查找。如:
- 人类社会关系
- 图书信息管理
- 社会组织结构
树的定义
n(n>=0)个节点构成的有限集合
- 当n=0时,称为空树。
- 对于非空树:
- 树根(root),一个特殊的节点,用 r表示
- 其余节点可分为m(m>0)个互不相交的有限集T1,T2....,Tm,其中每个集合本身又是一棵树,称为原树的子树(SubTree)。
根据树的定义如下事例就不是树,因为:
- 子树是互不相交的;
- 除了跟结点外,每个结点都有且只有一个父结点;
- 一棵含有n个结点的树,具有n-1条边
树的基本术语
- 结点的度(Degree):结点的子树个数(如:A的度数为3)
- 树的度:树中所有结点最大的度数(如:上述树的度为3)
- 叶(Leaf)结点:度为0的结点(如:上述树的叶结点为:F,L,H,M,J,K)
- 路径和路径长度:从结点n到结点b的路径为一个结点序列,其路径长度为所包含边的个数(如:A到F的路径为A,B,F,路径长度为2)
- 结点的层次(Level):规定根结点在第一层,其他结点层次为其父结点层次加一。(如:A的层次为1,B的层次为2)
- 树的深度(Depth):树中所有结点的最大层次。(如:上述树的深度为4)
- 森林(Forest):是m(m>=0)互不相交树的集合。对于每个结点而言,其子树的集合即为森林。由此,也可以森林和树相互递归的定义来定义描述树。Tree=(root,F),其中root为根结点,F是m(m>=0)棵树的森林。
树的表示
对于一颗指定的树(如下),我们要怎样在计算机中表示它的信息呢?
由于树中的每个结点的度不统一,所以显然,首先我们想到的是结构体加链表的形式对其进行表示,如下图所示:
我们知道,当一棵树具有n个节点时,它具有n-1条边,而上述的表示方式则需要3n(因为树的度为3)个存储单元来存放树的边。这样一样,2n+1个存储单元就被浪费了。因此为了减少上述浪费,实际编码时我们一般采用儿子-兄弟的表示方法:
-
树的结构体中包含:一个存放结点元素的单元,一个指向第一个儿子的指针和一个指向第一个兄弟的指针。
- 这样一来,我们表示一颗树,则只需要2n个存储单元来存储树的边,仅仅浪费n+1个存储单元。
- 当我们把上述树进行旋转45度时,发现这就是一颗二叉树了,因此大部分的树都可以转化为二叉树的形式进行表示。综上所述,树的算法大多围绕二叉树进行。
二叉树的表示
<big>二叉树是一个有穷的结点集合,基本结构单元由一个包含结点元素、左孩子和右孩子指针的结构体组成。</big>
-
二叉树有五种基本形态
- 二叉树有左右顺序之分,因此下述两棵树不为同一棵树。
- 特殊二叉树:
-
斜二叉树(skewed binary tree):完全向一边偏,形如单向链表。
- 完美二叉树(perfect binary tree)或满二叉树 (full binary tree):没有度为一的结点。(可用顺式存储方式进行存储)
- 完全二叉树(complete binary tree):若对结点为n的完全二叉树从上到下、从左到右进行编号i(1<=i<=n),其编号与满二叉树中编号为i的结点在二叉树中的位置相同。(可用顺式存储方式进行存储)
二叉树的重要性质
- 一颗二叉树的第i层的最大结点数为2^(i-1),i>=1,不适合空树。
- 深度为k的二叉树拥有的最大结点树为2^k-1,k>=1,不适合空树。
- 对于任何非空二叉树T,若n0表示叶结点的个数,n2表示度为2结点的个数,那么它们满足关系n0=n2+1。
- 树的边数等于结点个数减一
- 二叉树只有度为零、一和二的结点,可以分别用n0,n1,n2表示。
- n0+n1+n2则为树结点个数,n11+n22**则为树的边树
- n0+n1+n2-1=n11+n22,即:n0=n2+1
二叉树的抽象数据数据类型
三种遍历方式:- 先序遍历
- 先访问其根结点(即输出元素值)
- 再遍历其左子树
- 最遍历其右子树
-
中序遍历
- 先遍历其左子树
- 再访问其根结点(即输出元素值)
- 最后遍历其右子树
-
后序遍历
- 先遍历其左子树
- 再遍历其右子树
- 最后访问其根结点(即输出元素值)
-
层序遍历
按二叉树的在满二叉树上对应编号的先后顺序输出。上述树的层序遍历输出结果为:ABOCSMQWK
二叉树的顺序存储结构( tree.py)
- 根据完全二叉树和满二叉树的性质,从上到下、从左到右对结点进行编号,我们可以利用数组来存储这两种含有n个结点的特殊二叉树。
- 若我们对一般二叉树也采取上述存储方式,则会造成空间浪费。
- 生成树:
tree =['A','B','O','C','S','M','Q','W','K'] - 是否为空树
def isEmptyTree(tree):
return len(tree) == 0 - 递归算法的遍历:
- 先序遍历
def preOrderTraversal(tree,root): # 递归算法
if root <= len(tree):
if tree[root-1]:
print(tree[root-1]) # 输出元素,访问结点
preOrderTraversal(tree,root=2root) # 遍历左子树
preOrderTraversal(tree,root=2root+1) # 遍历右子树 - 中序遍历
def inOrderTraversal(tree, root): # 中序遍历
if root <= len(tree):
inOrderTraversal(tree, root=2 * root) # 遍历左子树
if tree[root - 1]:
print(tree[root - 1]) # 输出元素,访问结点
inOrderTraversal(tree, root=2 * root + 1) # 遍历右子树 - 后序遍历
def postOrderTraversal(tree, root): # 后序遍历
if root <= len(tree):
postOrderTraversal(tree, root=2 * root) # 遍历左子树
postOrderTraversal(tree, root=2 * root + 1) # 遍历右子树
if tree[root - 1]:
print(tree[root - 1]) # 输出元素,访问结点
- 先序遍历
-
非递归算法遍历(利用堆栈)
- 先序遍历(入栈的时候输出)
import stack_chain
def preOrderTraversal(tree):
store = stack_chain.stackChain() # 建立空栈
node = 1 # 指向树根
while node <= len(tree) or not (stack_chain.isEmpty(store)): # 如果树没有到叶结点,或堆栈不为空
while node <= len(tree): # 遍历左子树
if tree[node-1]:
print(tree[node-1]) # 访问结点,并输出结点
stack_chain.push(store, [tree[node - 1], node]) # 将左子树的元素压入堆栈中
node = 2
if not (stack_chain.isEmpty(store)):
element = stack_chain.pop(store)
node = 2element[1] + 1 # 左子树遍历完后遍历右子树 - 中序遍历(出栈的时候输出)
import stack_chain
def preOrderTraversal(tree):
store = stack_chain.stackChain() # 建立空栈
node = 1 # 指向树根
while node <= len(tree) or not (stack_chain.isEmpty(store)): # 如果树没有到叶结点,或堆栈不为空
while node <= len(tree): # 遍历左子树
stack_chain.push(store, [tree[node - 1], node]) # 将左子树的元素压入堆栈中
node = 2
if not (stack_chain.isEmpty(store)): # 访问结点,并输出
element = stack_chain.pop(store)
if element[0]:
print(element[0])
node = 2element[1] + 1 # 左子树遍历完后遍历右子树 - 后序遍历(第二次出栈的时候输出)
import stack_chain
def preOrderTraversal(tree):
store = stack_chain.stackChain() # 建立空栈
node = 1 # 指向树根
while node <= len(tree) or not (stack_chain.isEmpty(store)): # 如果树没有到叶结点,或堆栈不为空
while node <= len(tree): # 遍历左子树
stack_chain.push(store, [tree[node - 1], node,0]) # 将左子树的元素压入堆栈中,增加一个tag表示元素第几次被弹出
node = 2
if not (stack_chain.isEmpty(store)): # 访问结点,并输出
element = stack_chain.pop(store)
if element[0] and element[2]>0: # 元素第二次被弹出时输入。
print(element[0])
if element[2] ==0:
element[2]=1 # 被弹出一次后改变tag
stack_chain.push(store,element)
node = 2element[1] + 1 # 左子树遍历完后遍历右子树 - 层序遍历
def levelOrderTraversal(tree):
node = 0
while node < len(tree):
if tree[node]:
print(tree[node])
node += 1
二叉树的链式存储结构(tree_chain.py)
由包含结点元素、指向左孩子的指针和指向右孩子指针的结构体连接形成的链表结构。
-
创建二叉树(可以根据先序和中序,或中序和后序,根据先序和中序创建二叉树示意图如下)
-
先序的第一个为根结点
-
我们根据先序的根结点可以在中序遍历中找到,从而得到根结点的两个儿子结点的左右顺序。
-
因此当我们确定一颗二叉树时,中序遍历的顺序是必须的,因为只有它才能告诉我们儿子结点的左右顺序,而前和后序遍历提供的都是根结点的信息。
class BinaryTree(): # the basical structure of binary tree
def init(self, element=None, left=None, right=None):
self.element = element
self.left = left
self.right = right
def createTree(preOrder, inOrder):
if preOrder:
p = BinaryTree() # create a tree node
site = inOrder.index(preOrder[0]) # find root in inOrder sequence and then we can know that
# which set is on the left and which set is on the right
# attach left and right set to root, according to root site in inOder sequence
p.element = preOrder[0]
del preOrder[0]
# recursive
p.left = createTree(preOrder=preOrder[0:site],inOrder=inOrder[0:site])
p.right = createTree(preOrder=preOrder[site:],inOrder=inOrder[site+1:])
return p -
判断是否为空树
def isEmptyTree(root): # hasn't either left child or right child
return root.left is None and root.right is None -
递归算法的遍历:
- 先序遍历
def preOrderTraversal(root): # 递归算法
if root:
print(root.element) # 输出元素,访问结点
preOrderTraversal(root.left) # 遍历左子树
preOrderTraversal(root.right) # 遍历右子树 - 中序遍历
def inOrderTraversal(tree, root): # 中序遍历
if root:
inOrderTraversal(root.left) # 遍历左子树
print(root.element) # 输出元素,访问结点
inOrderTraversal(root.element) # 遍历右子树 - 后序遍历
def postOrderTraversal(tree, root): # 后序遍历
if root:
postOrderTraversal(root.left) # 遍历左子树
postOrderTraversal(root.right) # 遍历右子树
print(root.element) # 输出元素,访问结点
- 先序遍历
- 非递归算法遍历(利用堆栈)
- 先序遍历(入栈的时候输出)
import stack_chain
def preOrderTraversal(tree):
store = stack_chain.stackChain() # 建立空栈
p = tree # 指向树根
while p or not (stack_chain.isEmpty(store)): # 如果树没有到叶结点,或堆栈不为空
while p: # 遍历左子树
print(p.element) # 访问结点,并输出结点
stack_chain.push(store, p) # 将左子树的元素压入堆栈中
p = p.left
if not (stack_chain.isEmpty(store)):
node = stack_chain.pop(store)
p = node.right # 左子树遍历完后遍历右子树 - 中序遍历(出栈的时候输出)
import stack_chain
def preOrderTraversal(tree):
store = stack_chain.stackChain() # 建立空栈
p = tree # 指向树根
while p or not (stack_chain.isEmpty(store)): # 如果树没有到叶结点,或堆栈不为空
while p: # 遍历左子树
stack_chain.push(store, p) # 将左子树的元素压入堆栈中
p = p.left
if not (stack_chain.isEmpty(store)): # 访问结点,并输出
node = stack_chain.pop(store
print(node.element)
p = node.right # 左子树遍历完后遍历右子树 - 后序遍历(第二次出栈的时候输出)
import stack_chain
def preOrderTraversal(tree):
store = stack_chain.stackChain() # 建立空栈
p = tree # 指向树根
count = stack_chain.stackChain() # 记录结点弹出的次数
while p or not (stack_chain.isEmpty(store)): # 如果树没有到叶结点,或堆栈不为空
while p: # 遍历左子树
stack_chain.push(store, p) # 将左子树的元素压入堆栈中
stack_chain.push(count,1) # 增加一个tag表示元素第几次被弹出
p = p.left
if not (stack_chain.isEmpty(store)): # 访问结点,并输出
node = stack_chain.pop(store)
tag = stack_chain.pop(count)
if tag > 1: # 元素第二次被弹出时输入。
print(node.element)
else:
stack_chain.push(count,2) # 被弹出一次后改变tag
stack_chain.push(store,node)
p = node.right # 左子树遍历完后遍历右子树 - 层序遍历
def levelTraversal(tree):
store = queue_chain.queueChain() # 用队列来暂存数据
queue_chain.inQue(store, tree) # 将根结点插入队列中
while not(queue_chain.isEmpty(store)): # 逐个弹出访问
node = queue_chain.outQue(store)
print(node.element)
if node.left:
queue_chain.inQue(store, node.left)
if node.right:
queue_chain.inQue(store,node.right)
二叉树的应用
-
利用后序遍历求二叉树的高度
def getTreeHight(tree):
if tree: # 逐个遍历左边的树和右边的树,取高的最大值
hl = getTreeHight(tree.left)
hr = getTreeHight(tree.right)
hight = max(hl,hr)
return hight+1
else:
return 0 -
二元运算表达式树及其遍历