-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbinary_tree_basic.py
More file actions
108 lines (92 loc) · 2.59 KB
/
binary_tree_basic.py
File metadata and controls
108 lines (92 loc) · 2.59 KB
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
# -*- coding: utf-8 -*-
'''
Created on 2019/2/26 21:46
file : binary_tree_basic.py
@author: xieweiwei
'''
class Node(object):
"""二叉树节点"""
def __init__(self, elem=-1, lchild=None, rchild=None):
self.elem = elem
self.lchild = lchild
self.rchild = rchild
class Tree(object):
"""二叉树"""
def __init__(self, root=None):
self.root = root
def add(self, elem):
"""为树添加节点"""
node = Node(elem)
# 如果树是空的，则对根节点赋值
if self.root == None:
self.root = node
else:
queue = list()
queue.append(self.root)
while queue:
# 弹出队列的第一个元素
cur = queue.pop(0)
if cur.lchild == None:
cur.lchild = node
return
elif cur.rchild == None:
cur.rchild = node
return
else:
# 如果左右子树都不为空，往判断列表加入子树，循环进行子树的判断
queue.append(cur.lchild)
queue.append(cur.rchild)
def preorder(self, root):
"""递归实现先序遍历"""
if root == None:
return
print(root.elem)
self.preorder(root.lchild)
self.preorder(root.rchild)
def inorder(self, root):
"""递归实现中序遍历"""
if root == None:
return
self.inorder(root.lchild)
print(root.elem)
self.inorder(root.rchild)
def postorder(self, root):
"""递归实现后续遍历"""
if root == None:
return
self.postorder(root.lchild)
self.postorder(root.rchild)
print(root.elem)
def breadth_travel(self, root):
"""利用队列实现树的层次遍历"""
if root == None:
return
queue = list()
queue.append(root)
while queue:
node = queue.pop(0)
print(node.elem)
if node.lchild != None:
queue.append(node.lchild)
if node.rchild != None:
queue.append(node.rchild)
if __name__=='__main__':
t=Tree()
t.add(0)
t.add(1)
t.add(2)
t.add(3)
t.add(4)
t.add(5)
t.add(6)
t.add(7)
t.add(8)
t.add(9)
print("\n广度优先BFS")
t.breadth_travel(t.root)
print("\n前序遍历")
t.preorder(t.root)
print("\n中序遍历")
t.inorder(t.root)
print("\n后序遍历")
t.postorder(t.root)