-
Notifications
You must be signed in to change notification settings - Fork 0
/
BST.cpp
121 lines (115 loc) · 3.12 KB
/
BST.cpp
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
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
void printArr(vector<int> & nums){
for(auto e:nums){
cout<<e<<' ';
}
cout<<endl;
}
struct TreeNode{
int val;
TreeNode * lchild;
TreeNode *rchild;
TreeNode(int x):val(x),lchild(nullptr),rchild(nullptr){}
};
void printBST(TreeNode * node){
// DFS
if(node==nullptr)return ;
printBST(node->lchild);
cout<<node->val<<' ';
printBST(node->rchild);
}
void insertBST(TreeNode * root,int num){
if(num > root->val){
if(root->rchild==nullptr){
root->rchild = new TreeNode(num);
return ;
}
insertBST(root->rchild,num);
}else{
if(root->lchild==nullptr){
root->lchild = new TreeNode(num);
return ;
}
insertBST(root->lchild,num);
}
}
// BST
TreeNode* buildBST(vector<int> & arr){
if(!arr.size()) return nullptr;
TreeNode * root = new TreeNode(arr[0]);
for(int i = 1; i<arr.size() ; i++){
insertBST(root,arr[i]);
}
return root;
}
TreeNode * findMin(TreeNode * root){
if(root->lchild==nullptr){
return root;
}
return findMin(root->lchild);
}
TreeNode * pre = nullptr;
void deleteNode(TreeNode * root, int num){
cout<<"cmp : "<<num<<','<<root->val<<endl;
if(root==nullptr) return;
if(num!=root->val){
if(root->val > num){
pre = root;
deleteNode(root->lchild,num);
return;
}
if(root->val < num){
pre = root;
deleteNode(root->rchild,num);
return;
}
}
cout<<"deleting "<<num<<endl;
cout<<"node info "<<(root->lchild? root->lchild->val : -1)<<" "<<(root->rchild? root->rchild->val:-1)<<endl;
if(root->lchild==nullptr&&root->rchild==nullptr){
if(pre->lchild==root)pre->lchild=nullptr;
if(pre->rchild==root)pre->rchild=nullptr;
delete root;
root = nullptr;
cout<<"root address "<<root<<endl;
return ;
}
if(root->rchild==nullptr){
root->val = root->lchild->val;
root->rchild = root->lchild->rchild;
TreeNode * delPtr = root->lchild;
root->lchild = root->lchild->lchild;
delete delPtr;
cout<<"root info"<<(root->lchild? root->lchild->val : -1)<<" "<<(root->rchild? root->rchild->val:-1)<<endl;
return ;
}
if(root->lchild==nullptr){
root->val = root->rchild->val;
root->lchild = root->rchild->lchild;
TreeNode * delPtr = root->rchild;
root->rchild= root->rchild->rchild;
delete delPtr;
return ;
}
if(root->lchild!=nullptr&&root->rchild!=nullptr){
// 右子树最小点替换
TreeNode * minPtr = findMin(root->rchild);
root->val = minPtr->val;
deleteNode(root->rchild,root->val);
return ;
}
}
int main(){
vector<int> nums1 = {53,17,78,9,45,65,87,23,91};
TreeNode * root = buildBST(nums1);
printBST(root);
cout<<endl<<"-----------"<<endl;
deleteNode(root,53);
printBST(root);
cout<<endl<<root->val<<endl;
return 0;
}