C Comment “dessiner” un Arbre Binaire de la console

Découvrez L'impression des Arbres Binaires en Ascii

De @AnyOneElse Pastbin ci-dessous:

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!Code originally from /http://www.openasthra.com/c-tidbits/printing-binary-trees-in-ascii/
!!! Just saved it, cause the website is down.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Printing Binary Trees in Ascii
Here we are not going to discuss what binary trees are (please refer this, if you are looking for binary search trees), or their operations but printing them in ascii.
The below routine prints tree in ascii for a given Tree representation which contains list of nodes, and node structure is this
struct Tree 
{
Tree * left, * right;
int element;
};
This pic illustrates what the below routine does on canvas..
ascii tree
Here is the printing routine..
b5855d39a6b8a2735ddcaa04a404c125001 
Auxiliary routines..
//This function prints the given level of the given tree, assuming
//that the node has the given x cordinate.
void print_level(asciinode *node, int x, int level) 
{
int i, isleft;
if (node == NULL) return;
isleft = (node->parent_dir == -1);
if (level == 0) 
{
for (i=0; i<(x-print_next-((node->lablen-isleft)/2)); i++) 
{
printf(" ");
}
print_next += i;
printf("%s", node->label);
print_next += node->lablen;
} 
else if (node->edge_length >= level) 
{
if (node->left != NULL) 
{
for (i=0; i<(x-print_next-(level)); i++) 
{
printf(" ");
}
print_next += i;
printf("/");
print_next++;
}
if (node->right != NULL) 
{
for (i=0; i<(x-print_next+(level)); i++) 
{
printf(" ");
}
print_next += i;
printf("\\");
print_next++;
}
} 
else 
{
print_level(node->left, 
x-node->edge_length-1, 
level-node->edge_length-1);
print_level(node->right, 
x+node->edge_length+1, 
level-node->edge_length-1);
}
}
//This function fills in the edge_length and 
//height fields of the specified tree
void compute_edge_lengths(asciinode *node) 
{
int h, hmin, i, delta;
if (node == NULL) return;
compute_edge_lengths(node->left);
compute_edge_lengths(node->right);
/* first fill in the edge_length of node */
if (node->right == NULL && node->left == NULL) 
{
node->edge_length = 0;
} 
else 
{
if (node->left != NULL) 
{
for (i=0; i<node->left->height && i < MAX_HEIGHT; i++) 
{
rprofile[i] = -INFINITY;
}
compute_rprofile(node->left, 0, 0);
hmin = node->left->height;
} 
else 
{
hmin = 0;
}
if (node->right != NULL) 
{
for (i=0; i<node->right->height && i < MAX_HEIGHT; i++) 
{
lprofile[i] = INFINITY;
}
compute_lprofile(node->right, 0, 0);
hmin = MIN(node->right->height, hmin);
} 
else 
{
hmin = 0;
}
delta = 4;
for (i=0; i<hmin; i++) 
{
delta = MAX(delta, gap + 1 + rprofile[i] - lprofile[i]);
}
//If the node has two children of height 1, then we allow the
//two leaves to be within 1, instead of 2 
if (((node->left != NULL && node->left->height == 1) ||
(node->right != NULL && node->right->height == 1))&&delta>4) 
{
delta--;
}
node->edge_length = ((delta+1)/2) - 1;
}
//now fill in the height of node
h = 1;
if (node->left != NULL) 
{
h = MAX(node->left->height + node->edge_length + 1, h);
}
if (node->right != NULL) 
{
h = MAX(node->right->height + node->edge_length + 1, h);
}
node->height = h;
}
asciinode * build_ascii_tree_recursive(Tree * t) 
{
asciinode * node;
if (t == NULL) return NULL;
node = malloc(sizeof(asciinode));
node->left = build_ascii_tree_recursive(t->left);
node->right = build_ascii_tree_recursive(t->right);
if (node->left != NULL) 
{
node->left->parent_dir = -1;
}
if (node->right != NULL) 
{
node->right->parent_dir = 1;
}
sprintf(node->label, "%d", t->element);
node->lablen = strlen(node->label);
return node;
}
//Copy the tree into the ascii node structre
asciinode * build_ascii_tree(Tree * t) 
{
asciinode *node;
if (t == NULL) return NULL;
node = build_ascii_tree_recursive(t);
node->parent_dir = 0;
return node;
}
//Free all the nodes of the given tree
void free_ascii_tree(asciinode *node) 
{
if (node == NULL) return;
free_ascii_tree(node->left);
free_ascii_tree(node->right);
free(node);
}
//The following function fills in the lprofile array for the given tree.
//It assumes that the center of the label of the root of this tree
//is located at a position (x,y).  It assumes that the edge_length
//fields have been computed for this tree.
void compute_lprofile(asciinode *node, int x, int y) 
{
int i, isleft;
if (node == NULL) return;
isleft = (node->parent_dir == -1);
lprofile[y] = MIN(lprofile[y], x-((node->lablen-isleft)/2));
if (node->left != NULL) 
{
for (i=1; i <= node->edge_length && y+i < MAX_HEIGHT; i++) 
{
lprofile[y+i] = MIN(lprofile[y+i], x-i);
}
}
compute_lprofile(node->left, x-node->edge_length-1, y+node->edge_length+1);
compute_lprofile(node->right, x+node->edge_length+1, y+node->edge_length+1);
}
void compute_rprofile(asciinode *node, int x, int y) 
{
int i, notleft;
if (node == NULL) return;
notleft = (node->parent_dir != -1);
rprofile[y] = MAX(rprofile[y], x+((node->lablen-notleft)/2));
if (node->right != NULL) 
{
for (i=1; i <= node->edge_length && y+i < MAX_HEIGHT; i++) 
{
rprofile[y+i] = MAX(rprofile[y+i], x+i);
}
}
compute_rprofile(node->left, x-node->edge_length-1, y+node->edge_length+1);
compute_rprofile(node->right, x+node->edge_length+1, y+node->edge_length+1);
}
Here is the asciii tree structure…
struct asciinode_struct
{
asciinode * left, * right;
//length of the edge from this node to its children
int edge_length; 
int height;      
int lablen;
//-1=I am left, 0=I am root, 1=right   
int parent_dir;   
//max supported unit32 in dec, 10 digits max
char label[11];  
};

de sortie:

        2
/ \
/   \
/     \
1       3
/ \     / \
0   7   9   1
/   / \     / \
2   1   0   8   8
/
7

Quelques conseils: l'espacement entre les noeuds à la même profondeur (par exemple, 2 et 4 ou 3 et 8 dans votre exemple), est une fonction de la profondeur.

Chaque imprimée ligne se compose de tous les nœuds avec la même profondeur, imprimés à partir du nœud le plus à gauche à l'extrême droite du nœud.

Si vous avez besoin d'un moyen de, par exemple, organiser vos nœuds dans des tableaux de lignes, en fonction de leur profondeur, dans l'ordre de leur la plus à gauche-ness.

De départ à partir du nœud racine, un en largeur d'abord de recherche permettra de visiter des nœuds dans l'ordre de la profondeur et de la plus à gauche-ness.

L'espacement entre les noeuds peuvent être trouvés en trouver le maximum de la hauteur de l'arbre, en utilisant une largeur constante pour le plus profond des nœuds, et du double de la largeur pour chaque profondeur moindre, de sorte que la largeur pour une profondeur = ( 1 + maxdepth - currentdepth ) * deepestwidth.

Que nombre vous donne l'impression largeur horizontale" de chaque nœud, à quelque profondeur.

Un nœud de gauche est à l'horizontale positionné dans la moitié gauche de son parent largeur, un droit nœud dans la moitié droite. Vous allez insérer un entretoises pour tout nœud qui n'ont pas de parents; un moyen plus facile de le faire serait de s'assurer que toutes les feuilles sont à la même profondeur que le nœud le plus profond, avec vide que leur valeur. Évidemment, vous aurez également à compenser la largeur des valeurs, peut-être en faisant la plus grande profondeur de largeur au moins aussi large que celui de l'imprimé (décimal représentation, sans doute) de la plus grande évalués nœud.

J'ai cette petite solution en c++, il pourrait facilement être converti en c.

Ma solution ne nécessite supplémentaire d'une structure de données pour stocker le courant du nœud de profondeur dans l'arbre (parce que si vous travaillez avec un incomplètes arbre un sous-arbre de profondeur peuvent ne pas être compatibles avec la profondeur dans l'arbre.)

#include <iostream>
#include <utility>
#include <algorithm>
#include <list>
namespace tree {
template<typename T>
struct node
{
T data;
node* l;
node* r;
node(T&& data_ = T()) : data(std::move(data_)), l(0), r(0) {}
};
template<typename T>
int max_depth(node<T>* n)
{
if (!n) return 0;
return 1 + std::max(max_depth(n->l), max_depth(n->r));
}
template<typename T>
void prt(node<T>* n)
{
struct node_depth
{
node<T>* n;
int lvl;
node_depth(node<T>* n_, int lvl_) : n(n_), lvl(lvl_) {}
};
int depth = max_depth(n);
char buf[1024];
int last_lvl = 0;
int offset = (1 << depth) - 1;
//using a queue means we perform a breadth first iteration through the tree
std::list<node_depth> q;
q.push_back(node_depth(n, last_lvl));
while (q.size())
{
const node_depth& nd = *q.begin();
//moving to a new level in the tree, output a new line and calculate new offset
if (last_lvl != nd.lvl)
{
std::cout << "\n";
last_lvl = nd.lvl;
offset = (1 << (depth - nd.lvl)) - 1;
}
//output <offset><data><offset>
if (nd.n)
sprintf(buf, " %*s%d%*s", offset, " ", nd.n->data, offset, " ");
else
sprintf(buf, " %*s", offset << 1, " ");
std::cout << buf;
if (nd.n)
{
q.push_back(node_depth(nd.n->l, last_lvl + 1));
q.push_back(node_depth(nd.n->r, last_lvl + 1));
}
q.pop_front();
}
std::cout << "\n";
}
}
int main()
{
typedef tree::node<int> node;
node* head = new node();
head->l    = new node(1);
head->r    = new node(2);
head->l->l = new node(3);
head->l->r = new node(4);
head->r->l = new node(5);
head->r->r = new node(6);
tree::prt(head);
return 0;
}

Il imprime le suivant:

        0                                                                                                
1       2                                                                                            
3   4   5   6                                                                                          

J'deuxième litb de la recommandation. J'ai eu à faire ces derniers temps pour imprimer la VAD arbre d'un processus de Windows et j'ai utilisé de la DOT de la langue (il suffit d'imprimer les nœuds de votre arbre binaire de marche de la fonction):

http://en.wikipedia.org/wiki/DOT_language

Par exemple, votre DOT fichier contient:

digraphe graphname { 
5 -> 3; 
5 -> 8; 
3 -> 4; 
3 -> 2; 
} 

Vous générer le graphique avec dotty.exe ou de le convertir en PNG à l'aide de dot.exe.

Je pense que vous ne devriez pas le code que vous-même, mais avoir un regard sur Arbre::Visualiser qui semble être un bon Perl mise en œuvre avec les différents styles possibles et de l'utilisation/port de l'un des algorithmes.