二叉查找树.cpp

常见算法

//二叉查找树.
#include<malloc.h>
#include<iostream>
using std::cin;
using std::cout;
using std::endl;
#define SIZE sizeof(struct tree)
#define N 10
	struct tree 
	{
		int key;
	    struct tree*left;
		struct tree*right;
		struct tree*father;
	};
//=============================
//     插入一个数到二叉查找树
//=============================
struct tree*insert_tree(int num,struct tree*root)
{ 
    struct tree*son;
	//struct tree *sonofroot;
	if (root==NULL)
	{
		root=(struct tree*)malloc(SIZE);
		root->key=num;
		root->father=NULL;
		root->left=NULL;
		root->right=NULL;
		return root;
	}
    
	if(num<root->key)                                     //如果数字比根小则插入左子树。
	{
        //root->left->father=root;
	 	son=insert_tree(num,root->left);                 
		son->father=root;                                  //插入后建立父子关系。
        root->left=son;
	}
	else                                                  //如果数字比根大或相等，则插入右子树。
	{
	     //root->right->father=root;
	     son=insert_tree(num,root->right);
		 son->father=root;                                //插入后建立父子关系。   
		 root->right=son; 
	}
    return root;
}
void output_tree(struct tree*root)                         //按顺序输出树中的数字
{
    if(root!=NULL)
	{
		output_tree(root->left);
		cout<<root->key<<"  ";
        output_tree(root->right);
    }
}
//============================================
//  查找某一个数，返回这个数在树的结点指针
//============================================
struct tree*find_tree(int num,struct tree*root)
{

	
	 if (root==NULL)
	 {
		 return NULL;
	 }
     if(root->key==num)
	 {
		 return root;
	 }
	 if (num<root->key)
	 {
		 return find_tree(num,root->left);    //如果小于root的关键字，则在左边找
	 }
	 else
	 {
		 return find_tree(num,root->right);   //否则在右边找。
	 }

}
//===========================================
//           寻找二叉树的最小数
//===========================================
struct tree*min_tree(struct tree*root)
{
	if (root->left==NULL)
	{
		return root;
	}
	return min_tree(root->left);
}
//===========================================
//     寻找输入数的后继，返回其指针。
//===========================================
struct tree*find_successor(int numb,struct tree*root)
{
    struct tree*find;
	find=find_tree(numb,root);
	if(find==NULL)
	{
		cout<<"没有找到此数！"<<endl;
	    return NULL;
	}
	else 
	{
		if (find->right!=NULL)                //如果右子指针不空，其后继是右子树的最小值。
		{
			return min_tree(find->right);
		}
		     else if (find->father==NULL)         //如果右子为空，且本节点是树的根，
			 {                                      //则无后继，返回空指针。
		     	return NULL;
			 }
		           else if (find->father->left==find) 
				   {
		    	         return find->father;}  //如果右子为空，且本节点不是根，且是父结点的左子。
		          
	      	             else if(find->father==find->father->father->left)
						 {
			                  return find->father->father;  //如果右子节点为空，且本节点不是根，是父的右子,其父接点
						 }                                                                 //是左结点。
						      else
							  {
								  return NULL;        //如果右子节点为空，且本节点不是根，是父的右子。
							  }                          
	}                                         
    
}
//====================================================
//   删除一个数：先找到输入数的节点，删除后返回其指针
//====================================================
struct tree*delete_tree(int num,struct tree*root)
{
	struct tree*del,*delkey;
//	int delflag=1;                         //flag为删除标记，等于1表明删除成功，等于0表明没有删除。
	del=find_tree(num,root);
    delkey=del;
	if (del==NULL)
	{
		cout<<"没有找到您输入的数！"<<endl;
	//	delflag=0;
		return NULL;
	}
	
	else
	{
	    if ((delkey->right==NULL)&&(delkey->left==NULL))   //如果本节点没有子节点，直接删除其父接点的对应子节点
		{
		    if (delkey==delkey->father->left)       //如果delkey是左子结点。
			{
                delkey->father->left=NULL;
		    }
			else
			{
				delkey->father->right=NULL;       //如果delkey是有字节点
			}
             
		}	
	    if ((delkey->right!=NULL)&&(delkey->left==NULL))           //只有右节点而无左节点。 
		{
			delkey->right->father=delkey->father;               
			if (delkey->father->left==delkey)
			{
                delkey->father->left=delkey->right;                     //delkey是左子节点             
			}
			else if(delkey->father->right==delkey)
			{
				delkey->father->right=delkey->right;                  //delkey是右子节点。
			}
		}
		if ((delkey->right==NULL)&&(delkey->left!=NULL))           //只有左节点而无右点。 
		{
			delkey->left->father=delkey->father;               
			if (delkey->father->left==delkey)
			{
                delkey->father->left=delkey->left;                     //delkey是左子节点             
			}
			else if(delkey->father->right==delkey)
			{
				delkey->father->right=delkey->left;                  //delkey是右子节点。
			}
		}
        if ((delkey->left!=NULL)&&(delkey->right!=NULL))
		{                                                    //如果delkey的左子和右子都存在
			delkey=find_successor(num,root);                   //直接把其后继代替他的位置，并置空
			if((delkey->left==NULL)&&(delkey->right==NULL))
			{
			
		        if(delkey->father->left==delkey){delkey->father->left=NULL;}
			    if (delkey->father->right==delkey) {delkey->father->right=NULL;}  //后继之父对应的节点。 
			}

			else if(delkey==delkey->father->left)
			{
				delkey->father->left=delkey->right;
			}
			else if (delkey->father->right==delkey)
			{
				delkey->father->right=delkey->right;
			}
			if (del->father!=NULL)
			{
            
			    if (del==del->father->left)
				{
				    del->father->left=delkey;              //如果删除的不是根
					                                         //将插入点的父指向delkey
				}
		    	if (del==del->father->right)
				{
				    del->father->right=delkey;
				}
			}
		
			delkey->father=del->father;                        
		    delkey->left=del->left;
			delkey->right=del->right;
			del->left->father=delkey;
			del->right->father=delkey;
			
		}
		if (delkey->father==NULL)
		{
			delkey=root;
		}
		cout<<"删除成功！"<<endl;
	}
	return del;
}
//=============================================
//                 主函数
//============================================
main()
{
	int array[N]={44,32,4,34,25,3,44,76,86,46};
    int i;
	struct tree*root0,*accept=NULL,*find,*successor,*dele;
	cout<<"待处理的数组是："<<endl;
    for(i=0;i<N;i++)
	{   
		cout<<array[i]<<"  ";                   //插入法将数组建立到一棵二叉查找树。
		root0=insert_tree(array[i],accept);
		accept=root0;
	}
	cout<<endl;
	cout<<"按顺序输出是："<<endl;
	output_tree(root0);
	cout<<endl;
    char select='y';
	while(select=='y')                                  //输出查找得数。
	{
	
	    cout<<"请输入您要找的数值："<<endl;
	    cin>>i;
	    find=find_tree(i,root0);
	    if(find!=NULL)
		{
	        cout<<"您要着的结果"<<find->key<<"存在";
	        cout<<endl;
		    break;
		}
    	else
		{
	    	cout<<"没有找到您所输入的数：继续吗?y继续，其它键退出："<<endl;
		    cin>>select;
		}
	}
	cout<<"其后继是："<<endl;
	successor=find_successor(i,root0);
	if (successor==NULL)
	{
		cout<<"没有后继"<<endl;
	}
	else
	{
		cout<<successor->key<<endl;
	}
    cout<<"请输入要删除的数："<<endl;
	cin>>i;
	dele=delete_tree(i,root0);
	if (dele!=NULL)
	{
		cout<<"您删除的数是："<<dele->key<<endl;
	}
	cout<<"删除后的树是：";
	output_tree(root0);
	cout<<endl;
	return 0;
}