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 중국어 웹사이트의 기타 관련 기사를 참조하세요!