0
노드 삭제 (값 8 또는 2)가 작동하지 않습니다. 나머지는 전체 코드가 잘 작동합니다. 심지어 노드 4를 삭제하십시오. 나는 그 문제를 이해할 수 없다.BBST의 노드 삭제
코드 : main() 함수에서 1D 벡터로부터 균형 이진 검색 트리를 만들었습니다. (8 노드 인)은 "0 아이"경우 TREE::deleteBBST에서
#include <iostream>
#include <vector>
using namespace std;
class TNode
{
public:
TNode(){}
~TNode(){ std::cout <<"TNode destroyed" << endl; }
TNode *left;
TNode *right;
int data;
};
////////////////////////////////////////////////////////////////////
////////////////////////// TREE ////////////////////////////////
////////////////////////////////////////////////////////////////////
class TREE
{
public:
TREE(){}
~TREE(){}
TNode* createBBST(std::vector<int>& arr, int startIdx, int endIdx);
void preOrderTraverseBT(TNode *node);
void inOrderTraverseBT(TNode *node);
void postOrderTraverseBT(TNode *node);
TNode* searchBBST(TNode *rootnode, int data);
TNode* insertBBST(TNode *rootnode, int data);
void deleteBBST(TNode *rootnode, int data);
TNode* findPred(TNode *rootnode);
};
TNode* TREE::createBBST(std::vector<int>& arr, int startIdx, int endIdx)
{
//base-case
if(startIdx>endIdx)
return NULL;
/* Get the middle element and make it root */
TNode *root = new TNode;
int mid = (startIdx+endIdx)/2;
root->data = arr[mid];
/* Recursively construct the left subtree and make it left child of root */
root->left = createBBST(arr, startIdx, mid-1);
/* Recursively construct the right subtree and make it right child of root */
root->right = createBBST(arr, mid+1, endIdx);
return root;
}
void TREE::preOrderTraverseBT(TNode *node)
{
if(node==NULL)
return;
cout << node->data << " ";
preOrderTraverseBT(node->left);
preOrderTraverseBT(node->right);
return;
}
void TREE::inOrderTraverseBT(TNode *node)
{
if(node==NULL)
return;
inOrderTraverseBT(node->left);
cout << node->data << " ";
inOrderTraverseBT(node->right);
return;
}
TNode* TREE::searchBBST(TNode *rootnode, int data)
{
if(rootnode==NULL)
return NULL;
if(rootnode->data == data)
return rootnode;
else if(rootnode->data > data){
return searchBBST(rootnode->left, data);
}
else //if(rootnode->data < data)
return searchBBST(rootnode->right, data);
}
TNode* TREE::insertBBST(TNode *rootnode, int data)
{
if(rootnode->data >= data)
{
if(rootnode->left==NULL)
{
rootnode->left = new TNode;
rootnode->left->left=NULL; rootnode->left->right=NULL;
rootnode->left->data = data;
return rootnode->left;
}
else// if(rootnode->left!=NULL)
{
return insertBBST(rootnode->left, data);
}
}
else// if(rootnode->data < data)
{
if(rootnode->right==NULL)
{
rootnode->right = new TNode;
rootnode->right->left=NULL; rootnode->right->right=NULL;
rootnode->right->data = data;
return rootnode->right;
}
else// if(rootnode->right!=NULL)
{
return insertBBST(rootnode->right, data);
}
}
//
}
TNode* TREE::findPred(TNode *rootnode)
{
if(rootnode==NULL)
return rootnode;
return findPred(rootnode->right);
}
void TREE::deleteBBST(TNode *rootnode, int data)
{
cout << "Delete node : " << data << endl;
TNode *deletenode = searchBBST(rootnode, data);
TNode* temp = NULL;
if(deletenode->left==NULL && deletenode->right==NULL) /* 0 Child */
{
cout << "0 child..." << endl;
delete deletenode;
deletenode = NULL;
inOrderTraverseBT(rootnode);
cout << "\ndeleted..."<<endl;
}
else if(deletenode->left!=NULL && deletenode->right==NULL) /* 1 Child */
{
cout << "1 child..." << endl;
//copy left child to its parent
temp = deletenode->left;
deletenode->data = temp->data;
deletenode->left = temp->left;
deletenode->right = temp->right;
}
else if(deletenode->left==NULL && deletenode->right!=NULL) /* 1 Child */
{
cout << "1 child..." << endl;
temp = deletenode->right;
deletenode->data = temp->data;
deletenode->right = temp->right;
deletenode->left = temp->left;
}
else /* 2 Children */
{
cout << "2 child..." << endl;
//find predecessor
TNode* pred = findPred(deletenode->left);
//if pred has no child
if(pred->left == NULL)
{
deletenode->data = pred->data;
}
else
{
//if pred has a left child
deletenode->data = pred->data;
pred->data = pred->left->data;
pred->left = pred->left->left;
}
delete pred;
pred = NULL;
}
//delete the old left child
delete temp;
temp = NULL;
}
////////////////////////////////////////////////////////////////////
////////////////////////// main ////////////////////////////////
////////////////////////////////////////////////////////////////////
int main(int argc, char const *argv[])
{
std::vector<int> vec(5);
for (int i = 0; i < vec.size(); ++i)
vec[i] = i;
TREE aTree;
TNode* root = aTree.createBBST(vec, 0, vec.size()-1);
//print the resulted BBST
aTree.inOrderTraverseBT(root);
//search a key
TNode* node = aTree.searchBBST(root, 3);
if(node != NULL)
cout << "node->data = " << node->data << endl;
else
cout << "Key not found..." << endl;
//insert
cout << "Insert node : 3" << endl;
aTree.insertBBST(root, 3);
aTree.inOrderTraverseBT(root);
cout << "Insert node : 8" << endl;
aTree.insertBBST(root, 8);
aTree.inOrderTraverseBT(root);
aTree.deleteBBST(root, 8);
// aTree.inOrderTraverseBT(root);
return 0;
}