我是靠谱客的博主 愉快毛豆,这篇文章主要介绍C++ delete a node from BST,现在分享给大家,希望可以做个参考。

首先, 从一个BST中删除一个节点可能很tricky。 例如, 对于如下一个BST of integers:

当我们想要删除某个节点的时候, 我们的第一步就是查找到这个元素值所在的位置。 接下来, 我们要保证删除这个节点之后, 我们的二叉搜索树依然是一个二叉搜索树(BST)。 但是这个删除操作本身又是那么的complicated。 因为被删除的项又分为四种情况:

(1): 被删除的节点是叶子节点, 即这个节点既没有左子树, 有没有右子树, 这是最简单的case。

(2): 被删除的节点没有左子树,但是有右子树。  也就是说此节点left成员为NULL。

(3):被删除的节点没有右子树, 但是有左子树。 也就是说此节点right成员为NULL。

(3): 被删除的节点既有左子树, 又有右子树。 这种情况是最复杂的。 要解决这种case, 我们需要将其想法转换为简单的case, 例如(2) 和 (3).

注意(2)和(3)其实是对称的两个cases。

case1: 直接删除也节点, 依然得到BST:

               

case 2: 删除left 为NULL的节点。 将其parent的link指向此节点的Child, 用temp 指向此节点, 直接delete即可。

  

(3) case 3: 同case 2:

 

case 4: 删除具有两个孩子的节点。 此时要想保持其实BST, 我们可以将这个节点的左子树的最大的值拷贝到这个节点的data 位置处。 注意由于这个值是左子树的最大的节点的。 所以存储着这个最大值的节点一定没有右孩子。 相当于我们将这个复杂的case, 简化为了case3 的情况了, 接下来删除这个节点就可以了。 删除此类节点当然不会成为上面问题。  另外, 除了这样的一个解决办法外, 我们还可以使用另外的一个办法, 就是将这个复杂的case 转换为case2 , 即找到右子树的最小的值, 此节点没有左孩子。 然后copy到应该删除的节点的位置处, 然后删除这个最小值的节点, 就okay了。

接下来, 找15 的左右子树的最小的节点(或者左子树的最大):

接下来, copy data:

然后删除, 最终得到如下:

 

主要C++ 程序如下:

复制代码
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
/* Deleting a node from Binary search tree */ #include<iostream> using namespace std; struct Node { int data; Node *left; Node *right; }; //Function to find minimum in a tree. Node* FindMin(Node* root) { while(root->left != NULL) root = root->left; return root; } // Function to search a delete a value from tree. struct Node* Delete(Node *root, int data) { if(root == NULL) return root; else if(data < root->data) root->left = Delete(root->left,data); else if (data > root->data) root->right = Delete(root->right,data); // Wohoo... I found you, Get ready to be deleted else { // Case 1: No child if(root->left == NULL && root->right == NULL) { delete root; root = NULL; } //Case 2: One child else if(root->left == NULL) { Node *temp = root; root = root->right; delete temp; } else if(root->right == NULL) { struct Node *temp = root; root = root->left; delete temp; } // case 3: 2 children else { Node *temp = FindMin(root->right); root->data = temp->data; root->right = Delete(root->right,temp->data); } } return root; } //Function to visit nodes in Inorder void Inorder(Node *root) { if(root == NULL) return; Inorder(root->left); //Visit left subtree cout << root->data << " "; //Print data Inorder(root->right); // Visit right subtree } // Function to Insert Node in a Binary Search Tree Node* Insert(Node *root,char data) { if(root == NULL) { root = new Node(); root->data = data; root->left = root->right = NULL; } else if(data <= root->data) root->left = Insert(root->left,data); else root->right = Insert(root->right,data); return root; } int main() { /*Code To Test the logic Creating an example tree 5 / 3 10 / 1 4 11 */ Node* root = NULL; root = Insert(root,5); root = Insert(root,10); root = Insert(root,3); root = Insert(root,4); root = Insert(root,1); root = Insert(root,11); cout << "Before delete: "; Inorder(root); cout << endl; // Deleting node with value 5, change this value to test other cases root = Delete(root,5); //Print Nodes in Inorder cout<<"Inorder: "; Inorder(root); cout<<"n"; }


运行结果:

 

 

 

 

最后

以上就是愉快毛豆最近收集整理的关于C++ delete a node from BST的全部内容,更多相关C++内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(47)

评论列表共有 0 条评论

立即
投稿
返回
顶部