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

企鹅博客
企鹅博客
企鹅博客
25193
文章
0
评论
2020年8月30日20:32:32 评论 39 views

二叉树的建立

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

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

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

继续阅读
企鹅博客
  • 本文由 发表于 2020年8月30日20:32:32
  • 转载请务必保留本文链接:https://www.qieseo.com/339993.html
css的一些小技巧!页面视觉差!_html/css_WEB-ITnose html教程

css的一些小技巧!页面视觉差!_html/css_WEB-ITnose

相当长的一段时间,现在网站与所谓的“视差”效果一直很受欢迎。 万一你没有听说过这种效果,不同的图像,在不同的方向移动或层主要包括。这导致了一个很好的光学效应,使参观者的注意。 在网页设计中,为了实现这...
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: