二叉搜索树插入和删除的例证

二叉搜索树也称为二叉排序树，然后它也是二叉树，然后满足以下属性的二叉树就是二叉搜索树:

1. 如果左子树不为空，则左子树上左右节点的值小于根节点的值

2. 如果其右子树不为空，则其右子树中所有节点的值都大于根节点的值

3. 它的左右子树也必须是二叉搜索树

================================================ ==== ==================

1，搜索

在插入之前，让我们先谈谈其搜索. 在上面的二叉搜索树中，找到一个元素非常简单. 由于其节点分布是规则的，因此只需执行以下步骤即可找到元素:

2. 插入

由于二进制搜索树的特殊性质，二进制搜索树中的每个元素只能出现一次，因此，如果在插入过程中发现该元素已经存在于二进制搜索树中，则不会出现. 插入.

否则，找到适合插入的位置.

第一种情况: _root为空

直接插入，返回true；

第二种情况: 要插入的元素已经存在

如上所述，如果该元素已经存在于二进制搜索树中，则将不再插入该元素并直接返回false；

第三种情况: 找到合适的位置

================================================ ==== ==================

对于二叉搜索树的删除操作二叉排序树的删除，主要是要了解其中的几个，并且编写起来相对简单.

当然，在开始时，我们仍然需要确定要删除的节点是否在我们的树中. 如果要删除的元素不在树中，则直接返回false；否则，返回false. 否则，分为以下四种情况进行分析: <

》要删除的节点没有左右子节点

》要删除的节点只有左子节点

》要删除的节点只有正确的子节点

》要删除的节点具有左右子节点

删除方法的说明:

对于第一种情况，我们可以将其完全分类为第二种或第三种情况，无需单独编写部分代码进行处理；

》如果要删除的节点只有左子节点，则让该节点的父节点指向该节点的左子节点，然后删除该节点，返回true;

》如果要删除的节点只有正确的子节点，则让该节点的父节点指向该节点的右边的子节点，然后删除该节点，返回true；

对于上述两种情况，在确定该节点是否是根节点之前二叉排序树的删除，我们还应该做出判断. 如果它是根节点，则直接将根节点指向该节点的左或右子节点，然后删除此节点.

》最后也是最麻烦的一个是要删除的节点的左右子节点存在. 目前，我们的删除方法如下:

1. 在节点的右子树中找到最左边的子节点（即，在遍历顺序中右子树中的第一个节点）

2. 将其值与要删除的节点的值交换

3. 然后删除此节点等同于删除我们要删除的节点，返回true;

================================================ ==== ==================

程序代码:

1. 二进制搜索树的插入操作

 1  bool Insert(const K& key)
 2     {
 3         if (_root == NULL)
 4         {
 5             _root = new Node(key);
 6             return true;
 7         }
 8         Node* parent=NULL;
 9         Node* pcur = _root;
10         while (pcur)
11         {
12             if (pcur->_key == key)  //有key节点，则不再插入
13                 return false;
14             if (pcur->_key > key)
15             {
16                 parent = pcur;
17                 pcur = pcur->_left;
18             }
19             else if (pcur->_key < key)
20             {
21                 parent = pcur;
22                 pcur = pcur->_right;
23             }
24         }
25         if (parent->_key < key)
26             parent->_right = new Node(key);
27         else
28             parent->_left = new Node(key);
29         return true;
30     }

2. 二进制搜索树布尔删除操作（常数K和键）

 1 bool Remove(const K& key)
 2     {
 3         assert(_root);
 4         Node* parent = NULL;
 5         Node* pcur = _root;
 6         Node* del = pcur;
 7         while (pcur != NULL  && pcur->_key != key)
 8         {
 9             if (pcur->_key > key)
10             {
11                 parent = pcur;
12                 pcur = pcur->_left;
13             }
14             else if (pcur->_key < key)
15             {
16                 parent = pcur;
17                 pcur = pcur->_right;
18             }
19         }
20         if (pcur == NULL)
21             return false;
22         if (pcur->_left == NULL)      //只有右孩子
23         {
24             //如果pcur就是根节点的话，让根节点指向根的右
25             if (pcur == _root)
26                 _root = pcur->_right;
27             else if (pcur == parent->_left) 
28             {
29                 parent->_left = pcur->_right;
30             }
31             else
32             {
33                 parent->_right = pcur->_right;
34             }
35             del = pcur;
36         }
37         else if (pcur->_right == NULL)     //只有左孩子
38         {
39            //如果是根节点，让根节点指向根的左
40             if (pcur == _root)
41                 _root = pcur->_left;
42             else if (parent->_left == pcur)
43             {
44                 parent->_left = pcur->_left;
45             }
46             else
47                 parent->_right = pcur->_left;
48             del = pcur;
49         }
50         //pcur左右孩子都不为空
51         else
52         {
53            //找到节点右子树的最左节点
54             Node* left = pcur->_right;
55             parent = pcur;
56             while (left->_left)     
57             {
58                 parent=left;
59                 left = left->_left;
60             }
61             del = left;
62             pcur->_key = left->_key;   //交换节点的值
63             if (parent->_left == left)
64             {
65                 parent->_left = left->_right;
66             }
67             else
68             {
69                 parent->_right = left->_right;
70             }
71 
72         }
73         delete del;
74         return true;
75     }

本文将永久更新链接地址:

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-223025-1.html