binary-tree/binary_tree.py at main · thiagorocha503/binary-tree · 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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
from node import NodeTree
from binary_tree_exception import NodeTypeError


class BinaryTree:

    def __init__(self):
        self.__root: NodeTree = NodeTree()

    def getRoot(self) -> NodeTree:
        return self.__root

    def remove(self, value):
        if self.__root is None:
            return
        if self.__root.getInfo() is None:
            return
        self.__remove(self.__root, value)

    def __remove(self, node: NodeTree, value):
        # case found
        if node.getInfo() == value:
            parent: NodeTree = node.getParent()
            if node.getParent() is None:
                raise Exception("Remoção de nó raiz")
            if (node.getLeft() is None) and (node.getRight() is None):
                # print("Nó folha")
                if node.isLeft():
                    parent.setLeft(None)
                else:
                    parent.setRight(None)
            elif (node.getLeft() is not None) and (node.getRight() is None):
                # print("Subárvore esquerda")
                if node.isLeft():
                    parent.setLeft(node.getLeft())
                else:
                    parent.setRight(node.getRight())
            elif (node.getLeft() is None) and (node.getRight() is not None):
                if node.isLeft():
                    parent.setLeft(node.getRight())
                else:
                    parent.setRight(node.getRight())

                # print("Subárvore direita")
            else:
                raise Exception("Nó com subárvore esquerda e direita")

        else:
            if value < node.getInfo():
                self.__remove(node.getLeft(), value)
            else:
                self.__remove(node.getRight(), value)

    def add(self, value):
        if self.__root is None:
            self.__root = NodeTree(value)
            return
        self.__add(self.__root, value)

    def __add(self, node_: NodeTree, value):
        # inf
        if node_.getInfo() is None:
            node_.setInfo(value)
        else:
            # left
            if value < node_.getInfo():
                if node_.getLeft() is None:
                    node_.setLeft(NodeTree(value))
                else:
                    self.__add(node_.getLeft(), value)
            else:  # right
                if node_.getRight() is None:
                    node_.setRight(NodeTree(value))
                else:
                    self.__add(node_.getRight(), value)

    def hasValue(self, value) -> bool:
        if self.find(value) is None:
            return False
        else:
            return True

    def find(self, value) -> NodeTree or None:
        if self.__root is None:
            return None
        if self.__root.getInfo() is None:
            return None
        return self.__find(self.__root, value)

    def __find(self, node_: NodeTree, value) -> NodeTree or None:
        if node_ is None:
            return None
        if not isinstance(node_, NodeTree):
            raise NodeTypeError(node_)
        if node_.getInfo() == value:
            return node_
        else:
            if value < node_.getInfo():  # node left
                if node_.getLeft() is not None:
                    return self.__find(node_.getLeft(), value)
                else:
                    return None
            else:  # node right
                if node_.getRight() is not None:
                    return self.__find(node_.getRight(), value)
                else:
                    return None

    def clear(self) -> None:
        self.__root = None