使用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