Tree* tmp = t;
if(tmp->parent->left == tmp)
{
tmp->parent->left = NULL;
}
else
{
tmp->parent->right = NULL;
}
delete tmp;
tmp = NULL;
}
else if((t->left == NULL)||(t->right == NULL))
{/*一个子节点*/
Tree* tmp = t;
if(tmp->parent->left == tmp)
{
tmp->parent->left = (tmp->left ==NULL) tmp->right :tmp->left;
}
else
{
tmp->parent->right = (tmp->left ==NULL) tmp->right :tmp->left;
}
delete tmp;
tmp = NULL;
}
else
{/*两个子节点*/
Tree* s = Successor(t);
if(s == NULL)
{
return false;
}
t->node_value = s->node_value ;
DeleteTreeNode(s);
}
}
/*删除一个节点
p为树根节点指针
*/
bool DeleteTreeNode(Tree * n)
{
if(n == NULL)
{
return NULL;
}
else if((n->left == NULL)&&(n->right == NULL))
{/*没有子节点*/
Tree* tmp = n;
if(tmp->parent->left == tmp)
{
tmp->parent->left = NULL;
}
else
{
tmp->parent->right = NULL;
}
delete tmp;
tmp = NULL;
}
else if((n->left == NULL)||(n->right == NULL))
{/*一个子节点*/
Tree* tmp = n;
if(tmp->parent->left == tmp)
{
tmp->parent->left = (tmp->left ==NULL) tmp->right :tmp->left;
}
else
{
tmp->parent->right = (tmp->left ==NULL) tmp->right :tmp->left;
}
delete tmp;
tmp = NULL;
}
else
{/*两个子节点*/
if(s == NULL)
{
return false;
}
n->node_value = s->node_value ;
DeleteTreeNode(s);
}
}
/*生成二叉查找树*/
Tree * CreateBSTree(int * array_list,int array_length)
{
if(array_length <= 0)
{
return false;
}
Tree * root = NULL;
root = new BSTree();
root->left = NULL;
root->right = NULL;
root->parent = NULL;
root->node_value = array_list[0];
for(int i=1;i
CreateBSTree(root,array_list[i]);
}
return root;
}
void CreateBSTree(Tree * root,int node_value)
{
if(root == NULL)
{
return ;
}
if(root->node_value > node_value)
{
if(root->left == NULL)
{
Tree * node = new Tree();
node->left = NULL;
node->right = NULL;
node->node_value = node_value;
node->parent = root;
root->left = node;
}
else
{
CreateBSTree(root->left,node_value);
}
}
else
{
if(root->right == NULL)
{
Tree * node = new Tree();
node->left = NULL;
node->right = NULL;
node->node_value = node_value;
node->parent = root;
root->right = node;
}
else
{
CreateBSTree(root->right,node_value);
}
}
}
/*中序排序输出二叉查找树*/
void Print(Tree* root)
{
if(root == NULL)
{
return ;
}
Print(root->left);
std::cout<