Arvore Binária
Publicado por marlon luis petry 29/05/2005
[ Hits: 19.860 ]
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'); }
Fila bancária utilizando lista simplisment encadeada
Calculando PI usando série de Leibniz
Enviar mensagem ao usuário trabalhando com as opções do php.ini
Meu Fork do Plugin de Integração do CVS para o KDevelop
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
Compartilhamento de Rede com samba em modo Público/Anônimo de forma simples, rápido e fácil
Cups: Mapear/listar todas as impressoras de outro Servidor CUPS de forma rápida e fácil
Criando uma VPC na AWS via CLI
Tem como instalar o gerenciador AMD Adrenalin no Ubuntu 24.04? (16)
Arch Linux - Guia para Iniciantes (2)
Problemas ao instalar o PHP (11)
Tenho dois Link's ( IP VÁLIDOS ), estou tentando fazer o failover... (0)