使用C ++程序在BST中查找有序的后继者Successor 和 Predecessor前任者

前任表示在给定节点之后的节点，后继表示在给定节点之后的节点。

有序遍历是其中遍历节点的格式为“左根右”的遍历。

算法：

步骤1：从树的根部开始

步骤2：如果给定节点等于root，则对于有序前任节点，请转到根节点左子节点的最右节点；对于有序后继者，请转到根节点左子节点的最左节点。根。

步骤3：如果给定节点大于根，则更新等于root的前任节点，并等于其右子节点的root并搜索子树（当前树）。

步骤4：如果给定节点小于根，则更新等于root的后继节点，并等于其左子节点的root并搜索子树（当前树）。

考虑给定的程序：

#include<iostream>
using namespace std;

/*structure of the tree*/
struct node 
{
	int info;	
	node *left,*right;
};

/*查找前任和后任的方法*/
void find(node *root,node*& pre,node*& suc,int info) 
{
	if(root==NULL)
	{
		return ;
	}
	
	/*如果键（给定节点）是根*/ 
	if(root->info == info )        
	{
		if(root->left != NULL)
		{
			node* temp=root->left;
			while(temp->right != NULL)
			{
				temp=temp->right;
			}
			pre=temp;
		}
		if(root->right != NULL)
		{
			node* temp=root->right;
			while(temp->left != NULL)
			{
				temp=temp->left;
			}
			suc=temp;
		}
		return ;
	}
	
	/*如果键小于当前节点（根）*/
	if(root->info > info)       
	{
		suc=root;
		/*Search the left subtree*/
		find(root->left,pre,suc,info);   
	}
	/*如果键大于当前节点（根）*/
	else
	{
		pre=root;
		/*搜索右子树*/
		find(root->right,pre,suc,info);  
	}
}

/*如果树不存在则创建newNode的方法*/
node *newNode(int n)  
{
	node *p=new node;
	p->info=n;
	p->left=p->right=NULL;
	return p;
}

/*在BST中插入节点的方法*/
node *insert(node* node,int info)  
{
	if(node==NULL)
	{
		return newNode(info);
	}
	if(info < node->info)          
	{
		node->left=insert(node->left,info);
	}
	else
	{
		node->right=insert(node->right,info);
	}
	return node;
}

//主程序
int main(){
	int info=70;

	node* root=newNode(60);
	insert(root,50);
	insert(root,70);
	insert(root,40);
	insert(root,30);
	insert(root,75);
	insert(root,80);
	insert(root,65);
	insert(root,45);
	insert(root,55);
	insert(root,90);
	insert(root,67);

	node*pre=NULL,*suc=NULL;  /*pre将包含前任，suc将包含后任*/

	find(root,pre,suc,info);
	if(pre != NULL)
	{
		cout<<"Predecessor of "<<info<<" is "<<pre->info<<endl;
	}	
	else
	{
		cout<<"!!!!!!No possible predecessor!!!!!!";
	}

	if(suc != NULL)
	{
		cout<<"Successor of "<<info<<" is "<<suc->info<<endl;
	}	
	else
	{
		cout<<"!!!!!!No possible successor!!!!!!";
	}
	cout<<endl;
	
	return 0;
}

输出结果

Predecessor of 70 is 67
Successor of 70 is 75