Teilen Sie die Definition und Durchquerung von in Python implementierten Binärbäumen

In diesem Artikel werden hauptsächlich die von Python implementierten Binärbaumdefinitionen und Traversalalgorithmen vorgestellt. Er analysiert den auf Python basierenden Binärbaum und seine allgemeinen Traversaloperationsimplementierungstechniken anhand spezifischer Beispiele dazuDie Beispiele in diesem Artikel beschreiben die in Python implementierte Binärbaumdefinition und den Traversalalgorithmus. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

Einsteiger in Python müssen zunächst einen Entscheidungsbaum implementieren. Üben Sie zunächst die Verwendung von Python zur Implementierung einer binären Baumdatenstruktur. Beim Erstellen des Baums wird eine Verarbeitung durchgeführt, um sicherzustellen, dass der erstellte Binärbaum ein ausgeglichener Binärbaum ist.

Ausgabe:

# -*- coding: utf-8 -*-
from collections import deque
class Node:
  def init(self,val,left=None,right=None):
    self.val=val
    self.left=left
    self.right=right
  #setter and getter
  def get_val(self):
    return self.val
  def set_val(self,val):
    self.val=val
  def get_left(self):
    return self.left
  def set_left(self,left):
    self.left=left
  def get_right(self):
    return self.right
  def set_right(self,right):
    self.right=right
class Tree:
  def init(self,list):
    list=sorted(list)
    self.root=self.build_tree(list)
  #递归建立平衡二叉树
  def build_tree(self,list):
    l=0
    r=len(list)-1
    if(l>r):
      return None
    if(l==r):
      return Node(list[l])
    mid=(l+r)/2
    root=Node(list[mid])
    root.left=self.build_tree(list[:mid])
    root.right=self.build_tree(list[mid+1:])
    return root
  #前序遍历
  def preorder(self,root):
    if(root is None):
      return
    print root.val
    self.preorder(root.left)
    self.preorder(root.right)
  #后序遍历
  def postorder(self,root):
    if(root is None):
      return
    self.postorder(root.left)
    self.postorder(root.right)
    print root.val
  #中序遍历
  def inorder(self,root):
    if(root is None):
      return
    self.inorder(root.left)
    print root.val
    self.inorder(root.right)
  #层序遍历
  def levelorder(self,root):
    if root is None:
      return
    queue =deque([root])
    while(len(queue)>0):
      size=len(queue)
      for i in range(size):
        node =queue.popleft()
        print node.val
        if node.left is not None:
          queue.append(node.left)
        if node.right is not None:
          queue.append(node.right)
list=[1,-1,3,4,5]
tree=Tree(list)
print '中序遍历：'
tree.inorder(tree.root)
print '层序遍历：'
tree.levelorder(tree.root)
print '前序遍历：'
tree.preorder(tree.root)
print '后序遍历：'
tree.postorder(tree.root)

Der erstellte Binärbaum sieht wie folgt aus:

中序遍历
-1
1
3
4
5
层序遍历
3
-1
4
1
5
前序遍历
3
-1
1
4
5
后序遍历
1
-1
5
4
3

Das obige ist der detaillierte Inhalt vonTeilen Sie die Definition und Durchquerung von in Python implementierten Binärbäumen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!