2017-07-23 09:09:19
writer:pprp
二叉查找树,删除的功能,分为三种情况,
- 没有子节点
- 有一个子节点
- 有两个子节点 (有两种方法,具体见代码)
代码如下:
#include <iostream>
using namespace std;
struct tree
{
tree*left;
int date;
tree*right;
};
void print(tree * root) //用中序打印出来
{
if(root!=NULL)
{
print(root->left);
cout << root->date << endl;
print(root->right);
}
}
tree* insert(tree * root,int key);
tree * create(int *node,int len) //建立一个二叉树
{
tree *root = NULL;
for(int i = 0 ; i< len ; i++ )
{
root = insert(root,node[i]);
}
return root;
}
tree* insert(tree * root,int key) //在二叉树中根据规则插入一个数
{
tree*current;
tree*parent;
tree*newval=new tree();
newval->left = NULL;
newval->right = NULL;
newval->date = key;
if(root == NULL)
{
root = newval;
}
else
{
current = root;
while(current!=NULL)
{
parent = current;
if(current->date>key)
{
current = current->left;
}
else
{
current = current->right;
}
}
if(parent->date > key)
{
parent->left = newval;
}
else
{
parent->right = newval;
}
}
return root;
}
tree * bisearch(tree* root,int x) //在二叉树中查找一个数
{
// if(root!=NULL)
// {
// if(root->date == x)
// {
// return root;
// }
// else if(root->date > x)
// {
// root = bisearch(root->left,x);
// }
// else
// {
// root = bisearch(root->right,x);
// }
// }
// return NULL;
bool solve = false;
while(root && !solve)
{
if(x == root->date)
solve = true;
else if(x < root->date)
root = root->left;
else
root = root->right;
}
if(root == NULL)
cout <<"can't find it" << endl;
return root;
}
bool Delete(tree*root,int x) //从二叉树中删除一个数
{
bool find = false;
tree*parent = NULL;
tree*current = NULL;
current = root;
while(current&&!find) //用parent记录下来现在节点的父节点,通过这个while循环找到x
{
if(current->date < x)
{
parent = current;
current = current->right;
}
else if(current->date > x)
{
parent = current;
current = current->left;
}
else if(current->date == x)
{
find = true;
}
}
if(current == NULL)
cout << "can't find " << x << endl;
if(current->left == NULL && current->right == NULL) //第一种情况,如果没有子节点
{
if( current == root)
root = NULL;
if(parent->left == current)
parent->left = NULL;
else
parent->right = NULL;
delete current;
}
else if(current->right == NULL || current->left == NULL) //第二种情况,如果只有一个子节点
{
if(current == root)
{
if(current->left == NULL)
root = current->right;
else
root = current->left;
}
else //分四种情况,手动画图看看
{
if(parent->left == current && current->left)
parent->left = current->left;
else if(parent->left == current && current->right)
parent->left = current->right;
else if(parent->right == current && current->right)
parent->right = current->right;
else
parent->right = current->left;
}
delete current;
}
else //有两个子节点,可以有两种方法,
//1,找到前继忠最大的点,交换;
//2,找到后集中最小的点,交换;
//这里采用的是第一种方案
{
tree * par = current;
tree * kid = current->left;
while(kid->right)
{
par = kid;
kid = kid->right;
}
current->date = kid->date;
if(par == current)
current->left = kid->left;
else
par->right = kid->left;
delete kid;
}
return find;
}
int main()
{
int x;
tree * root = NULL;
tree * point = NULL;
int node[11] = {1,2,3,4,5,6,7,8,9,10,11};
root = create(node,11);
print(root);
cout << "您想查找的节点的值:" << endl;
cin >> x;
point = bisearch(root,x);
if(point == NULL)
cout <<"没有您要的数" << endl;
else
cout <<point->date<< endl;
cout << "您想删除的数: " << endl;
cin >> x;
if(Delete(root,x) == true)
cout <<"the number "<<x << " has been delete successfully!" << endl;
else
cout <<"can't find the number " <<x << endl;
print(root);
return 0;
}
代码改变世界