Explication détaillée de la méthode d'implémentation de la structure arborescente binaire et de la traversée de l'arbre binaire en Python

Construire un arbre binaire

Utiliser le formulaire d'une classe pour définir un arbre binaire, qui est plus lisible

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 exécute le binaire parcours d'arbre

Exigences :
Code Python pour implémenter l'arbre binaire :
1 Parcours en précommande, imprimer les résultats du parcours
2. les résultats du parcours
3. Parcours post-commande, imprimer le résultat du parcours
4. Traverser en fonction du niveau de l'arbre, imprimer le résultat du parcours
5. pas de nœuds enfants, utilisez 'N' à la place

Méthode :
Utilisez defaultdict ou approvedtuple pour représenter un arbre binaire
Utilisez la méthode StringIO, écrivez le résultat pendant le parcours et enfin imprimez le résultat
Lors de l'impression de la valeur du nœud, si elle est vide, StringIO() écrit 'N'
Utiliser l'accès récursif aux nœuds enfants
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())

Pour des explications plus détaillées sur les méthodes de Python de implémentant des structures d'arbres binaires et la traversée d'arbres binaires, veuillez faire attention au site Web PHP chinois !