二叉樹的建立
使用類的形式定義二叉樹，可讀性更好
|
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
|
class BinaryTree: def __init__(self, root): self.key = root self.left_child = None self.right_child = None def insert_left(self, new_node): if self.left_child == None: self.left_child = BinaryTree(new_node) else: t = BinaryTree(new_node) t.left_child = self.left_child self.left_child = t def insert_right(self, new_node): if self.right_child == None: self.right_child = BinaryTree(new_node) else: t = BinaryTree(new_node) t.right_child = self.right_child self.right_child = t def get_right_child(self): return self.right_child def get_left_child(self): return self.left_child def set_root_val(self, obj): self.key = obj def get_root_val(self): return self.keyr = BinaryTree('a')print(r.get_root_val())print(r.get_left_child())r.insert_left('b')print(r.get_left_child())print(r.get_left_child().get_root_val())r.insert_right('c')print(r.get_right_child())print(r.get_right_child().get_root_val())r.get_right_child().set_root_val('hello')print(r.get_right_child().get_root_val()) |
Python進行二叉樹遍歷
需求：
python代碼實現二叉樹的：
1. 前序遍歷，打印出遍歷結果
2. 中序遍歷，打印出遍歷結果
3. 后序遍歷，打印出遍歷結果
4. 按樹的level遍歷，打印出遍歷結果
5. 結點的下一層如果沒有子節點，以‘N'代替
方法：
使用defaultdict或者namedtuple表示二叉樹
使用StringIO方法，遍歷時寫入結果，最后打印出結果
打印結點值時，如果為空，StringIO（）寫入‘N '
采用遞歸訪問子節點
代碼
|
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
|
#!/usr/bin/env python3# -*- coding: utf-8 -*-# test tree as below:''' 1 / \ / \ / \ / \ 2 3 / \ / \ / \ / \ 4 5 6 N / \ / \ / \ 7 N N N 8 9 / \ / \ / \ N N N N N N '''from collections import namedtuplefrom io import StringIO#define the node structureNode = namedtuple('Node', ['data', 'left', 'right'])#initialize the treetree = Node(1, Node(2, Node(4, Node(7, None, None), None), Node(5, None, None)), Node(3, Node(6, Node(8, None, None), Node(9, None, None)), None))#read and write str in memoryoutput = StringIO()#read the node and write the node's value#if node is None, substitute with 'N 'def visitor(node): if node is not None: output.write('%i ' % node.data) else: output.write('N ')#traversal the tree with different orderdef traversal(node, order): if node is None: visitor(node) else: op = { 'N': lambda: visitor(node), 'L': lambda: traversal(node.left, order), 'R': lambda: traversal(node.right, order), } for x in order: op[x]()#traversal the tree level by leveldef traversal_level_by_level(node): if node is not None: current_level = [node] while current_level: next_level = list() for n in current_level: if type(n) is str: output.write('N ') else: output.write('%i ' % n.data) if n.left is not None: next_level.append(n.left) else: next_level.append('N') if n.right is not None: next_level.append(n.right) else: next_level.append('N ') output.write('\n') current_level = next_levelif __name__ == '__main__': for order in ['NLR', 'LNR', 'LRN']: if order == 'NLR': output.write('this is preorder traversal:') traversal(tree, order) output.write('\n') elif order == 'LNR': output.write('this is inorder traversal:') traversal(tree, order) output.write('\n') else: output.write('this is postorder traversal:') traversal(tree, order) output.write('\n') output.write('traversal level by level as below:'+'\n') traversal_level_by_level(tree) print(output.getvalue()) |
