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

二叉树的建立

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