Arboles Binarios En C++

IMPLEMENTACION DE LA CLASE NODE Teniendo conocimientos previos de arboles, se llega a tomar en cuenta que necesitaremos usar un nodo en particular, a diferencia de la pila, cola y listas ordenadas; el nodo de un árbol tiene dos apuntadores a tipos de su misma clase, un puntero a su derecha y un puntero a su izquierda además de un dato que en este caso es entero. El atributo privado que almacenarael dato tendrá un método público que retorne el dato entero del mismo objeto. Los dos atributos privados que almacenaran las direcciones de memoria de su nodo derecho y nodo izquierdo respectivamente, tendrán dos métodos cada uno; un método devolverá su dirección y el otro método actualizara su enlace. IMPLEMENTACION DE LA CLASE TREE. La clase “tree” cuanta con los siguientes atributos yfunciones privadas: Un puntero llamado “root” de tipo “node” el cual apuntara a la raíz. Un entero que servirá para contar los nodos actuales. Existen tres métodos: inorder().- que recorre la lista de manera ordenada; postorder().- que recorre la lista primero pasando por la izquierda, luego por derecha y luego por la raíz; preorder().- que recorre la lista pasando primero por la raíz, después por suizquierda y después por su derecha. Por último la función clearpostorder() es un método recursivo que elimina el árbol pasando por cada uno de sus nodos en forma de postorder(). Estas cuatro funciones son implementadas en los métodos públicos de los que se explicara enseguida. En los métodos públicos implementamos los siguientes métodos: *Constructor que inicializa el árbol con su raíz nula y con sucontador "n" en cero. *Destructor que manda a llamar la función clear() que contiene la función recursiva clearpostorder(); la cual hace la raíz nula y el contador "n" lo pone en cero. *Las funciones printinorder(), printposorder() y printpreorder() contienen respectivamente su función recursiva privada explicada anteriormente. *La función clear() manda a llamar la función clearpostorder() einicializa el contador "n" en cero y la raíz a nula. *La función bsearch() contiene un parámetro que es un entero a buscar en el árbol, es muy corta gracias a que va comparando el parámetro con el nodo actual, si es mayor el dato a buscar se va a la derecha, de otro modo se va a la izquierda, este método se cumple mientras el dato del nodo actual no es igual al dato a buscar y mientras no sea nulo elpuntero siguiente ya sea izquierda o derecha.

*La función eliminar sirve de la siguiente manera: Haremos el recorrido de todo el árbol apoyándonos con dos apuntadores en este caso los llame "p" y "q", y dos variables de tipo bool llamadas “fromleft” y “fromright” que tendrán valor verdadero solo si en el nodo que estamos vino de izquierda o derecha respectivamente. El recorrido se hará mientrasexista el nodo "p" y que "p" sea diferente al dato a eliminar, dentro de este ciclo compararemos si el dato a eliminar es menor o mayor al dato del nodo actual; si el dato a eliminar es menor entonces pasamos "p" a su siguiente nodo de izquierda pero antes respaldamos en "q", entonces se activara a TRUE la variable “fromleft”. Pero si el dato a eliminar es mayor entonces también haremos elrespaldo de "p" en "q" y movemos a "p" a su derecha, entonces se activara TRUE la variable “fromright”. Una vez que se haya acabado el ciclo ya se definió donde está el nodo a eliminar, de otro modo la función regresara FALSE. Aquí es donde siguen las siguientes condiciones: Nótese: En estos casos se verificara si el nodo a eliminar es el "root" para reacomodarlo, de otro modo “root” no se mueve. Caso1.-Si borramos una hoja. Caso 2.-Si borramos un nodo cuyo hijo derecho no exista, pero hijo izquierdo sí. Caso 3.-Si borramos un nodo cuyo hijo derecho exista, pero hijo izquierdo no. Caso 4.-Si borramos un nodo cuyos hijos derecho e izquierdo si existan. *La función size() regresa un entero que es el numero de nodos en el árbol.

Diagrama de flujo inserción en árbol binario

Diagrama de...