Encuentra sucesor en orden y predecesor en un BST mediante el programa C ++

En este post, vamos a aprender cómo encontrar sucesor en orden y predecesor en el BST (árbol de búsqueda binaria) mediante el programa C ++ ?

predecesor significa que el nodo que se encuentra justo detrás del nodo dado y sucesor significa el nodo que se encuentra justo después de que el nodo dado.

Un en orden de recorrido es un recorrido en el que los nodos son atravesados ​​en el formato Izquierda Derecha Raíz.

Algoritmo:

Paso 1: comenzar con la raíz del árbol

Paso 2: if el nodo dado es igual a la raíz, a continuación, para el predecesor van de la orden a la derecha la mayoría de nodo del hijo izquierdo de la raíz y para el sucesor van de la orden al nodo más a la izquierda del hijo derecho de la raíz.

Paso 3: if el nodo especificado es superior a la raíz, a continuación, la actualización predecesor igual a la raíz y la raíz igual a su hijo derecho y buscar en el sub-árbol (árbol actual).

Paso 4: if el nodo dado es inferior a la raíz, a continuación, la actualización sucesor igual a la raíz y la raíz igual a su hijo izquierdo y busque el subárbol (árbol actual).

Considere el programa dado:

#include<iostream>
using namespace std;

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;

find(root->left,pre,suc,info);
}

else
{
pre=root;

find(root->right,pre,suc,info);
}
}

node *newNode(int n)
{
node *p=new node;
p->info=n;
p->left=p->right=NULL;
return p;
}

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;
}
//main program
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;
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;
}

salida

Predecessor of 70 is 67
Successor of 70 is 75


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *