Árvores Computacionais

Ver o tópico anterior Ver o tópico seguinte Ir em baixo

Árvores Computacionais

Mensagem por Evandro Abu Kamel em Sex 13 Nov 2009, 13:29

Olá denovo pessoal, sei que está meio "fora do prazo", mas vou postar aqui algumas coisas sobre árvore binária e árvore AVL.

Pra evitar repetições, podem dar uma lida na WikiPédia, com bons artigos sobre os temas:

Árvore Binária: Fala sobre o conceito de árvore e as três formas de se percorrer uma árvore (em ordem, pré-ordem e pós-ordem) e algumas funções interessantes.

Árvore Binária de Pesquisa: Fala sobre busca, inserção, remoção, percurso e ordenação de uma árvore binária.

Árvore AVL: Cita características, operações e rotação de uma AVL.

Segue abaixo uns códigos sobre essas árvores.
Tomaremos como base o código da classe BinaryTree passado pela professora.

Procurei mais um pouco por códigos de AVL e encontrei um muito bom feito em Java, e foi super fácil passar pra C#, e os códigos nem estão tão complexos.
Código de Árvore AVL

Código:
using System;
using System.Collections.Generic;
using System.Text;

namespace BinaryTree
{
    public class BinaryTree
    {
        private class Node
        {
            public int value;
            public Node left, right;


            public Node(int value, Node left, Node right)
            {
                this.value = value;
                this.left = left;
                this.right = right;
            }
            public Node(int value) : this(value, null, null) { }
        }

        private Node root;

        public BinaryTree()
        {
            root = null;
        }

        public bool contains(int value)
        {
            return contains(root, value);
        }

        public void insert(int value)
        {
            root = insert(root, value);
        }

        public void remove(int key)
        {
            root = remove(root, key);
        }

        public void print()
        {
            if (root == null)
                Console.WriteLine("\nArvore inexistente! ");
            else
            {
                Console.WriteLine("\nA arvore em pre-ordem fica assim: ");
                print(root);
            }
        }

        private bool contains(Node R, int value)
        {
            if (R == null)
                return false;
            else if (value == R.value)
                return true;
            else if (value < R.value)
                return contains(R.left, value);
            else
                return contains(R.right, value);
        }

        private Node insert(Node R, int value)
        {
            if (R == null)
                return new Node(value);
            else
            {
                if (value < R.value)
                    R.left = insert(R.left, value);
                else if (value > R.value)
                    R.right = insert(R.right, value);
                return R;
            }
        }

        private void print(Node R)  // imprime em pre-ordem
        {
            Console.Write(" {0} ", R.value);
            if (R.left != null)
                print(R.left);
            if (R.right != null)
                print(R.right);
        }

        private Node remove(Node R, int value)
        {
            if (R != null)
            {
                if (value == R.value)
                    R = removeNode(R);
                else if (value < R.value)
                    R.left = remove(R.left, value);
                else
                    R.right = remove(R.right, value);
            }
            return R;
        }

        private Node removeNode(Node R)
        {
            if (R.left == null)
                return R.right;
            else if (R.right == null)
                return R.left;
            else
                return removeMax(R);
        }

        private Node removeMax(Node R)
        {
            if (R.left.right == null)
            {
                R.left.right = R.right;
                return R.left;
            }
            else
            {
                Node aux1 = R.left;
                Node aux2 = R.left.right;
                while (aux2.right != null)
                {
                    aux1 = aux2;
                    aux2 = aux2.right;
                }
                aux1.right = aux2.left;
                aux2.left = R.left;
                aux2.right = R.right;
                return aux2;
            }
        }


        /* ************************************** */
        static void Main(string[] args)
        {
            BinaryTree tree = new BinaryTree();

            Console.WriteLine("Arvore Binaria\n");

            tree.insert(5);
            tree.insert(3);
            tree.insert(7);
            tree.insert(9);
            tree.insert(1);
            tree.print();

            Console.ReadLine();
        }
    }
}

Agora vem os códigos de algumas funções de manipulação de árvore que não estão no código acima. Vejam a recursão atuando. Wink

Imprime a árvore em ordem:
Código:
public void printEm(Node t)
{
    if (t.left != null)            // left
        printEm(t.left);
    Console.Write(" {0} ", t.value);  // root
    if (t.right != null)          // right
        printEm(t.right);
}

Imprime a árvore pré-ordem:
Código:
public void printEm(Node t)
{
    Console.Write(" {0} ", t.value);  // root
    if (t.left != null)            // left
        printEm(t.left);
    if (t.right != null)          // right
        printEm(t.right);
}

Imprime a árvore pós-ordem:
Código:
public void printEm(Node t)
{
    if (t.left != null)            // left
        printEm(t.left);
    if (t.right != null)          // right
        printEm(t.right);
    Console.Write(" {0} ", t.value);  // root
}

A travessia em amplitude tenho apenas usando filas, mas estou esperando a professora me passar um código usando apenas recursão.

Creio que isso aí já ajude a dar uma luz para fazer o trabalhinho sobre árvore, que nem é pra entregar.

Até a próxima.

_________________
"Faça as coisas o mais simples que você puder,
porém, não as mais simples." Albert Einstein

avatar
Evandro Abu Kamel
Administrador
Administrador

Número de Mensagens : 222
Idade : 28
Data de inscrição : 11/03/2009

Ver perfil do usuário http://forum.clubedosistema.com

Voltar ao Topo Ir em baixo

Ver o tópico anterior Ver o tópico seguinte Voltar ao Topo

- Tópicos similares

 
Permissão deste fórum:
Você não pode responder aos tópicos neste fórum