数据结构-二叉树遍历

• 数据结构-二叉树遍历部分,包括 python 源代码

• 参考资料

  https://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000

  <维基等>

• 更新

  19.03.05 初始
  

导语

• 贪心法涉及到的图论部分,头大,计算下工作量,基本等于数据结构部分重新刷完了.
• 直接开始数据结构部分,图论等按顺序来.
• 下一篇是排序.

二叉树基础

• 二叉树（英语：Binary tree）是每个节点最多只有两个分支的树结构。通常分支被称作“左子树”或“右子树”.
• 满二叉树/完全二叉树
  • 深度为 $k$ 的二叉树最多拥有 $2^{k+1}-1$ 个节点.(根节点的深度定义为$k_0 = 0$)
  • 深度为 $k$ 拥有 $2^{k+1}-1$ 个节点的二叉树称为满二叉树(每一层都满员)
  • 而深度为 $k$ 有 $n$ 个节点的二叉树,当且仅当每个节点都与深度为 $k$ 的满二叉树序号由1到n一一对应时,称为完全二叉树.(前k-1层,满员,第k层,叶子节点聚集在左侧,可能满也可能不满.)

• 二叉树存储

  • 数组
    • 第k个节点,对应左子树为2k,右子树为2k+1.第0个节点置空.(随意)
    • 非常方便寻址,且块存储,不易碎片化.
    • 对于非满/完全二叉树,有可能存在空间浪费.
  • 二叉链表
    • 仿照二叉树结构,在数据结构中加入左子树/右子树地址.
    • 节约空间,易碎片化,寻址等稍繁琐.
  • 数据结构中可能会用到两种,这里随机生成一个数组,且在数据结构定义中加入左/右子树地址,并链接.
  • 数据值域因为python为动态语言,这里限定仅为 int 和 str 类型.

• 源码:

  #!/usr/bin/python3
  import random
  import copy
  import string
  
  
  class BtNode(object):
      def __init__(self, value=0, leftBt=None, rightBt=None):
          self.value = value
          self.lchild = leftBt
          self.rchild = rightBt
  
      @property
      def value(self):
          return self._value
  
      @value.setter
      def value(self, values):
          if not (isinstance(values, int) or isinstance(values, str)):
              raise ValueError('value must be an int or str!')
          self._value = values
  
      @property
      def lchild(self):
          return self._lchild
  
      @lchild.setter
      def lchild(self, leftBt):
          if not (isinstance(leftBt, BtNode) or (leftBt is None)):
              raise ValueError('leftBt must be BtNode')
          self._lchild = leftBt
  
      @property
      def rchild(self):
          return self._rchild
  
      @rchild.setter
      def rchild(self, rightBt):
          if not (isinstance(rightBt, BtNode) or (rightBt is None)):
              raise ValueError('rightBt must be BtNode')
          self._rchild = rightBt
  
  
  class Btree(object):
      def __init__(self, len=50):
          self.__len = len
          self.__arr = [BtNode() for i in range(self.__len)]
          self.__link()
  
      def Cr_int(self):
          self.__arr = list(map(self.__randomint, self.__arr))
          return copy.deepcopy(self.__arr)
  
      def Cr_str(self, len=50):
          self.__arr = list(map(self.__randomstr, self.__arr))
          return copy.deepcopy(self.__arr)
  
      def __link(self):
          for i in range(self.__len - 1, 1, -1):
              if (i % 2) == 1:
                  self.__arr[i // 2].rchild = self.__arr[i]
              else:
                  self.__arr[i // 2].lchild = self.__arr[i]
  
      def __randomint(self, btNode):
          btNode.value = random.randint(0, 100)
          return btNode
  
      def __randomstr(self, btNode):
          btNode.value = ''.join(random.choices(string.ascii_lowercase, k=1))
          return btNode
  
      @classmethod
      def visit(self, node):
          return print(node.value, end=' ')
  

• 测试代码

  #!/usr/bin/python3
  import unittest
  from bt_base import BtNode, Btree
  
  
  class test_bt(unittest.TestCase):
      def test_BtNode(self):
          tmp = BtNode()
          self.assertEqual(tmp.value, 0)
          self.assertEqual(tmp.lchild, None)
          self.assertEqual(tmp.rchild, None)
          with self.assertRaises(ValueError):
              tmp.value = 1.3
          with self.assertRaises(ValueError):
              tmp.lchild = 1.3
          with self.assertRaises(ValueError):
              tmp.rchild = 1.3
  
      def test_Btree(self):
          bt = Btree()
          tmp = bt.Cr_int()
          for node in tmp:
              self.assertTrue(isinstance(node, BtNode))
              self.assertTrue(isinstance(node.value, int))
              self.assertTrue(isinstance(node.lchild, (BtNode, type(None))))
              self.assertTrue(isinstance(node.rchild, (BtNode, type(None))))
          tmp = bt.Cr_str()
          for node in tmp:
              self.assertTrue(isinstance(node, BtNode))
              self.assertTrue(isinstance(node.value, str))
              self.assertTrue(isinstance(node.lchild, (BtNode, type(None))))
              self.assertTrue(isinstance(node.rchild, (BtNode, type(None))))
  

二叉树遍历

• 二叉树遍历按遍历方式分为3种,每种又有递归和循环两种写法.

  • 先序遍历: 节点值->左子树->右子树
  • 中序遍历: 左子树->节点值->右子树
  • 后序遍历: 左子树->右子树->节点值

• 代码比较简单,配合python与伪代码相差不大,没写注释.

• 代码

  • 递归

    @classmethod
    def Pre_Order_Re(self, root):
        if root:
            Btree.visit(root)
        if root.lchild:
            self.Pre_Order_Re(root.lchild)
        if root.rchild:
            self.Pre_Order_Re(root.rchild)
    
    @classmethod
    def In_Order_Re(self, root):
        if root.lchild:
            self.In_Order_Re(root.lchild)
        if root:
            Btree.visit(root)
        if root.rchild:
            self.In_Order_Re(root.rchild)
    
    @classmethod
    def Post_Order_Re(self, root):
        if root.lchild:
            self.Post_Order_Re(root.lchild)
        if root.rchild:
            self.Post_Order_Re(root.rchild)
        if root:
            Btree.visit(root)
    

  • 循环

        @classmethod
    def Pre_Order_loop(self, root):
        stack = []
        stack.append(root)
        while stack:
            p = stack.pop()
            Btree.visit(p)
            if p.rchild:
                stack.append(p.rchild)
            if p.lchild:
                stack.append(p.lchild)
    
    @classmethod
    def In_Order_loop(self, root):
        stack = []
        p = root
        while stack or p:
            while p:
                stack.append(p)
                p = p.lchild
            if stack:
                p = stack.pop()
                Btree.visit(p)
                p = p.rchild
    
    @classmethod
    def Post_Order_loop(self, root):
        stack = []
        stackb = []
        stack.append(root)
        while stack:
            p = stack.pop()
            stackb.append(p)
            if p.lchild:
                stack.append(p.lchild)
            if p.rchild:
                stack.append(p.rchild)
        while stackb:
            Btree.visit(stackb.pop())
    

• 说明:

  • 递归代码非常明了,但没有尾递归优化的语言,可能存在堆栈溢出.
  • 先序遍历循环写法,利用了一个堆栈来实现,受益于python,与伪代码非常接近.
  • 中序遍历循环写法,与先序遍历循环相似,特殊一点的时,在遍历完根节点的左子树时,堆栈为空,但p不为空,循环条件判断时,针对这种情况要做相应处理.
  • 后序遍历循环写法,可以实现的方式不唯一,这里是更改先序遍历,将顺序更改为后序遍历的逆过程,不断将结果压入另一个堆栈,最后从这个堆栈中释放,得到后序遍历的正确顺序.