Jump to content

Travessia PreOrder de uma Árvore Binária


kripton2007
 Share

Recommended Posts

Boas, preciso de uma ajuda...

Precisava de saber como se faz uma função de travessia PreOrder iterativa de uma árvore binária, se possível sem recurso a stack.

A mesma função de modo recursivo é simples de se fazer, em modo iterativo é que não faço ideia...

typedef struct node
{
     int value;
     struct node *left;
     struct node *right;
}    mynode;

mynode *root;



void preorder(mynode *root)
{
     if(root)
     {     printf("[%d] ", root->value);
           preorder(root->left);
           preorder(root->right);
    }
}

Alguém me pode mostrar uma função e se possível com a explicação?

Obrigado! 😛

Link to comment
Share on other sites

ok... estive a fazer o seguinte com a ajuda de umas coisas que encontrei pela net:

void itPreOrder(mynode *root)
{
mynode *save[100];
int top = 0;
if(root == NULL)
	return;
save[top++] = root;
while(top != 0)
{	root = save[--top];
printf("[%d] ", root->value);
if (root->right != NULL)
	save[top++] = root->right;
if(root->left != NULL)
	save[top++] = root->left;
}
}

Podem-me dizer se isto é ou não correcto?!

Link to comment
Share on other sites

Parece-me bem 😛 A única coisa a apontar seria a limitação a 100 nós, e estás a utilizar o stack para guardar o percurso, tendo dito que era preferível não o fazer. A solução mais simples seria contar os nós antes de fazer a travessia e alocar o array conforme essa contagem. Outra solução seria fazer uma lista de apontadores para nó que referenciasse o antecessor, e utilizá-la em vez do array, construindo o percurso da mesma maneira que estás a fazer agora.

Desaparecido.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.