札记之PHP实现二叉搜索树

Posted on | In

什么是二叉树搜索树：

二叉搜索树又被称为二叉排序树，那么它本身也是一棵二叉树，那么满足以下性质的二叉树就是二叉搜索树：

  • 若左子树不为空，则左子树上左右节点的值都小于根节点的值
  • 若它的右子树不为空，则它的右子树上所有的节点的值都大于根节点的值
  • 它的左右子树也要分别是二叉搜索树

基于下图介绍二叉搜索树相关操作：

札记之PHP实现二叉搜索树

二叉搜索树的查找操作
  • 我们先取根节点，如果它等于我们要查找的数据，那就返回；
  • 如果要查找的数据比根节点的值小，那就在左子树中递归查找；
  • 如果要查找的数据比根节点的值大，那就在右子树中递归查找；
二叉搜索树的插入操作
  • 如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；
  • 如果不为空，就再递归遍历右子树，查找插入位置；
  • 如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；
二叉搜索树的删除操作
  • 如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为 null；
  • 如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了；
  • 如果要删除的节点有两个子节点，我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点；
二叉搜索树最小值
  • 循环左侧节点，找对最小值；
二叉搜索树最大值
  • 循环右侧节点，找对最大值；
获取层数
  • 递归左右高度，取最大值+1；

完整代码：

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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
class Node 
{
    public $left;
    public $right;
    public $data;

    public function __construct($data) 
    {
        $this->data = $data;
        $this->left = null;
        $this->right = null;
    }
}

class BinaryTree
{
    public $root = null;
 
    //插入节点
    public function insert($data)
    {
        $newNode = new Node($data);
        if ($this->root == null) {
            $this->root = $newNode;
        } else {
            $this->insertNode($this->root, $newNode);
        }
    }

    private function insertNode($node, $newNode) 
    {
        if ($newNode->data < $node->data) {
            if ($node->left == null) {
                $node->left = $newNode;
            } else {
                $this->insertNode($node->left, $newNode);
            }
        } else {
            if ($node->right == null) {
                $node->right = $newNode;
            } else {
                $this->insertNode($node->right, $newNode);
            }
        }
    }

    //查询
    public function search($data)
    {
        return $this->searchNode($this->root, $data);
    }

    private function searchNode($node, $data)
    {
        if ($node == null) {
            return false;
        }
        if ($data < $node->data) {
            return $this->searchNode($node->left, $data);
        } else if ($data > $node->data) {
            return $this->searchNode($node->right, $data);
        } else {
            return $node;
        }
    }

    //删除
    public function delete($data)
    {
        return $this->deleteNode($this->root, $data);
    }

    private function deleteNode($node, $data)
    {
        if ($node == null) {
            return null;
        }
        if ($data < $node->data) {
            $node->left = $this->deleteNode($node->left, $data);
            return $node;
        } else if ($data > $node->data) {
            $node->right = $this->deleteNode($node->right, $data);
            return $node;
        } else {
            if ($node->left == null && $node->right == null) {
                $node = null;
                return $node;//根节点
            } else if ($node->left == null) {
                $node = $node->right;
                return $node;
            } else if ($node->right == null) {
                $node = $node->left;
                return $node;
            } else {
                //找出要删除的节点，用他左边子节点去替换要删除的节点
                $aux = $this->findMinNode($node->right);
                $node->data = $aux->data;
                $node->right = $this->deleteNode($node->right, $aux->data);
                return $node;
            }
        }
    }

    //找出左侧最小节点
    private function findMinNode($node)
    {
        if ($node == null) {
            return null;
        }
        while ($node && $node->left != null) {
            $node = $node->left;
        }
        return $node;
    }

    public function min()
    {
        return $this->minNode($this->root);
    }

    //找出左侧最小节点
    private function minNode($node)
    {
        if ($node == null) {
            return null;
        }
        while ($node && $node->left != null) {
            $node = $node->left;
        }
        return $node->data;
    }

    public function max()
    {
        return $this->maxNode($this->root);
    }

    //找出右侧最大节点值
    private function maxNode($node)
    {
        if ($node == null) {
            return null;
        }
        while ($node && $node->right != null) {
            $node = $node->right;
        }
        return $node->data;
    }

    //层数
    public function getHeight($node)
    {
        if ($node == null) {
            return null;
        }
        $leftH = $this->getHeight($node->left);
        $rightH = $this->getHeight($node->right);

        return max($leftH, $rightH) + 1;
    }

    //前序遍历
    public function preOrder($node)
    {
        if ($node == null) {
            return ;            
        }
        echo $node->data . '->';
        $this->preOrder($node->left);
        $this->preOrder($node->right);
    }

    //中序遍历
    public function inOrder($node)
    {
        if ($node == null) {
            return ;            
        }
        $this->inOrder($node->left);
        echo $node->data . '->';
        $this->inOrder($node->right);
    }

    //后序遍历
    public function postOrder($node)
    {
        if ($node == null) {
            return ;            
        }
        $this->postOrder($node->left);
        $this->postOrder($node->right);
        echo $node->data . '->';
    }
}    

$nodes = [6, 3, 8, 2, 5, 1, 7];
$bTreeObj = new BinaryTree();
foreach ($nodes as $node) {
    $bTreeObj->insert($node);
}

printf("先序遍历:\n");
$bTreeObj->preOrder($bTreeObj->root);
echo PHP_EOL;

printf("中序遍历\n");
$bTreeObj->inOrder($bTreeObj->root);
echo PHP_EOL;

printf("后序遍历\n");
$bTreeObj->postOrder($bTreeObj->root);

print_r($bTreeObj->search(3));

$bTreeObj->delete(3);

printf("删除后中序遍历！\n");
$bTreeObj->inOrder($bTreeObj->root);

printf("最小值: %d\n", $bTreeObj->min());

printf("最大值: %d\n", $bTreeObj->max());

printf("层数: %d\n", $bTreeObj->getHeight($bTreeObj->root));

结果：

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
先序遍历:
6->3->2->1->5->8->7->
中序遍历
1->2->3->5->6->7->8->
后序遍历
1->2->5->3->7->8->6->
Node Object
(
    [left] => Node Object
        (
            [left] => Node Object
                (
                    [left] => 
                    [right] => 
                    [data] => 1
                )

            [right] => 
            [data] => 2
        )

    [right] => Node Object
        (
            [left] => 
            [right] => 
            [data] => 5
        )

    [data] => 3
)
删除后中序遍历！
1->2->5->6->7->8->
最小值: 1
最大值: 8
层数: 4
参考资料：
数据结构与算法之美：[https://time.geekbang.org/column/article/68334]
-------------本文结束感谢您的阅读-------------
坚持原创技术分享，您的支持将鼓励我继续创作！