Arvore Binária
Publicado por marlon luis petry 29/05/2005
[ Hits: 20.006 ]
Homepage: http://petryx.blogrs.com.br
Este script transforma uma árvore em árvore binária, e mostra os algoritmos de atravessamento da árvore de forma recursiva e não recursiva.
/****************************************************************************** **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'); }
Memória compartilhada, semáforo e criação de processos
Rotina para controle de portas paralelas em C. (biblioteca LP.h)
Busca, inserção e remoção de elementos numa lista
Atualizando o Passado: Linux no Lenovo G460 em 2025
aaPanel - Um Painel de Hospedagem Gratuito e Poderoso
O macete do Warsaw no Linux Mint e cia
Um modo leve de ouvir/ver áudio/vídeo da internet em máquinas pererecas
Resolver algumas mensagens de erro do SSH
Instalar módulo de segurança do Banco do Brasil Warsaw do tipo .run
Sem espaço na partição home (0)
O que você está ouvindo agora? [2] (190)
Procrastinação e autossabotagem são problemas muito comuns na sociedad... (5)
warsaw parou de funcionar após atualização do sistema (solução) (10)