Python实现二叉树结构与进行二叉树遍历的方法详解

二叉树的建立

使用类的形式定义二叉树，可读性更好

    class BinaryTree:
      def __init__(self, root):
        self.key = root
        self.left_child = None
        self.right_child = None
      def insert_left(self, new_node):
        if self.left_child == None:
          self.left_child = BinaryTree(new_node)
        else:
          t = BinaryTree(new_node)
          t.left_child = self.left_child
          self.left_child = t
      def insert_right(self, new_node):
        if self.right_child == None:
          self.right_child = BinaryTree(new_node)
        else:
          t = BinaryTree(new_node)
          t.right_child = self.right_child
          self.right_child = t
      def get_right_child(self):
        return self.right_child
      def get_left_child(self):
        return self.left_child
      def set_root_val(self, obj):
        self.key = obj
      def get_root_val(self):
        return self.key

    r = BinaryTree('a')
    print(r.get_root_val())
    print(r.get_left_child())
    r.insert_left('b')
    print(r.get_left_child())
    print(r.get_left_child().get_root_val())
    r.insert_right('c')
    print(r.get_right_child())
    print(r.get_right_child().get_root_val())
    r.get_right_child().set_root_val('hello')
    print(r.get_right_child().get_root_val())

Python进行二叉树遍历

需求：
python代码实现二叉树的：
1. 前序遍历，打印出遍历结果
2. 中序遍历，打印出遍历结果
3. 后序遍历，打印出遍历结果
4. 按树的level遍历，打印出遍历结果
5. 结点的下一层如果没有子节点，以'N'代替

方法：
使用defaultdict或者namedtuple表示二叉树
使用StringIO方法，遍历时写入结果，最后打印出结果
打印结点值时，如果为空，StringIO（）写入'N '
采用递归访问子节点
代码

    #!/usr/bin/env python3
    # -*- coding: utf-8 -*-

    # test tree as below:
    ''' 1 / \ / \ / \ / \ 2 3 / \ / \ / \ / \ 4 5 6 N / \ / \ / \ 7 N N N 8 9 / \ / \ / \ N N N N N N '''

    from collections import namedtuple
    from io import StringIO

    #define the node structure
    Node = namedtuple('Node', ['data', 'left', 'right'])
    #initialize the tree
    tree = Node(1,
          Node(2,
             Node(4,
               Node(7, None, None),
               None),
             Node(5, None, None)),
          Node(3,
             Node(6,
               Node(8, None, None),
               Node(9, None, None)),
             None))
    #read and write str in memory
    output = StringIO()


    #read the node and write the node's value
    #if node is None, substitute with 'N '
    def visitor(node):
      if node is not None:
        output.write('%i ' % node.data)
      else:
        output.write('N ')


    #traversal the tree with different order
    def traversal(node, order):
      if node is None:
        visitor(node)
      else:
        op = {
            'N': lambda: visitor(node),
            'L': lambda: traversal(node.left, order),
            'R': lambda: traversal(node.right, order),
        }
        for x in order:
          op[x]()


    #traversal the tree level by level
    def traversal_level_by_level(node):
      if node is not None:
        current_level = [node]
        while current_level:
          next_level = list()
          for n in current_level:
            if type(n) is str:
              output.write('N ')
            else:
              output.write('%i ' % n.data)
              if n.left is not None:
                next_level.append(n.left)
              else:
                next_level.append('N')
              if n.right is not None:
                next_level.append(n.right)
              else:
                next_level.append('N ')

          output.write('\n')
          current_level = next_level


    if __name__ == '__main__':
      for order in ['NLR', 'LNR', 'LRN']:
        if order == 'NLR':
          output.write('this is preorder traversal:')
          traversal(tree, order)
          output.write('\n')
        elif order == 'LNR':
          output.write('this is inorder traversal:')
          traversal(tree, order)
          output.write('\n')
        else:
          output.write('this is postorder traversal:')
          traversal(tree, order)
          output.write('\n')

      output.write('traversal level by level as below:'+'\n')
      traversal_level_by_level(tree)

      print(output.getvalue())