-
Notifications
You must be signed in to change notification settings - Fork 5
/
next_sibbling_connectivity.py
65 lines (57 loc) · 1.67 KB
/
next_sibbling_connectivity.py
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
from queue import Queue
from tree import Tree
# function to add new node into a next sibbling tree
# @@Param: root node
def insert_next_sibbling(node):
queue = Queue()
queue.enqueue(node.root)
queue.enqueue(None)
while not queue.is_empty():
temp = queue.dequeue()
if not temp:
if not queue.is_empty():
queue.enqueue(None)
else:
temp.next_sibbling = queue.peek()
if temp.left:
queue.enqueue(temp.left)
if temp.right:
queue.enqueue(temp.right)
del queue
return
def insert_next_sibbling_rec(node):
if not node:
return
if node.left:
node.left.next_sibbling = node.right
if node.right:
next_sib = node.next_sibbling
if next_sib:
next_sib = next_sib.left
node.right.next_sibbling = next_sib
insert_next_sibbling_rec(node.left)
insert_next_sibbling_rec(node.right)
# Function to traverse next sibbling tree
# @@Param: root node
def traverse_next_sibbling_tree(tree):
root = tree.root
queue = Queue()
queue.enqueue(root)
while not queue.is_empty():
temp = queue.dequeue()
if temp:
if temp.left:
queue.enqueue(temp.left)
print(temp.data),
current_temp = temp.next_sibbling
while(current_temp):
print(current_temp.data),
current_temp = current_temp.next_sibbling
def main():
tree = Tree()
for i in range(10):
tree.insert(i)
tree.root.next_sibbling = None
insert_next_sibbling_rec(tree.root)
traverse_next_sibbling_tree(tree)
main()