Share the definition and traversal of binary trees implemented in python-Python Tutorial-php.cn

Share the definition and traversal of binary trees implemented in python

零下一度

Release： 2017-07-02 11:04:50

Original

1621 people have browsed it

This article mainly introduces the binary tree definition and traversal algorithm implemented by python. It analyzes the binary tree defined based on Python and its common traversal operation implementation techniques based on specific examples. Friends in need can refer to the following

The example in this article describes the binary tree definition and traversal algorithm implemented in python. Share it with everyone for your reference, the details are as follows:

If you are new to python, you need to implement a decision tree. First, practice using python to implement a binary tree data structure. When building the tree, processing is done to ensure that the binary tree established is a balanced binary tree.

# -*- 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 &#39;中序遍历：&#39;
tree.inorder(tree.root)
print &#39;层序遍历：&#39;
tree.levelorder(tree.root)
print &#39;前序遍历：&#39;
tree.preorder(tree.root)
print &#39;后序遍历：&#39;
tree.postorder(tree.root)

Copy after login

Output:

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

Copy after login

The binary tree established is shown below:

The above is the detailed content of Share the definition and traversal of binary trees implemented in python. For more information, please follow other related articles on the PHP Chinese website!