А.1 ФАЙЛ NODE.PY
1: class Node:
2: def __init__(self, data):
3: self.value = data
4: self.left = None
5: self.right = None
6:
7:
8: def insert(self, data):
9: if self.value == data:
10: return False
11:
12: elif data < self.value:
13: if self.left:
14: return self.left.insert(data)
15: else:
16: self.left = Node(data)
17: return True
18:
19: else:
20: if self.right:
21: return self.right.insert(data)
22: else:
23: self.right = Node(data)
24: return True
25:
26:
27: def search(self, data):
28: If self.value == data:
29: return True
30: elif self.value > data:
31: if self.left:
32: return self.left.search(data)
33: else:
34: return False
35: else:
36: if self.right:
37: return self.right.search(data)
38: else:
39: return False
40:
41:
42: def getSize(self):
43: if self.left and self.right:
44: return 1 + self.left.getSize() + self.right.getSize()
45: elif self.left:
46: return 1 + self.left.getSize()
47: elif self.right:
48: return 1 + self.right.getSize()
49: else:
50: return 1
51:
52:
53: def getHeight(self):
54: if self.left and self.right:
55: return 1 + max(self.left.getHeight(), self.right.getHeight())
56: elif self.left:
57: return 1 + self.left.getHeight()
58: elif self.right:
59: return 1 + self.right.getHeight()
60: else:
61: return 1
62:
63:
64: def preorder(self):
65: print(str(self.value), end=' ')
66: if self.left:
67: self.left.preorder()
68: if self.right:
69: self.right.preorder()
70:
71:
72: def postorder(self):
73: if self.left:
74: self.left.postorder()
75: if self.right:
76: self.right.postorder()
77: print(str(self.value), end=' ')
78:
79:
80: def inorder(self):
81: if self.left:
82: self.left.inorder()
83: print(str(self.value), end=' ')
84: if self.right:
85: self.right.inorder()
86:
87:
88: def getTreeView(self):
89: if self.left:
90: if self.right:
91: return f"({self.left.getTreeView()} {self.value} {self.right.getTreeView()})"
92: else:
93: return f"({self.left.getTreeView()} {self.value} None)"
94: elif self.right:
95: return f"(None {self.value} {self.right.getTreeView()})"
96: else:
97: return f"(None {self.value} None)"
А.2 ФАЙЛ TREE.PY
1: from node import Node
2:
3: class Tree:
4:
5: def __init__(self):
6: self.root = None
7:
8: def insert(self, data):
9: if self.root:
10: return self.root.insert(data)
11: else:
12: self.root = Node(data)
13: return True
14:
15: def search(self, data):
16: if self.root:
17: return self.root.search(data)
18: else:
19: return False
20:
21: def getHeight(self):
22: if self.root:
23: return self.root.getHeight()
24: else:
25: return 0
26:
27: def getSize(self):
28: if self.root:
29: return self.root.getSize()
30: else:
31: return 0
32:
33: def getTreeView(self):
34: if self.root:
35: print(self.root.getTreeView())
36:
37: def preorder(self):
38: if self.root:
39: self.root.preorder()
40:
41: def postorder(self):
42: if self.root:
43: self.root.postorder()
44:
45: def inorder(self):
46: if self.root:
47: self.root.inorder()
48:
49: def remove(self, data):
50: # tree is empty?
51: if self.root is None:
52: return False
53:
54: # remove root
55: if self.root.value == data:
56: if self.root.left is None and self.root.right is None:
57: self.root = None
58: elif self.root.left and self.root.right is None:
59: self.root = self.root.left
60: elif self.root.left is None and self.root.right:
61: self.root = self.root.right
62: elif self.root.left and self.root.right:
63: erasing_node_parent = self.root
64: erasing_node = self.root.right
65: while erasing_node.left:
66: erasing_node_parent = erasing_node
67: erasing_node = erasing_node.left
68:
69: if erasing_node.right:
70: if erasing_node_parent.value > erasing_node.value:
71: erasing_node_parent.left = erasing_node.right
72: elif erasing_node_parent.value < erasing_node.value:
73: erasing_node_parent.right = erasing_node.right
74: else:
75: if erasing_node.value < erasing_node_parent.value:
76: erasing_node_parent.left = None
77: else:
78: erasing_node_parent.right = None
79: self.root.value = erasing_node.value
80:
81: return True
82:
83: parent = None
84: node = self.root
85:
86: # searching for node
87: while node and node.value!= data:
88: parent = node
89: if data < node.value:
90: node = node.left
91: elif data > node.value:
92: node = node.right
93:
94: # not found, False
95: if node is None:
96: return False
97:
98: # removal node has 0 children
99: if node.left is None and node.right is None:
100: if data < parent.value:
101: parent.left = None
102: else:
103: parent.right = None
104: return True
105:
106: # case 2: removal has left child
107: elif node.left and node.right is None:
108: if data < parent.value:
109: parent.left = node.left
110: else:
111: parent.right = node.left
112: return True
113:
114: # case 3: removal has right child
115: elif node.left is None and node.right:
116: if data < parent.value:
117: parent.left = node.right
118: else:
119: parent.right = node.right
120: return True
121:
122: # case 4: removal has 2 children
123: else:
124: erasing_node_parent = node
125: erasing_node = node.right
126: while erasing_node.left:
127: erasing_node_parent = erasing_node
128: erasing_node = erasing_node.left
129:
130: node.value = erasing_node.value
131: if erasing_node.right:
132: if erasing_node_parent.value > erasing_node.value:
133: erasing_node_parent.left = erasing_node.right
134: elif erasing_node_parent.value < erasing_node.value:
135: erasing_node_parent.right = erasing_node.right
136: else:
137: if erasing_node.value < erasing_node_parent.value:
138: erasing_node_parent.left = None
139: else:
140: erasing_node_parent.right = None
А.3 ФАЙЛ MAIN.PY
1: from tree import Tree
2: import time
3: import random
4: import os
5:
6: def showMsg(msg):
7: print(msg)
8: input('Press any button to continue...')
9: os.system('cls')
10:
11:
12: def main():
13: tree = None
14: while True:
15:
16: print('\n\tBinary Search Tree')
17: print('1. Create the Tree')
18: print('2. Show the Tree')
19: print('3. Clear the Tree')
20: print('4. Add node to the Tree')
21: print('5. Remove node from the Tree')
22: print('6. Find node')
23: print('7. Evaluate height of the Tree')
24: print('8. Evaluate size of the Tree')
25: print('9. Preorder Tree traversal')
26: print('10. Postorder Tree traversal')
27: print('11. Inorder Tree traversal')
28: print('12. Random Tree')
29: print('0. Exit')
30:
31: ch = input('\nInput number of action you want: ')
32:
33: try:
34: ch = int(ch)
35: except ValueError:
36: showMsg('Wrong choice!!!')
37: continue
38: if ch < 0 or ch > 12:
39: showMsg('Wrong choice!!!')
40: continue
41:
42: os.system('cls')
43:
44: if ch == 1:
45: if tree is None:
46: data = input('Value of the root: ')
47: try:
48: data = int(data)
49: except ValueError:
50: showMsg('Can\'t convert input value to int. Try again with correct input')
51: continue
52: tree = Tree()
53: tree.insert(data)
54: else:
55: showMsg('Tree already exists!!!')
56:
57: elif ch == 2:
58: if tree is None or tree.getSize() == 0:
59: showMsg('Tree is empty!!!')
60: continue
61: else:
62: tree.getTreeView()
63:
64: elif ch == 3:
65: if tree is None or tree.getSize() == 0:
66: showMsg('Tree is empty!!!')
67: continue
68: else:
69: tree = None
70:
71: elif ch == 4:
72: if tree is not None:
73: data = input('Value to insert: ')
74: try:
75: data = int(data)
76: except ValueError:
77: showMsg('Can\'t convert input value to int. Try again with correct input')
78: continue
79: if tree.insert(data) == False:
80: showMsg('Value already exists!!!')
81: continue
82: else:
83: showMsg('Tree is empty!!!')
84:
85: elif ch == 5:
86: if tree is not None:
87: data = input('Value to delete: ')
88: try:
89: data = int(data)
90: except ValueError:
91: showMsg('Incorrect input')
92: continue
93: if tree.remove(data) == False:
94: showMsg(f'Node with value {data} doesn\'t exist!!!')
95: continue
96: else:
97: showMsg('Tree is empty!!!')
98:
99: elif ch == 6:
100: if tree is not None:
101: data = input('Value to find: ')
102: try:
103: data = int(data)
104: except ValueError:
105: showMsg('Incorrect input')
106: continue
107: if tree.search(data) == False:
108: showMsg(f'Node with value {data} not found!!!')
109: continue
110: else:
111: showMsg(f'Node with value {data} has been found')
112: else:
113: showMsg('Tree is empty!!!')
114:
115: elif ch == 7:
116: if tree is not None:
117: showMsg(f'Height of the tree: {tree.getHeight()}')
118: else:
119: showMsg('Create tree firstly!!!')
120:
121: elif ch == 8:
122: if tree is not None:
123: showMsg(f'Size of the tree: {tree.getSize()}')
124: else:
125: showMsg('Create tree firstly!!!')
126:
127: elif ch == 9:
128: if tree is not None:
129: tree.preorder()
130: else:
131: showMsg('Create tree firstly!!!')
132:
133: elif ch == 10:
134: if tree is not None:
135: tree.postorder()
136: else:
137: showMsg('Create tree firstly!!!')
138:
139: elif ch == 11:
140: if tree is not None:
141: tree.inorder()
142: else:
143: showMsg('Create tree firstly!!!')
144:
145: elif ch == 12:
146: size = random.randint(3,15)
147: tree = Tree()
148: for _ in range(size):
149: tree.insert(random.randint(1,100))
150: showMsg('Random tree has been created successfully')
151:
152: elif ch == 0:
153: exit(0)
154:
155: if __name__ == '__main__':
156: main()
А.4 ФАЙЛ TESTS.PY
1: from tree import Tree
2: import time
3: import random
4:
5: file_obj=open('result.txt', 'a')
6: file_obj.write('size:time(mcs)\n')
7: file_obj.close()
8:
9: for i in range(1,101):
10: file_obj = open('result.txt', 'a')
11: size = i * 10000
12: root = Tree()
13: for _ in range(size):
14: while True:
15: value = random.randint(0, size * 20)
16: if root.insert(value) == True:
17: break
18: totalTime = 0
19: for _ in range(20):
20: start = time.time_ns()
21: root.getSize()
22: end = time.time_ns()
23: totalTime += round((end - start) / 1000)
24: print(f'Iteration #{i}: Time spent to count {size} elements: {round(totalTime / 20)}\n')
25: file_obj.write(f'{size}:{round(totalTime / 20)}\n')
26: del root
27: file_obj.close()