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())

#!/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),Node(5,None)),Node(3,Node(6,Node(8,Node(9,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,}
    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())