Home > Article > Backend Development > Share the definition and traversal of binary trees implemented in python
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 '中序遍历:' tree.inorder(tree.root) print '层序遍历:' tree.levelorder(tree.root) print '前序遍历:' tree.preorder(tree.root) print '后序遍历:' tree.postorder(tree.root)
Output:
中序遍历 -1 1 3 4 5 层序遍历 3 -1 4 1 5 前序遍历 3 -1 1 4 5 后序遍历 1 -1 5 4 3
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!