Python で実装されたバイナリ ツリーの定義と走査を共有する

この記事では、主に python で実装されたバイナリ ツリーとトラバーサル アルゴリズムを紹介します。Python に基づいて定義されたバイナリ ツリーと、その一般的なトラバーサル操作の実装テクニックを、具体的な例に基づいて分析します。この記事では、Python で実装されたバイナリ ツリー定義とトラバーサル アルゴリズムについて説明します。参考のために皆さんと共有してください。詳細は次のとおりです。

Python の初心者は、まず、Python を使用してバイナリ ツリー データ構造を実装する練習をする必要があります。ツリーを構築するとき、確立されたバイナリ ツリーがバランスの取れたバイナリ ツリーであることを確認するための処理が行われます。

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

出力:

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

確立されたバイナリツリーは以下のようになります:

以上がPython で実装されたバイナリ ツリーの定義と走査を共有するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。