本文实例讲述了python实现的二叉树定义与遍历算法。分享给大家供大家参考，具体如下：
初学python，需要实现一个决策树，首先实践一下利用python实现一个二叉树数据结构。建树的时候做了处理，保证建立的二叉树是平衡二叉树。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
# -*- coding: utf-8 -*-from collections import dequeclass 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=rightclass 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
中序遍历-11345层序遍历3-1415前序遍历3-1145后序遍历1-1543 |
建立的二叉树如下图所示：
PS：作者的github: https://github.com/zhoudayang
希望本文所述对大家Python程序设计有所帮助。
