数据结构-二叉树遍历

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

  • 参考资料

    https://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000
    <维基等>

  • 更新

    1
    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 类型.
  • 源码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    #!/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=' ')
  • 测试代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    #!/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与伪代码相差不大,没写注释.🧐

  • 代码

    • 递归

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      @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)
    • 循环

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
          @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不为空,循环条件判断时,针对这种情况要做相应处理.
    • 后序遍历循环写法,可以实现的方式不唯一,这里是更改先序遍历,将顺序更改为后序遍历的逆过程,不断将结果压入另一个堆栈,最后从这个堆栈中释放,得到后序遍历的正确顺序.