Algorithm/tree.py at master · FeixLiu/Algorithm · GitHub

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
from queue import Queue

class Node:
	def __init__(self, data, lc = None, rc = None):
		self.data = data
		self._lc = lc
		self._rc = rc

	def get_data(self):
		return str(self.data)

	def get_rc(self):
		return rc

	def get_lc(self):
		return lc

def preorder(root):
	print(root.get_data())
	if root.get_lc() != None:
		preorder(root.get_lc())
	if root.get_rc() != None:
		preorder(root.get_rc())

def midorder(root):
	if root.get_lc() != None:
		midorder(root.get_lc())
	print(root.get_data())
	if root.get_rc() != None:
		midorder(root.get_rc())

def lastorder(root):
	if root.get_lc() != None:
		lastorder(root.get_lc())
	if root.get_rc() != None:
		lastorder(root.get_rc())
	print(root.get_data())

def depth_first(root):
	if root is None:
		return
	nodeset = set()
	nodeset.add(root)
	while nodeset:
		cur = nodeset.pop(0)
		print(cur.get_data())
		if root.get_lc() != None:
			nodeset.add(root.get_lc())
		if root.get_rc() != None:
			nodeset.add(root.get_rc())

def width_first(root):
	if root is None:
		return
	nodeset = set()
	nodeset.insert(root)
	while nodeset:
		cur = nodeset.pop(0)
		print(cur.get_data())
		if root.get_lc() != None:
			nodeset.insert(root.get_lc())
		if root.get_rc() != None:
			nodeset.insert(root.get_rc())