#include "bst.h"
#include <stdio.h>
#include <iostream>
#include <assert.h>
using namespace std;
BST::BST():_root(NULL){
}
/*
** @Summary : insert value into BST
** @param value : value to be inserted.
*/
void BST::insert(int value) {
// If BST is empty, assign _root with value
if(!_root) {
_root = new BSTNode;
_root->_value = value;
_root->_LChild = NULL;
_root->_RChild = NULL;
return;
}
// Find where to insert
BSTNode* p = _root;
BSTNode* q;
while(p) {
// If value exists, do nothing.
if(p->_value == value) return;
q=p;
if(p->_value < value) p = p->_RChild;
else p = p->_LChild;
}
// Insert value into correct place;
BSTNode* temp = new BSTNode;
temp->_value = value;
temp->_LChild = NULL;
temp->_RChild = NULL;
if(q->_value < value) q->_RChild = temp;
else q->_LChild = temp;
}
/*
** @Summary : search value in BST
** @param value : value to search.
** @param target: searched BSTNode*
** @param parent: parent of target.
*/
bool BST::search(int value, BSTNode* &target, BSTNode* &parent) {
BSTNode* temp = _root;
parent = NULL;
while(temp) {
if(temp->_value == value) {
target = temp;
return true;
} else if(temp->_value < value) {
parent = temp;
temp = temp->_RChild;
}else {
parent = temp;
temp = temp->_LChild;
}
}
target=temp;
return false;
}
/*
** @Summary : find the value and delete its node
** @param value : value to delete.
*/
void BST::del(int value) {
BSTNodePtr target, parent, temp, precursor;
target = _root;
parent = NULL;
while(target && target->_value != value) {
parent = target;
if(target->_value > value) target = target->_LChild;
else target = target->_RChild;
}
if(!target) return; // value does not exist, needn't deleting.
temp = target;
precursor = NULL;
// target has both left child and right child
if(target->_LChild && target->_RChild) {
// find precursor of target.
precursor = target->_LChild;
temp = precursor;
while(precursor->_RChild) {
temp = precursor;
precursor = precursor->_RChild;
}
target->_value = precursor->_value;
// assign target value with precursor value
if(temp != precursor)
temp->_RChild = precursor->_LChild;
else // if precursor is target's left child
target->_LChild = precursor->_LChild;
} else if(target->_LChild) { // target only has left child
precursor = target->_LChild;
target->_value = precursor->_value;
target->_LChild = precursor->_LChild;
target->_RChild = precursor->_RChild;
} else if(target->_RChild) { // target only has right child
precursor = target->_RChild;
target->_value = precursor->_value;
target->_LChild = precursor->_LChild;
target->_RChild = precursor->_RChild;
} else if(parent) { // target is leaf node and has parent
precursor = target;
if(parent->_LChild == target) parent->_LChild = NULL;
else parent->_RChild = NULL;
} else { // target is leaf and is root
precursor = target;
_root = NULL;
}
delete precursor;
}
/*
** @Summary : replace the target node with its precursor
** @param value : node to delete.
*/
void BST::deleteNodePrecursor(BSTNode* n) {
}
/*
** @Summary : replace the target node with its successor
** @param value : node to delete.
*/
void BST::deleteNodeSuccessor(BSTNode* n) {
}
/*
** @Summary : view the tree in preorder
** @param order : the current BSTNode
*/
void BST::PreView(BSTNode* n) {
if(n) {
cout<<n->_value<<" ";
PreView(n->_LChild);
PreView(n->_RChild);
}
}
/*
** @Summary : view the tree in middle order
** @param order : the current BSTNode
*/
void BST::MidView(BSTNode* n) {
if(n) {
MidView(n->_LChild);
cout<<n->_value<<" ";
MidView(n->_RChild);
}
}
/*
** @Summary : view the tree in postorder
** @param order : the current BSTNode
*/
void BST::PostView(BSTNode* n) {
if(n) {
PostView(n->_LChild);
PostView(n->_RChild);
cout<<n->_value<<" ";
}
}
/*
** @Summary : view the tree
** @param order : 0-preorder, 1-middle order, 2-postorder
*/
void BST::view(unsigned order) {
switch(order) {
default:
assert(0 && "Illegal view order!");
case 0:
PreView(_root);
break;
case 1:
MidView(_root);
break;
case 2:
PostView(_root);
break;
}
cout<<endl;
}
评论7
最新资源