[ Foro de C# ]

resolver preOrder de arbol binario cutilizando colas

31-May-2014 00:10
Invitado (sifa)
1 Respuestas

Hola, mi duda es como hacer para resolver una expresión en preOrder utilizando COLA? ya la hice resolviendo en postOrder utilizando PILA, pero no se como resolver la de preOrder con COLA

 
class Arbol
//clase donde se generan los recorridos del arbol, se crea el arbol y se resuelve la   
//expresion con recorrido postOrder
    {
        private Nodo principio;
        private string cadena;
        private Nodo raiz;
        private Nodo tope;
        private int cont = 0;
 
 
 
        public void agregar_a_Lista(Nodo n)
        {
            Nodo aux;
            aux = principio;
 
            if(principio == null)
            { principio = n;  }
            else
            {while (aux.siguiente != null)
                {
                    aux = aux.siguiente;
                }
                aux.siguiente = n;
                n.anterior = aux;
            }
        }
        public string listar()
        {
            Nodo aux = principio;
            string cad = "";
 
            while(aux!= null)
            {
                cad += aux.signos + " ";
                aux = aux.siguiente;
            }
            return cad;
        }
        public void generarArbol()
        {
            Nodo aux;
                aux = principio;
 
                while (aux != null)
                {
                    if (aux.signos == 42 || aux.signos == 47)//42 = * y 47 = / en ASCII
                    {
                        aux.izquierda = aux.anterior;//se bajan izquierdo
                        eliminar(aux.izquierda);//se elimina el izquierdo
                        aux.derecha = aux.siguiente;//se baja derecho
                        eliminar(aux.derecha);//se elimina derecho
                    } 
                    aux = aux.siguiente;
                }
                aux = principio;//se regresa aux a inicio para que analice los otros signos, si es que estos existen
                while (aux != null)
                {
                    if (aux.signos == 43 || aux.signos == 45)//43 = + y 45 = - en ASCII
                    {
                        aux.izquierda = aux.anterior;//se bajan izquierdo
                        eliminar(aux.izquierda);//se elimina el izquierdo
                        aux.derecha = aux.siguiente;//se baja derecho
                        eliminar(aux.derecha);//se elimina derecho
                    }
                    aux = aux.siguiente;
                }
        }
        public void quitaParentesis()
        {
            Nodo auxi = principio;
            while(auxi.signos == 40 && auxi.siguiente != null)
            {
                auxi = auxi.siguiente;
                generarArbol();
            }
            if(auxi.signos == 41)
            {
                auxi = auxi.siguiente;
                generarArbol();
            }
        }
        public void eliminar(Nodo signo)
        {
            Nodo auxi = principio;//se comienza en aux
            //bool encontrado = false;
            // principio.anterior = null;//borramos su anterior
            if (signo == principio)
            {
                principio = principio.siguiente;//se pasa inicio al siguiente
                principio.anterior = null;
 
            }
            else//si no...
            {
                if (signo.anterior != null)//si en el elemento que se esta tiene un anterior
                {
                    signo.anterior.siguiente = signo.siguiente;//el siguiente en el que se estaba sera el siguiente de su anterior 
                }
                if (signo.siguiente != null)//si en el elemento que se esta tiene un siguiente
                {
                    signo.siguiente.anterior = signo.anterior;//el anterior en el que se estaba sera el anteriore de su siguiente 
                }
            }
        }
        public double ResultadoPost(string expresion)//resolver expresion PostOrder
        {
            //se declaran variables y se crea pila de doubles
            int ope1 = 0;
            int ope2 = 0;
            double respuesta = 0;
 
            Pila<int> pila = new Pila<int>(expresion.Length);
 
            for(int i = 0; i < expresion.Length; i++)//se recorre la expresion
            {
                if(expresion[i] >= '0' && expresion[i] <= '9')//si el termino es un valor entre 0 y 9 lo metemos a la pila
                {
                    pila.Push(expresion[i] - '0');
                }
                if(expresion[i] == '+'|| expresion[i] == '-'|| expresion[i] == '/'|| expresion[i] == '*')//si el termino es un operador
                {
                    ope2 = pila.Pop();//se saca el operando2 de la pila
                    ope1 = pila.Pop();//se saca el operando1 de la pila
 
                    //de acuerdo al operador se hace su funcion
                    switch(expresion[i])
                    {
                        case '+':
                            respuesta = ope1 + ope2;
                            break;
                        case '-':
                            respuesta = ope1 - ope2;
                            break;
                        case '*':
                            respuesta = ope1 * ope2;
                            break;
                        case '/':
                            respuesta = ope1 / ope2;
                            break;
 
                    }
                    pila.Push(Convert.ToInt32(respuesta));//se mete el resultado en la pila
                }
            }
            return respuesta;//se regresa la respuesta
        }
 
        public string inOrder()
        {
            cadena = " ";
            inOrder(principio);
            return cadena;
        }
        private void inOrder(Nodo r)//comienza por el lado izquierdo, despues la raiz y al final el derecho
        {
            if (r.izquierda != null)
            {
                inOrder(r.izquierda);
            }
 
            cadena += r.signos;//la raiz queda en medio 
 
            if (r.derecha != null)
            {
                inOrder(r.derecha);
            }
        }
        public string preOrder()
        {
            cadena = " ";
            preOrder(principio);
            return cadena;
        }
        private void preOrder(Nodo r)//comienza por la raiz, despues lado izquierdo y al final derecho
        {
            cadena += r.signos;//la raiz es la que comienza
 
            if (r.izquierda != null)
            {
                preOrder(r.izquierda);
            }
            if (r.derecha != null)
            {
                preOrder(r.derecha);
            }
        }
        public string postOrder()
        {
            cadena = " ";
            postOrder(principio);
            return cadena;
        }
        private void postOrder(Nodo r)//comienza por el lado izquierdo, despues lado derecho y al final la raiz
        {
            if (r.izquierda != null)
            {
                postOrder(r.izquierda);
            }
            if (r.derecha != null)
            {
                postOrder(r.derecha);
            }
            cadena += r.signos;//la raiz es al final
        }
    }
------------------------------------
//clase pila
class Pila<T>
    {
        //atributos
        T[] vector;
        int tam;
        int tope;
        bool vacia, llena;
        public Pila(int n)//constructor
        {
            tam = n;
            vector = new T[tam];
            tope = 0;
            vacia = true;
            llena = false;
        }
        public void Push(T valor)
        {
            vacia = false;
            vector[tope++] = valor;
            if(tope == tam)
            {
                llena = true;
            }
        }
        public T Pop()
        {
            llena = false;
            if(--tope == 0)
            {
                vacia = true;
            }
            return vector[tope];
        }
        public bool esta_vacia()
        {
            return vacia;
        }
        public bool esta_llena()
        {
            return llena;
        }
        public T Tope()
        {
            return vector[tope - 1];
        }
    }
-----------------------------------------------------------
//clase Nodo
public Nodo derecha
        {
            set { _derecha = value; }
            get { return _derecha; }
        }
        public Nodo siguiente
        {
            set { _siguiente = value; }
            get { return _siguiente; }
        }
        public Nodo anterior
        {
            set { _anterior = value; }
            get { return _anterior; }
        }
        public char signos//guarda los signos
        {
            set { _signos = value; }
            get { return _signos; }
        }
        public Nodo(char signos)
        {
            _signos = signos;
        }
        public Nodo ()
        { }
 
 
        public override string ToString()
        {
            return "Dato:" + _signos.ToString();
        }
    }
-----------------------------------------------------------------------
clase NODO
 
class Nodo
    {
        private Nodo _izquierda;
        private Nodo _derecha;
        private Nodo _siguiente;
        private Nodo _anterior;
        private char _signos;
 
        public Nodo izquierda
        {
            set { _izquierda = value; }
            get { return _izquierda; }
        }
        public Nodo derecha
        {
            set { _derecha = value; }
            get { return _derecha; }
        }
        public Nodo siguiente
        {
            set { _siguiente = value; }
            get { return _siguiente; }
        }
        public Nodo anterior
        {
            set { _anterior = value; }
            get { return _anterior; }
        }
        public char signos//guarda los signos
        {
            set { _signos = value; }
            get { return _signos; }
        }
        public Nodo(char signos)
        {
            _signos = signos;
        }
        public Nodo ()
        { }
 
 
        public override string ToString()
        {
            return "Dato:" + _signos.ToString();
        }
    }
 



02-Jun-2014 01:36
Nacho Cabanes (+32)

No tengo muy claro lo que pretendes... te pongo unos pocos conceptos básicos para ver qué no estoy entendiendo, porque creo que estás mezclando dos cosas distintas:

- La notación postfija, o polaca inversa, es de la forma: 2 5 +   Esta notación permite resolver operaciones con la ayuda de una pila: cada vez que encuentras un operador, debes desapilar dos operandos, realizar la operación y apilar su resultado.

- La notación prefija, o polaca, es de la forma: + 3 4   El que sea "contraria" a una pila no quiere decir que se pueda resolver con una cola. Hace muchos años que lo estudié, pero, al contrario que con la notación postfija, en la que es fácil aplicar una pila, no recuerdo haber leído que la prefija se pueda resolver con una cola.

- En un árbol binario sí se puede hablar de pre-orden (nodo, izquierda, derecha), de post-orden (izquierda, derecha, nodo) y de in-orden (izquierda, nodo, derecha). Pero si estás usando el árbol binario para resolver expresiones matemáticas, deberías recorrerlo en orden.

Por eso, como hablas de colas y de preorden pero tu fuente tiene árboles y pilas... no tengo claro si quieres resolver una expresión a partir del arbol (que sí podrás, pero si lo recorres en orden), o usando una cola (que me temo que debería ser una pila), o si quieres convertir el arbol en la pila o la cola equivalente volcándolo a notación prefija o postfija...

Si entiendes el inglés, puedes leer más sobre la mayoría de esas cosas en estos artículos de la wikipedia:
http://en.wikipedia.org/wiki/Binary_expression_tree
http://en.wikipedia.org/wiki/Tree_traversal
http://en.wikipedia.org/wiki/Reverse_Polish_notation
http://en.wikipedia.org/wiki/Polish_notation






(No se puede continuar esta discusión porque tiene más de dos meses de antigüedad. Si tienes dudas parecidas, abre un nuevo hilo.)