Detaillierte Erläuterung der Methode zur Implementierung der Binärbaumstruktur und der Binärbaumdurchquerung in Python

Erstellen eines Binärbaums

Verwenden Sie die Form einer Klasse, um einen Binärbaum zu definieren, der besser lesbar ist

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 führt Binärfunktionen aus Baumdurchquerung

Anforderungen:
Python-Code zur Implementierung des Binärbaums:
1. Durchquerung vorbestellen, Durchlaufergebnisse ausdrucken
2 die Durchlaufergebnisse
3. Nach der Durchquerung das Durchlaufergebnis ausdrucken
4. Durchlauf entsprechend der Ebene des Baums ausdrucken
5 Keine untergeordneten Knoten, verwenden Sie stattdessen „N“

Methode:
Verwenden Sie defaultdict oder benanntes Tupel, um einen Binärbaum darzustellen
Verwenden Sie die StringIO-Methode, schreiben Sie das Ergebnis während der Durchquerung und drucken Sie das Ergebnis schließlich aus
Wenn der Knotenwert gedruckt wird und dieser leer ist, schreibt StringIO() „N“
Rekursiven Zugriff auf untergeordnete Knoten verwenden
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())

Für detailliertere Erklärungen der Python-Methoden von Wenn Sie Binärbaumstrukturen und Binärbaumdurchquerung implementieren, beachten Sie bitte die chinesische PHP-Website!