binary_search_tree

发表于 | 分类于 | 阅读次数:
字数统计: 591 | 阅读时长 ≈ 3

对树节点 二叉搜索树的简单抽象

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
# -*- coding: utf-8 -*-


class TreeNode(object):
    def __init__(self, key, value, parent=None, left_node=None, right_node=None, balance_factor=0):
        self.key = key
        self.payload = value
        self.left_child = left_node
        self.right_child = right_node
        self.parent = parent
        self.balance_factor = balance_factor

    def has_left_child(self):
        return self.left_child

    def has_right_child(self):
        return self.right_child

    def is_left_child(self):
        return self.parent and self.parent.left_child == self

    def is_right_child(self):
        return self.parent and self.parent.right_child == self

    def is_root(self):
        return not self.parent

    def is_leaf(self):
        return not (self.right_child or self.left_child)

    def has_any_children(self):
        return self.right_child or self.left_child

    def has_both_children(self):
        return self.right_child or self.left_child

    def replace_node_data(self, key, value, lc, rc):
        self.key = key
        self.payload = value
        self.left_child = lc
        self.right_child = rc
        if self.has_left_child():
            self.left_child.parent = self
        if self.has_right_child():
            self.right_child.parent = self


class BinarySearchTree(object):
    def __init__(self):
        self.root = None
        self.size = 0

    def length(self):
        return self.size

    def __len__(self):
        return self.size

    # 中序遍历
    def in_order(self, node):
        if node.left_child:
            self.inorder(node.left_child)
        self.print_node(node)
        if node.right_child:
            self.inorder(node.right_child)

    def level_order(self, node):
        nodes = []
        nodes.append(node)
        while len(nodes) > 0:
            current_node = nodes.pop(0)
            self.print_node(current_node)
            if current_node.left_child:
                nodes.append(current_node.left_child)
            if current_node.right_child:
                nodes.append(current_node.right_child)

    def print_node(self, node):
        if node.parent:
            print([node.key,
                   node.payload,
                   node.parent.key])
        else:
            print([node.key, node.payload])

    # ---------------------  插入节点 ----------------
    def put(self, key, value):
        if self.root:
            self._put(key, value, self.root)
        else:
            self.root = TreeNode(key, value)
        self.size += 1

    def _put(self, key, value, current_node):
        if key < current_node.key:
            if current_node.has_left_child():
                self._put(key, value, current_node.left_child)
            else:
                current_node.left_child = TreeNode(key, value, parent=current_node)

        else:
            if current_node.has_right_child():
                self._put(key, value, current_node.right_child)
            else:
                current_node.right_child = TreeNode(key, value, parent=current_node)
    # ---------------------  插入节点 ----------------

    def __setitem__(self, key, value):
        self.put(key, value)

    # ---------------------  删除节点 ----------------
    def find_min(self):  # Gets minimum node (leftmost leaf) in a subtree
        current_node = self
        while current_node.left_child:
            current_node = current_node.left_child
        return current_node

    def replace_node_in_parent(self, new_value=None):
        if self.parent:
            if self == self.parent.left_child:
                self.parent.left_child = new_value
            else:
                self.parent.right_child = new_value
        if new_value:
            new_value.parent = self.parent

    def binary_tree_delete(self, key):
        if key < self.key:
            self.left_child.binary_tree_delete(key)
        elif key > self.key:
            self.right_child.binary_tree_delete(key)
        else:  # delete the key here
            if self.left_child and self.right_child:  # if both children are present
                successor = self.right_child.find_min()
                self.key = successor.key
                successor.binary_tree_delete(successor.key)
            elif self.left_child:  # if the node has only a *left* child
                self.replace_node_in_parent(self.left_child)
            elif self.right_child:  # if the node has only a *right* child
                self.replace_node_in_parent(self.right_child)
            else:  # this node has no children
                self.replace_node_in_parent(None)
    # ---------------------  删除节点 ----------------

    def get(self, key):
        if self.root:
            res = self._get(key, self.root)
            if res:
                return res.payload
            else:
                return None
        else:
            return None

    def _get(self, key, current_node):
        if not current_node:
            return None
        elif current_node.key == key:
            return current_node
        elif key < current_node.key:
            return self._get(key, current_node.left_child)
        else:
            return self._get(key, current_node.right_child)


def run():
    print('test bst')
    mytree = BinarySearchTree()
    mytree[3] = "red"
    mytree[4] = "blue"
    mytree[2] = "rat"
    mytree[5] = "cat"
    mytree[1] = "dog"

    mytree.level_order(mytree.root)


if __name__ == '__main__':
    run()