c++ - nodo - Imprime un árbol binario de una manera bonita
buscar un nodo en un arbol binario en c (15)
Prefacio
La respuesta tardía y tardía está en Java, pero me gustaría añadir el mío al registro porque descubrí cómo hacerlo con relativa facilidad y la forma en que lo hice es más importante. El truco es reconocer que lo que realmente desea es que ninguno de sus subárboles se imprima directamente debajo de sus nodos raíz / subrot (en la misma columna). ¿Por qué puedes preguntar? Debido a que se garantiza que no hay problemas de espaciado, no se superponen, no existe la posibilidad de que el subárbol izquierdo y el subárbol derecho colisionen, incluso con números superlongos. Se ajusta automáticamente al tamaño de los datos de su nodo. La idea básica es que el subárbol izquierdo se imprima totalmente a la izquierda de la raíz y el subárbol derecho se imprima totalmente a la derecha de la raíz.
Una anaología de cómo pensé acerca de este problema.
Una buena manera de pensarlo es con los paraguas, imagina primero que estás afuera con un paraguas grande, representas la raíz y tu paraguas y todo lo que hay debajo es todo el árbol . piensa en tu subárbol izquierdo como un hombre bajo (más bajo que tú) con un paraguas más pequeño que está a tu izquierda debajo de tu paraguas grande. Su subárbol derecho está representado por un hombre similar con un paraguas similar en su lado derecho. Imagínese que si los paraguas de los hombres bajos se tocan, se enojan y se golpean entre sí (mala coincidencia). Tú eres la raíz y los hombres a tu lado son tus subárboles . Debes estar exactamente en el medio de sus paraguas (subárboles) para separar a los dos hombres y asegurarte de que nunca toquen los paraguas. El truco consiste en imaginar esto recursivamente, donde cada uno de los dos hombres tiene a sus propias dos personas más pequeñas bajo su paraguas (nodos de niños) con paraguas cada vez más pequeños (sub-subárboles y demás) que necesitan para mantenerse separados bajo su paraguas (subárbol), actúan como subraíces . Fundamentalmente, eso es lo que debe suceder para "resolver" el problema general al imprimir árboles binarios, la superposición de subárbol. Para hacer esto, simplemente necesitas pensar en cómo "imprimirías" o "representarías" a los hombres en mi anaología.
Mi implementación, sus limitaciones y su potencial.
En primer lugar, la única razón por la que la implementación de mi código toma más parámetros de los que deberían ser necesarios (el nodo actual para ser impreso y el nivel de nodo) es porque no puedo mover fácilmente una línea en la consola al imprimir, así que primero tengo que mapear mis líneas e imprimir. ellos a la inversa. Para hacer esto, hice un lineLevelMap que mapeaba cada línea del árbol a su salida (esto podría ser útil para el futuro como una forma de reunir fácilmente cada línea del árbol y también imprimirlo al mismo tiempo).
//finds the height of the tree beforehand recursively, left to reader as exercise
int height = TreeHeight(root);
//the map that uses the height of the tree to detemrine how many entries it needs
//each entry maps a line number to the String of the actual line
HashMap<Integer,String> lineLevelMap = new HashMap<>();
//initialize lineLevelMap to have the proper number of lines for our tree
//printout by starting each line as the empty string
for (int i = 0; i < height + 1; i++) {
lineLevelMap.put(i,"");
}
Si pudiera obtener códigos de escape ANSI trabajando en la consola java (windows ugh), simplemente podría imprimir una línea hacia arriba y reduciría el número de parámetros en dos porque no necesitaría mapear líneas o conocer la profundidad del árbol de antemano. Independientemente, aquí está mi código que se repite en un recorrido ordenado del árbol:
public int InOrderPrint(CalcTreeNode currentNode, HashMap<Integer,String>
lineLevelMap, int level, int currentIndent){
//traverse left case
if(currentNode.getLeftChild() != null){
//go down one line
level--;
currentIndent =
InOrderPrint(currentNode.getLeftChild(),lineLevelMap,level,currentIndent);
//go up one line
level++;
}
//find the string length that already exists for this line
int previousIndent = lineLevelMap.get(level).length();
//create currentIndent - previousIndent spaces here
char[] indent = new char[currentIndent-previousIndent];
Arrays.fill(indent,'' '');
//actually append the nodeData and the proper indent to add on to the line
//correctly
lineLevelMap.put(level,lineLevelMap.get(level).concat(new String(indent) +
currentNode.getData()));
//update the currentIndent for all lines
currentIndent += currentNode.getData().length();
//traverse right case
if (currentNode.getRightChild() != null){
//go down one line
level--;
currentIndent =
InOrderPrint(currentNode.getRightChild(),lineLevelMap,level,currentIndent);
//go up one line
level++;
}
return currentIndent;
}
Para imprimir realmente este árbol para la consola en java, solo use el mapa de línea que generamos. De esta manera podemos imprimir las líneas al revés.
for (int i = height; i > -1; i--) {
System.out.println(lineLevelMap.get(i));
}
Cómo funciona todo realmente
La subfunción InorderPrint hace todo el ''trabajo'' y puede imprimir recursivamente cualquier nodo y sus subárboles correctamente. Aún mejor, los separa de manera uniforme y usted puede modificarlos fácilmente para espaciar a todos los nodos por igual (solo haga que los Nodedata sean iguales o haga que el algoritmo piense que es). La razón por la que funciona tan bien es porque utiliza la longitud de datos del Nodo para determinar dónde debería estar la siguiente sangría. Esto asegura que el subárbol izquierdo siempre se imprima ANTES de la raíz y el subárbol derecho, por lo tanto, si se asegura esto recursivamente, no se imprime ningún nodo izquierdo debajo de su raíz ni sus raíces y así sucesivamente con lo mismo para cualquier nodo derecho. En cambio, la raíz y todas las subredes están directamente en medio de sus subárboles y no se desperdicia ningún espacio.
Un ejemplo de salida con una entrada de 3 + 2 como la de la consola es:
Y un ejemplo de 3 + 4 * 5 + 6 es:
Y finalmente, un ejemplo de (3 + 4) * (5 + 6) tenga en cuenta que el paréntesis es:
Ok, pero ¿por qué Inorder?
La razón por la que un recorrido Inorder funciona tan bien es porque siempre imprime primero el material que está más a la izquierda, luego la raíz y luego el material que está más a la derecha. Exactamente cómo queremos que sean nuestros subárboles: todo a la izquierda de la raíz se imprime a la izquierda de la raíz, todo a la derecha se imprime a la derecha. El recorrido transversal del orden, naturalmente, permite esta relación, y como imprimimos líneas y hacemos sangrías basadas en datos de nodos, no debemos preocuparnos por la longitud de nuestros datos. El nodo podría tener una longitud de 20 caracteres y no afectaría al algoritmo (aunque podría comenzar a quedarse sin espacio de pantalla real). El algoritmo no crea ningún espacio entre los nodos, pero se puede implementar fácilmente, lo importante es que no se superponen.
Solo para probarlo por usted (no tome mi palabra para esto) aquí hay un ejemplo con algunos caracteres bastante largos.
Como puede ver, simplemente se ajusta según el tamaño de los datos, ¡No se superponen! Mientras tu pantalla sea lo suficientemente grande. Si alguna vez alguien descubre una forma fácil de imprimir una fila en la consola java (soy todo oídos), esto será mucho más simple, lo suficientemente fácil para que casi cualquier persona con conocimientos básicos de árboles lo entienda y lo use, y la mejor parte. es que no hay riesgo de errores de superposición mal.
Solo me pregunto si puedo obtener algunos consejos sobre cómo imprimir un bonito árbol binario en forma de:
5
10
11
7
6
3
4
2
Ahora mismo lo que imprime es:
2
4
3
6
7
11
10
5
Sé que mi ejemplo está al revés de lo que estoy imprimiendo actualmente, lo cual no importa si imprimo desde la raíz hacia abajo como se imprime actualmente. Cualquier consejo es muy apreciado para mi pregunta completa:
¿Cómo modifico mis impresiones para que el árbol se vea como un árbol?
//Binary Search Tree Program
#include <iostream>
#include <cstdlib>
#include <queue>
using namespace std;
int i = 0;
class BinarySearchTree
{
private:
struct tree_node
{
tree_node* left;
tree_node* right;
int data;
};
tree_node* root;
public:
BinarySearchTree()
{
root = NULL;
}
bool isEmpty() const { return root==NULL; }
void print_inorder();
void inorder(tree_node*);
void print_preorder();
void preorder(tree_node*);
void print_postorder();
void postorder(tree_node*);
void insert(int);
void remove(int);
};
// Smaller elements go left
// larger elements go right
void BinarySearchTree::insert(int d)
{
tree_node* t = new tree_node;
tree_node* parent;
t->data = d;
t->left = NULL;
t->right = NULL;
parent = NULL;
// is this a new tree?
if(isEmpty()) root = t;
else
{
//Note: ALL insertions are as leaf nodes
tree_node* curr;
curr = root;
// Find the Node''s parent
while(curr)
{
parent = curr;
if(t->data > curr->data) curr = curr->right;
else curr = curr->left;
}
if(t->data < parent->data)
{
parent->left = t;
}
else
{
parent->right = t;
}
}
}
void BinarySearchTree::remove(int d)
{
//Locate the element
bool found = false;
if(isEmpty())
{
cout<<" This Tree is empty! "<<endl;
return;
}
tree_node* curr;
tree_node* parent;
curr = root;
while(curr != NULL)
{
if(curr->data == d)
{
found = true;
break;
}
else
{
parent = curr;
if(d>curr->data) curr = curr->right;
else curr = curr->left;
}
}
if(!found)
{
cout<<" Data not found! "<<endl;
return;
}
// 3 cases :
// 1. We''re removing a leaf node
// 2. We''re removing a node with a single child
// 3. we''re removing a node with 2 children
// Node with single child
if((curr->left == NULL && curr->right != NULL) || (curr->left != NULL && curr->right == NULL))
{
if(curr->left == NULL && curr->right != NULL)
{
if(parent->left == curr)
{
parent->left = curr->right;
delete curr;
}
else
{
parent->right = curr->left;
delete curr;
}
}
return;
}
//We''re looking at a leaf node
if( curr->left == NULL && curr->right == NULL)
{
if(parent->left == curr)
{
parent->left = NULL;
}
else
{
parent->right = NULL;
}
delete curr;
return;
}
//Node with 2 children
// replace node with smallest value in right subtree
if (curr->left != NULL && curr->right != NULL)
{
tree_node* chkr;
chkr = curr->right;
if((chkr->left == NULL) && (chkr->right == NULL))
{
curr = chkr;
delete chkr;
curr->right = NULL;
}
else // right child has children
{
//if the node''s right child has a left child
// Move all the way down left to locate smallest element
if((curr->right)->left != NULL)
{
tree_node* lcurr;
tree_node* lcurrp;
lcurrp = curr->right;
lcurr = (curr->right)->left;
while(lcurr->left != NULL)
{
lcurrp = lcurr;
lcurr = lcurr->left;
}
curr->data = lcurr->data;
delete lcurr;
lcurrp->left = NULL;
}
else
{
tree_node* tmp;
tmp = curr->right;
curr->data = tmp->data;
curr->right = tmp->right;
delete tmp;
}
}
return;
}
}
void BinarySearchTree::print_postorder()
{
postorder(root);
}
void BinarySearchTree::postorder(tree_node* p)
{
if(p != NULL)
{
if(p->left) postorder(p->left);
if(p->right) postorder(p->right);
cout<<" "<<p->data<<"/n ";
}
else return;
}
int main()
{
BinarySearchTree b;
int ch,tmp,tmp1;
while(1)
{
cout<<endl<<endl;
cout<<" Binary Search Tree Operations "<<endl;
cout<<" ----------------------------- "<<endl;
cout<<" 1. Insertion/Creation "<<endl;
cout<<" 2. Printing "<<endl;
cout<<" 3. Removal "<<endl;
cout<<" 4. Exit "<<endl;
cout<<" Enter your choice : ";
cin>>ch;
switch(ch)
{
case 1 : cout<<" Enter Number to be inserted : ";
cin>>tmp;
b.insert(tmp);
i++;
break;
case 2 : cout<<endl;
cout<<" Printing "<<endl;
cout<<" --------------------"<<endl;
b.print_postorder();
break;
case 3 : cout<<" Enter data to be deleted : ";
cin>>tmp1;
b.remove(tmp1);
break;
case 4:
return 0;
}
}
}
Aquí está la rutina de preorden que imprime un gráfico general de árbol de una manera compacta
void preOrder(Node* nd, bool newLine=false,int indent=0)
{
if(nd != NULL) {
if (newLine && indent) {
std::cout << "/n" << std::setw(indent) << '' ''
} else if(newLine)
std::cout << "/n";
cout<< nd->_c;
vector<Node *> &edges=nd->getEdges();
int eSize=edges.size();
bool nwLine=false;
for(int i=0; i<eSize; i++) {
preOrder(edges[i],nwLine,indent+1);
nwLine=true;
}
}
}
int printGraph()
{
preOrder(root,true);
}
Aquí está mi código. Se imprime muy bien, quizás no sea perfectamente simétrico. pequeña descripción:
- 1era función - imprime nivel por nivel (raíz lv -> hojas lv)
- 2da función - distancia desde el comienzo de la nueva línea
- Tercera función: imprime nodos y calcula la distancia entre dos impresiones;
void Tree::TREEPRINT()
{
int i = 0;
while (i <= treeHeight(getroot())){
printlv(i);
i++;
cout << endl;
}
}
void Tree::printlv(int n){
Node* temp = getroot();
int val = pow(2, treeHeight(root) -n+2);
cout << setw(val) << "";
prinlv(temp, n, val);
}
void Tree::dispLV(Node*p, int lv, int d)
{
int disp = 2 * d;
if (lv == 0){
if (p == NULL){
cout << " x ";
cout << setw(disp -3) << "";
return;
}
else{
int result = ((p->key <= 1) ? 1 : log10(p->key) + 1);
cout << " " << p->key << " ";
cout << setw(disp - result-2) << "";
}
}
else
{
if (p == NULL&& lv >= 1){
dispLV(NULL, lv - 1, d);
dispLV(NULL, lv - 1, d);
}
else{
dispLV(p->left, lv - 1, d);
dispLV(p->right, lv - 1, d);
}
}
}
Entrada:
50-28-19-30-29-17-42-200-160-170-180-240-44-26-27
Aquí hay otra implementación de C ++ 98, con un tree como salida.
Salida de muestra:
PHP
└── is
├── minor
│ └── perpetrated
│ └── whereas
│ └── skilled
│ └── perverted
│ └── professionals.
└── a
├── evil
│ ├── incompetent
│ │ ├── insidious
│ │ └── great
│ └── and
│ ├── created
│ │ └── by
│ │ └── but
│ └── amateurs
└── Perl
El código:
void printTree(Node* root)
{
if (root == NULL)
{
return;
}
cout << root->val << endl;
printSubtree(root, "");
cout << endl;
}
void printSubtree(Node* root, const string& prefix)
{
if (root == NULL)
{
return;
}
bool hasLeft = (root->left != NULL);
bool hasRight = (root->right != NULL);
if (!hasLeft && !hasRight)
{
return;
}
cout << prefix;
cout << ((hasLeft && hasRight) ? "├── " : "");
cout << ((!hasLeft && hasRight) ? "└── " : "");
if (hasRight)
{
bool printStrand = (hasLeft && hasRight && (root->right->right != NULL || root->right->left != NULL));
string newPrefix = prefix + (printStrand ? "│ " : " ");
cout << root->right->val << endl;
printSubtree(root->right, newPrefix);
}
if (hasLeft)
{
cout << (hasRight ? prefix : "") << "└── " << root->left->val << endl;
printSubtree(root->left, prefix + " ");
}
}
Aquí hay un pequeño ejemplo para imprimir un montón basado en matriz en forma de árbol. Necesitaría un poco de ajuste al algoritmo para números más grandes. Acabo de hacer una cuadrícula en papel y calculé qué índice de espacio tendría cada nodo para verse bien, luego noté que había un patrón en la cantidad de espacios que cada nodo necesitaba según la cantidad de espacios de sus padres y el nivel de recursión, además de cómo alto es el árbol. Esta solución va un poco más allá de la impresión en orden de nivel y satisface el requisito de "belleza".
#include <iostream>
#include <vector>
static const int g_TerminationNodeValue = -999;
class HeapJ
{
public:
HeapJ(int* pHeapArray, int numElements)
{
m_pHeapPointer = pHeapArray;
m_numElements = numElements;
m_treeHeight = GetTreeHeight(1);
}
void Print()
{
m_printVec.clear();
int initialIndex = 0;
for(int i=1; i<m_treeHeight; ++i)
{
int powerOfTwo = 1;
for(int j=0; j<i; ++j)
{
powerOfTwo *= 2;
}
initialIndex += powerOfTwo - (i-1);
}
DoPrintHeap(1,0,initialIndex);
for(size_t i=0; i<m_printVec.size(); ++i)
{
std::cout << m_printVec[i] << ''/n'' << ''/n'';
}
}
private:
int* m_pHeapPointer;
int m_numElements;
int m_treeHeight;
std::vector<std::string> m_printVec;
int GetTreeHeight(int index)
{
const int value = m_pHeapPointer[index-1];
if(value == g_TerminationNodeValue)
{
return -1;
}
const int childIndexLeft = 2*index;
const int childIndexRight = childIndexLeft+1;
int valLeft = 0;
int valRight = 0;
if(childIndexLeft <= m_numElements)
{
valLeft = GetTreeHeight(childIndexLeft);
}
if(childIndexRight <= m_numElements)
{
valRight = GetTreeHeight(childIndexRight);
}
return std::max(valLeft,valRight)+1;
}
void DoPrintHeap(int index, size_t recursionLevel, int numIndents)
{
const int value = m_pHeapPointer[index-1];
if(value == g_TerminationNodeValue)
{
return;
}
if(m_printVec.size() == recursionLevel)
{
m_printVec.push_back(std::string(""));
}
const int numLoops = numIndents - (int)m_printVec[recursionLevel].size();
for(int i=0; i<numLoops; ++i)
{
m_printVec[recursionLevel].append(" ");
}
m_printVec[recursionLevel].append(std::to_string(value));
const int childIndexLeft = 2*index;
const int childIndexRight = childIndexLeft+1;
const int exponent = m_treeHeight-(recursionLevel+1);
int twoToPower = 1;
for(int i=0; i<exponent; ++i)
{
twoToPower *= 2;
}
const int recursionAdjust = twoToPower-(exponent-1);
if(childIndexLeft <= m_numElements)
{
DoPrintHeap(childIndexLeft, recursionLevel+1, numIndents-recursionAdjust);
}
if(childIndexRight <= m_numElements)
{
DoPrintHeap(childIndexRight, recursionLevel+1, numIndents+recursionAdjust);
}
}
};
const int g_heapArraySample_Size = 14;
int g_heapArraySample[g_heapArraySample_Size] = {16,14,10,8,7,9,3,2,4,1,g_TerminationNodeValue,g_TerminationNodeValue,g_TerminationNodeValue,0};
int main()
{
HeapJ myHeap(g_heapArraySample,g_heapArraySample_Size);
myHeap.Print();
return 0;
}
/* output looks like this:
16
14 10
8 7 9 3
2 4 1 0
*/
De tu raíz, cuenta el número de tus hijos izquierdos. Del número total de hijos abandonados, continúe imprimiendo la raíz con la sangría del número de hijos abandonados. Vaya al siguiente nivel del árbol con el número decrementado de sangría para el niño izquierdo, seguido de dos sangrías iniciales para el niño derecho. Disminuye la sangría del niño izquierdo en función de su nivel y su padre con una doble sangría para su hermano derecho.
Haga un recorrido en orden, descendiendo a los niños antes de pasar a los hermanos. En cada nivel, es cuando desciendes a un niño, aumenta la sangría. Después de cada nodo que imprima, imprima una nueva línea.
Algunos psuedocode. Llame a Print con la raíz de su árbol.
void PrintNode(int indent, Node* node)
{
while (--indent >= 0)
std::cout << " ";
std::cout << node->value() << "/n";
}
void PrintNodeChildren(int indent, Node* node)
{
for (int child = 0; child < node->ChildCount(); ++child)
{
Node* childNode = node->GetChild(child);
PrintNode(indent, childNode);
PrintNodeChildren(indent + 1, childNode);
}
}
void Print(Node* root)
{
int indent = 0;
PrintNode(indent, root);
PrintNodeChildren(indent + 1, root);
}
Nunca va a ser lo suficientemente bonito, a menos que uno haga un seguimiento para recalibrar la salida de la pantalla. Pero uno puede emitir árboles binarios bastante bonitos de manera eficiente mediante heurísticas: dada la altura de un árbol, uno puede adivinar cuál es el ancho esperado y la cantidad de nodos a diferentes profundidades. Hay algunas piezas necesarias para hacer esto, así que comencemos con las funciones de nivel superior primero para proporcionar contexto.
La función de impresión bonita:
// create a pretty vertical tree
void postorder(Node *p)
{
int height = getHeight(p) * 2;
for (int i = 0 ; i < height; i ++) {
printRow(p, height, i);
}
}
El código anterior es fácil. La lógica principal está en la función printRow. Vamos a ahondar en eso.
void printRow(const Node *p, const int height, int depth)
{
vector<int> vec;
getLine(p, depth, vec);
cout << setw((height - depth)*2); // scale setw with depth
bool toggle = true; // start with left
if (vec.size() > 1) {
for (int v : vec) {
if (v != placeholder) {
if (toggle)
cout << "/" << " ";
else
cout << "//" << " ";
}
toggle = !toggle;
}
cout << endl;
cout << setw((height - depth)*2);
}
for (int v : vec) {
if (v != placeholder)
cout << v << " ";
}
cout << endl;
}
getLine () hace lo que cabría esperar: almacena todos los nodos con una profundidad igual dada en vec. Aquí está el código para eso:
void getLine(const Node *root, int depth, vector<int>& vals)
{
if (depth <= 0 && root != nullptr) {
vals.push_back(root->val);
return;
}
if (root->left != nullptr)
getLine(root->left, depth-1, vals);
else if (depth-1 <= 0)
vals.push_back(placeholder);
if (root->right != nullptr)
getLine(root->right, depth-1, vals);
else if (depth-1 <= 0)
vals.push_back(placeholder);
}
Ahora de vuelta a printRow (). Para cada línea, establecemos el ancho del flujo en función de la profundidad del árbol binario. Este formato será agradable porque, por lo general, cuanto más profundo vaya, más ancho será necesario. Digo típicamente porque en árboles degenerados, esto no se vería tan bonito. Siempre que el árbol esté más o menos equilibrado y sea pequeño (<20 elementos), debería quedar bien. Se necesita un marcador de posición para alinear los caracteres ''/'' y ''/' correctamente. Entonces, cuando se obtiene una fila a través de getLine (), insertamos el marcador de posición si no hay ningún nodo presente en la profundidad especificada. El marcador de posición se puede establecer en algo como (1<<31) por ejemplo. Obviamente, esto no es robusto porque el marcador de posición podría ser un valor de nodo válido. Si un codificador se descompone y solo trata con decimales, uno podría modificar el código para emitir cadenas convertidas decimales a través de getLine () y usar un marcador de posición como "_". (Desafortunadamente, no soy un codificador así: P)
El resultado para los siguientes elementos insertados en orden: 8, 12, 4, 2, 5, 15 es
8
/ /
4 12
/ / /
2 5 15
getHeight () se deja al lector como un ejercicio. :) Incluso se pueden obtener resultados más bonitos al actualizar de forma retroactiva la red de nodos poco profundos en función del número de elementos en los nodos más profundos. Eso también se deja al lector como un ejercicio.
Para imprimir un árbol de forma recursiva, debe pasar dos argumentos a su función de impresión:
- El nodo del árbol a imprimir, y
- El nivel de sangría
Por ejemplo, puedes hacer esto:
void BinarySearchTree::postorder(tree_node* p, int indent=0)
{
if(p != NULL) {
if(p->left) postorder(p->left, indent+4);
if(p->right) postorder(p->right, indent+4);
if (indent) {
std::cout << std::setw(indent) << '' '';
}
cout<< p->data << "/n ";
}
}
La llamada inicial debe ser postorder(root);
Si desea imprimir el árbol con la raíz en la parte superior, mueva cout a la parte superior del if .
Para una matriz, encuentro esto mucho más conciso. Simplemente pasar en la matriz. Podría mejorarse para manejar números muy grandes (longitudes de dígitos largas). Copiar y pegar para c ++ :)
#include <math.h>
using namespace std;
void printSpace(int count){
for (int x = 0; x<count; x++) {
cout<<"-";
}
}
void printHeap(int heap[], int size){
cout<<endl;
int height = ceil(log(size)+1); //+1 handle the last leaves
int width = pow(2, height)*height;
int index = 0;
for (int x = 0; x <= height; x++) { //for each level of the tree
for (int z = 0; z < pow(2, x); z++) { // for each node on that tree level
int digitWidth = 1;
if(heap[index] != 0) digitWidth = floor(log10(abs(heap[index]))) + 1;
printSpace(width/(pow(2,x))-digitWidth);
if(index<size)cout<<heap[index++];
else cout<<"-";
printSpace(width/(pow(2,x)));
}
cout<<endl;
}
}
Si su única necesidad es visualizar su árbol, un método mejor sería mostrarlo en un formato de punto y dibujarlo con grapviz.
Puede consultar la guía de puntos para obtener más información sobre la sintaxis, etc.
Tengo un código más fácil .......... Considero un árbol hecho de nodos de estructura
struct treeNode{
treeNode *lc;
element data;
short int bf;
treeNode *rc;
};
La profundidad del árbol se puede encontrar usando
int depth(treeNode *p){
if(p==NULL) return 0;
int l=depth(p->lc);
int r=depth(p->rc);
if(l>=r)
return l+1;
else
return r+1;
}
debajo de la función gotoxy mueve el cursor a la posición deseada
void gotoxy(int x,int y)
{
printf("%c[%d;%df",0x1B,y,x);
}
Luego imprimiendo un árbol se puede hacer como:
void displayTreeUpDown(treeNode * root,int x,int y,int px=0){
if(root==NULL) return;
gotoxy(x,y);
int a=abs(px-x)/2;
cout<<root->data.key;
displayTreeUpDown(root->lc,x-a,y+1,x);
displayTreeUpDown(root->rc,x+a,y+1,x);
}
que se puede llamar usando:
display(t,pow(2,depth(t)),1,1);
#include <stdio.h>
#include <stdlib.h>
struct Node
{
struct Node *left,*right;
int val;
} *root=NULL;
int rec[1000006];
void addNode(int,struct Node*);
void printTree(struct Node* curr,int depth)
{
int i;
if(curr==NULL)return;
printf("/t");
for(i=0;i<depth;i++)
if(i==depth-1)
printf("%s/u2014/u2014/u2014",rec[depth-1]?"/u0371":"/u221F");
else
printf("%s ",rec[i]?"/u23B8":" ");
printf("%d/n",curr->val);
rec[depth]=1;
printTree(curr->left,depth+1);
rec[depth]=0;
printTree(curr->right,depth+1);
}
int main()
{
root=(struct Node*)malloc(sizeof(struct Node));
root->val=50;
//addNode(50,root);
addNode(75,root); addNode(25,root);
addNode(15,root); addNode(30,root);
addNode(100,root); addNode(60,root);
addNode(27,root); addNode(31,root);
addNode(101,root); addNode(99,root);
addNode(5,root); addNode(61,root);
addNode(55,root); addNode(20,root);
addNode(0,root); addNode(21,root);
//deleteNode(5,root);
printTree(root,0);
return 0;
}
void addNode(int v,struct Node* traveller)
{
struct Node *newEle=(struct Node*)malloc(sizeof(struct Node));
newEle->val=v;
for(;;)
{
if(v<traveller->val)
{
if(traveller->left==NULL){traveller->left=newEle;return;}
traveller=traveller->left;
}
else if(v>traveller->val)
{
if(traveller->right==NULL){traveller->right=newEle;return;}
traveller=traveller->right;
}
else
{
printf("%d Input Value is already present in the Tree !!!/n",v);
return;
}
}
}
Espero que lo encuentres bonito.
Salida:
50
ͱ———25
⎸ ͱ———15
⎸ ⎸ ͱ———5
⎸ ⎸ ⎸ ͱ———0
⎸ ⎸ ∟———20
⎸ ⎸ ∟———21
⎸ ∟———30
⎸ ͱ———27
⎸ ∟———31
∟———75
ͱ———60
⎸ ͱ———55
⎸ ∟———61
∟———100
ͱ———99
∟———101
void btree::postorder(node* p, int indent)
{
if(p != NULL) {
if(p->right) {
postorder(p->right, indent+4);
}
if (indent) {
std::cout << std::setw(indent) << '' '';
}
if (p->right) std::cout<<" //n" << std::setw(indent) << '' '';
std::cout<< p->key_value << "/n ";
if(p->left) {
std::cout << std::setw(indent) << '' '' <<" ///n";
postorder(p->left, indent+4);
}
}
}
Con este árbol:
btree *mytree = new btree();
mytree->insert(2);
mytree->insert(1);
mytree->insert(3);
mytree->insert(7);
mytree->insert(10);
mytree->insert(2);
mytree->insert(5);
mytree->insert(8);
mytree->insert(6);
mytree->insert(4);
mytree->postorder(mytree->root);
Llevaría a este resultado:
//Binary tree (pretty print):
// ________________________50______________________
// ____________30 ____________70__________
// ______20____ 60 ______90
// 10 15 80
// prettyPrint
public static void prettyPrint(BTNode node) {
// get height first
int height = heightRecursive(node);
// perform level order traversal
Queue<BTNode> queue = new LinkedList<BTNode>();
int level = 0;
final int SPACE = 6;
int nodePrintLocation = 0;
// special node for pushing when a node has no left or right child (assumption, say this node is a node with value Integer.MIN_VALUE)
BTNode special = new BTNode(Integer.MIN_VALUE);
queue.add(node);
queue.add(null); // end of level 0
while(! queue.isEmpty()) {
node = queue.remove();
if (node == null) {
if (!queue.isEmpty()) {
queue.add(null);
}
// start of new level
System.out.println();
level++;
} else {
nodePrintLocation = ((int) Math.pow(2, height - level)) * SPACE;
System.out.print(getPrintLine(node, nodePrintLocation));
if (level < height) {
// only go till last level
queue.add((node.left != null) ? node.left : special);
queue.add((node.right != null) ? node.right : special);
}
}
}
}
public void prettyPrint() {
System.out.println("/nBinary tree (pretty print):");
prettyPrint(root);
}
private static String getPrintLine(BTNode node, int spaces) {
StringBuilder sb = new StringBuilder();
if (node.data == Integer.MIN_VALUE) {
// for child nodes, print spaces
for (int i = 0; i < 2 * spaces; i++) {
sb.append(" ");
}
return sb.toString();
}
int i = 0;
int to = spaces/2;
for (; i < to; i++) {
sb.append('' '');
}
to += spaces/2;
char ch = '' '';
if (node.left != null) {
ch = ''_'';
}
for (; i < to; i++) {
sb.append(ch);
}
String value = Integer.toString(node.data);
sb.append(value);
to += spaces/2;
ch = '' '';
if (node.right != null) {
ch = ''_'';
}
for (i += value.length(); i < to; i++) {
sb.append(ch);
}
to += spaces/2;
for (; i < to; i++) {
sb.append('' '');
}
return sb.toString();
}
private static int heightRecursive(BTNode node) {
if (node == null) {
// empty tree
return -1;
}
if (node.left == null && node.right == null) {
// leaf node
return 0;
}
return 1 + Math.max(heightRecursive(node.left), heightRecursive(node.right));
}