树与树的表示

作者: 掷骰子的求 | 来源:发表于2016-05-19 16:24 被阅读787次

    <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=2
        root+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 = 2
      element[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 = 2
      element[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 = 2
      element[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

    后续内容:

    相关文章

      网友评论

        本文标题:树与树的表示

        本文链接:https://www.haomeiwen.com/subject/xkgmrttx.html