Detailed explanation of the method of implementing binary tree structure and binary tree traversal in Python

Building a binary tree

Use the form of a class to define a binary tree, which is more readable

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 performs binary tree traversal

Requirements:
Python code to implement a binary tree:
1. Preorder traversal, print out the traversal Result
2. In-order traversal, print out the traversal result
3. Post-order traversal, print out the traversal result
4. Traverse according to the level of the tree, print out the traversal result
5. If the next level of the node has no child nodes, Replace 'N' with

Method:
Use defaultdict or namedtuple to represent a binary tree
Use StringIO method, write the result during traversal, and finally print out the result
When printing the node value, if it is empty, StringIO() writes 'N '
Using recursion to access child nodes
Code

#!/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())

For more detailed explanations of Python's methods of implementing binary tree structures and binary tree traversal, please pay attention to the PHP Chinese website for related articles!