Partager la définition et le parcours des arbres binaires implémentés en python

Cet article présente principalement la définition de l'arbre binaire et l'algorithme de traversée implémenté par python. Il analyse l'arbre binaire défini sur la base de Python et ses techniques courantes de mise en œuvre des opérations de traversée basées sur des exemples spécifiques. à cela

L'exemple de cet article décrit la définition de l'arbre binaire et l'algorithme de traversée implémenté en python. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Les débutants en Python doivent implémenter un arbre de décision. Tout d'abord, entraînez-vous à utiliser Python pour implémenter une structure de données arborescente binaire. Lors de la construction de l'arbre, un traitement est effectué pour garantir que l'arbre binaire établi est un arbre binaire équilibré.

# -*- 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)

Sortie :

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

L'arbre binaire établi est le suivant :

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!