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’代替

立即学习“Python免费学习笔记（深入）”；

方法：
使用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 namedtuplefrom io import StringIO #define the node structureNode = namedtuple('Node', ['data', 'left', 'right'])#initialize the treetree = 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 memoryoutput = 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 orderdef 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 leveldef 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('')      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('')    elif order == 'LNR':      output.write('this is inorder traversal:')      traversal(tree, order)      output.write('')    else:      output.write('this is postorder traversal:')      traversal(tree, order)      output.write('')   output.write('traversal level by level as below:'+'')  traversal_level_by_level(tree)   print(output.getvalue())

登录后复制

更多Python实现二叉树结构与进行二叉树遍历的方法详解相关文章请关注PHP中文网！