Arvore Binária
Publicado por marlon luis petry 29/05/2005
[ Hits: 19.842 ]
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'); }
Thread, Courses, Shell e Aquivo
Script MakePach para correção de platarforma 32 bits para 64
Rotina para controle de portas paralelas em C. (biblioteca LP.h)
Ponteiro para Ponteiro para Ponteiro
Vou voltar moderar conteúdos de Dicas e Artigos (0)
Compartilhando a tela do Computador no Celular via Deskreen
Como Configurar um Túnel SSH Reverso para Acessar Sua Máquina Local a Partir de uma Máquina Remota
Configuração para desligamento automatizado de Computadores em um Ambiente Comercial
Como renomear arquivos de letras maiúsculas para minúsculas
Imprimindo no formato livreto no Linux
Vim - incrementando números em substituição
Efeito "livro" em arquivos PDF
Como resolver o erro no CUPS: Unable to get list of printer drivers
Vou voltar moderar conteúdos de Dicas e Artigos (0)
Instalação Uefi com o instalador clássico do Mageia (0)
É cada coisa que me aparece! - não é só 3% (2)
[Python] Automação de scan de vulnerabilidades
[Python] Script para analise de superficie de ataque
[Shell Script] Novo script para redimensionar, rotacionar, converter e espelhar arquivos de imagem
[Shell Script] Iniciador de DOOM (DSDA-DOOM, Doom Retro ou Woof!)
[Shell Script] Script para adicionar bordas às imagens de uma pasta