树与树的表示

<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。

1. 树的边数等于结点个数减一
2. 二叉树只有度为零、一和二的结点，可以分别用n0，n1，n2表示。
3. n0+n1＋n2则为树结点个数，n11+n22**则为树的边树
4. n0+n1＋n2－1=n11+n22，即：n0=n2+1

二叉树的抽象数据数据类型

三种遍历方式：

• 先序遍历

1. 先访问其根结点（即输出元素值）
2. 再遍历其左子树
3. 最遍历其右子树

• 中序遍历

  
  

1. 先遍历其左子树
2. 再访问其根结点（即输出元素值）
3. 最后遍历其右子树

• 后序遍历

  
  

1. 先遍历其左子树
2. 再遍历其右子树
3. 最后访问其根结点（即输出元素值）

• 层序遍历

  
  

  按二叉树的在满二叉树上对应编号的先后顺序输出。上述树的层序遍历输出结果为：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

• 二元运算表达式树及其遍历

  
  

源代码: JacobKam-GitHub

后续内容：

• 平衡二叉树与二叉搜索树
• 堆、哈夫曼树和集合
• 树相关算法