Este script transforma uma árvore em árvore binária, e mostra os algoritmos de atravessamento da árvore de forma recursiva e não recursiva.

• Download WalkerBTree.c
• Enviar nova versão

Esconder código-fonte

/******************************************************************************
**Author = Marlon Petry                                                  *
**e-mail = marlonpetry@gmail.com                                     *
**Date = 29/05/2005                                                  *
**Description: Binary Tree with traversals recursive and not recursive         *
**                                                              *
** This file may be distributed and/or modified under the terms of the         *
** GNU General Public License version 2 as published by the Free Software      *
** Foundation and appearing in the file LICENSE.GPL included in the            *
** packaging of this file.                                           *
**                                                              *   
******************************************************************************/



#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <unistd.h>
//estrutura da arvore
typedef struct no {
   int info;
   int n;
   struct no *left;
   struct no *right;
}tree;

tree *tfather=NULL; //ponteiro que indica o pai de uma subarvore
//estrutura para a pilha
typedef struct pr {
   tree *nodo;
   struct erd *next;
   struct erd *prev;
}pilha;

pilha *topo = NULL,*base = NULL;   

void push(tree *nodo) //inseri na pilha
{
pilha *aux=NULL;
   if(topo == NULL)
   {
      base = (pilha *) malloc(sizeof(pilha));
      base->nodo = nodo;
      base->next = NULL;
      base->prev = NULL;
      topo = base;
   }
   else
   {
      aux = (pilha *) malloc(sizeof(pilha));
      aux->nodo = nodo;
      aux->prev = topo;
      aux->next = NULL;
      topo->next = aux;
      topo = aux;
   }
}

tree *pop() //retira da pilha
{
   tree *nodo;
   if(topo == NULL)
      return NULL;
   else
   {
    nodo = topo->nodo;
   topo = topo->prev;
   }
   return nodo;
}


/*
 * Procura pelo pai na arvore
 */
       
tree *findFather(tree *root,int father)
{
   tree *aux = root;
   if(aux->info == father)
      tfather = aux;
   //else
      //return NULL;
   if(aux->left != NULL)
   findFather(aux->left,father);
   if(aux->right != NULL)
   findFather(aux->right,father);
      
}

/*
 * Insere na arvore
 */      
void insert(tree **root, int info, int position,int father)
{
   tree *aux,*aux2;
   if(*root == NULL)
   {
      aux = (tree *) malloc(sizeof(tree));
      aux->info = info;
      aux->left = NULL;
      aux->right = NULL;
      *root = aux;
   }
   else
   {
      findFather(*root,father);
      if(tfather == NULL)
        puts("Pai nao encontrado");
      if(tfather->info == father && position == -1 )
      {      
         aux = (tree *)malloc(sizeof(tree));
         aux->info = info;
         aux->left = NULL;
         aux->right = NULL;
         tfather->left = aux;
      }
      else if(tfather->info == father && position == 1)
      {      
         aux = (tree *)malloc(sizeof(tree));
         aux->info = info;
         aux->left = NULL;
         aux->right = NULL;
         tfather->right = aux;
      }   
      
   }
}

//Show binary tree by algorithm InOrder not recursive
void InOrder(tree *root) 
{
   tree *aux = root;
   int flag = 0;
   
   while(flag == 0)
   {
      while(aux != NULL)
      {
         push(aux);
         aux = aux->left;
      }
      
      aux = pop();
            
      if(aux == NULL)
         flag = 1;
      else
      {
         printf("%d\t",aux->info);
         aux = aux->right;
      }
   }
}
//Show binary tree by algorithm PreOrder 
void PreOrder(tree *root) 
{
   tree *aux = root;
   int flag = 0;
   
   while(flag == 0)
   {
      while(aux != NULL)
      {
         printf("%d\t",aux->info);
         push(aux);
         aux = aux->left;
      }
      
      aux = pop();
            
      if(aux == NULL)
         flag = 1;
      else
      {
        aux = aux->right;
      }
   }
}

//Show Binary tree by algorithm PostOrder
void PostOrder(tree *root) 
{
   tree *aux = root;
   
   int flag = 0;
   
   while(flag == 0)
   {
      while(aux != NULL)
      {
         aux->n=1;
         push(aux);
         aux = aux->left;
      }
      
      aux = pop();
            
      if(aux == NULL)
         flag = 1;
      else
      {
         if(aux->n == 1)
         {
            aux->n = 2;
          push(aux);
         aux   = aux->right;
         }
         else
         {
         printf("%d\t",aux->info);
         aux = NULL;
         }
      }
   }
}



/*
 * Show Tree by algorithm InOrder recursivo
 */
void showInOrder(tree *root)
{
   if(root == NULL)
      return;
   showInOrder(root->left);
   printf("%d\t",root->info);
   showInOrder(root->right);
}

/*
 * Show tree by algorithm PreOrder recursive
 */
void showPreOrder(tree *root)
{
   if(root == NULL)
      return;
   printf("%d\t",root->info);
   showPreOrder(root->left);
   showPreOrder(root->right);
}


/*
 * Show tree by algorithm PostOrder recursive
 */
void showPostOrder(tree *root)
{
   if(root == NULL)
      return;
   
   showPostOrder(root->left);
   showPostOrder(root->right);
   printf("%d\t",root->info);
}




int  menu()
{
   int opt;
   puts("Walker Binnary Tree - Marlon Petry");
   printf("\n(1) Insert");
   printf("\n(2) Show\n");
   scanf("%d",&opt);
   
      
   return opt;
}

int main()
{
   tree *root = NULL;
   int opt,flag=0,info,position,father;
   char c;
   do
   {
      opt = menu();
      switch(opt)
      {
      case 1:
         if(flag == 0)
         {
            puts("Insert root");
            scanf("%d",&info);
            insert(&root,info,0,0);
            flag = 1;
            break;
         }
          puts("Insert new nodo");
         puts("Insert father"); 
         scanf("%d",&father);
         puts("Insert position -1 left or 1 right");
         scanf("%d",&position);
         puts("Insert value");
         scanf("%d",&info);
         insert(&root,info,position,father);

         break;
      case 2:
         
         printf("In Order not Recursive \n");
         InOrder(root);
         printf("\n");
         printf("In Order Recursiva\n");
          showInOrder(root);
         
         printf("\n\nPre Order not Recursive\n");
         PreOrder(root);
         printf("\nPre Order Recursive\n");
          showPreOrder(root);
         
          printf("\n\nPost Order Not Recursive\n");
         PostOrder(root);
         printf("\nPost Order Recursive\n");
          showPostOrder(root);
         
         break;
      }
      puts("\nType e for finish");
      scanf(" %c",&c);
   }while( c != 'e');
}

Escaneando diretório

Programa recursivo para obter raiz quadrada

Biblioteca de tipos abstratos

Arvore AVL

Estrutura de dados: Lista dinâmica duplamente encadeada