PyDSA/trees.py at main · dev-dz-pro/PyDSA · 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
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
class Node():
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class Tree():
    def __init__(self, root) -> None:
        self.root = root


    def insert(self, data, node):
        if data > node.data:
            if node.right is None:
                node.right = Node(data)
            else:
                self.insert(data, node.right)
        elif data < node.data:
            if node.left is None:
                node.left = Node(data)
            else:
                self.insert(data, node.left)


    def search(self, data, node):
        if data == node.data:
            return node.data
        elif data > node.data:
            if node.right is None:
                return None
            else:
                return self.search(data, node.right)
        elif data < node.data:
            if node.left is None:
                return None
            else:
                return self.search(data, node.left)


    def inorder(self, node):
        if node.left is not None:
            self.inorder(node.left)
        print(node.data)
        if node.right is not None:
            self.inorder(node.right)

    def preorder(self, node):
        print(node.data)
        if node.left is not None:
            self.preorder(node.left)
        if node.right is not None:
            self.preorder(node.right)

    def postorder(self, node):
        if node.left is not None:
            self.postorder(node.left)
        if node.right is not None:
            self.postorder(node.right)
        print(node.data)

    def breadth_traversal(self, node):
        queue = [node]
        while queue:
            node = queue.pop(0)
            print(node.data)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)


if __name__ == '__main__':
    root = Node(1)
    tree = Tree(root)
    tree.insert(4, root)
    tree.insert(3, root)
    tree.insert(6, root)
    tree.insert(2, root)
    tree.insert(5, root)
    print("-------------------search-------------------")
    print(tree.search(9, root))
    print("-------------------inorder------------------")
    tree.inorder(root)
    print("------------------preorder-------------------")
    tree.preorder(root)
    print("------------------postorder-------------------")
    tree.postorder(root)
    print("------------------breadth_traversal-------------------")
    tree.breadth_traversal(root)