C Comment «dessiner» un arbre binary sur la console

Quels algorithmes peuvent être utilisés pour dessiner un arbre binary dans la console? L’arbre est implémenté en C. Par exemple, un BST avec des numéros: 2 3 4 5 8 serait affiché dans la console en tant que:

texte alt

Découvrez l’ impression d’arbres binarys dans 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; ileft->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; iright->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; ileft != 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], xi); } } 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]; }; 

sortie:

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

Code:

 int _print_t(tnode *tree, int is_left, int offset, int depth, char s[20][255]) { char b[20]; int width = 5; if (!tree) return 0; sprintf(b, "(%03d)", tree->val); int left = _print_t(tree->left, 1, offset, depth + 1, s); int right = _print_t(tree->right, 0, offset + left + width, depth + 1, s); #ifdef COMPACT for (int i = 0; i < width; i++) s[depth][offset + left + i] = b[i]; if (depth && is_left) { for (int i = 0; i < width + right; i++) s[depth - 1][offset + left + width/2 + i] = '-'; s[depth - 1][offset + left + width/2] = '.'; } else if (depth && !is_left) { for (int i = 0; i < left + width; i++) s[depth - 1][offset - width/2 + i] = '-'; s[depth - 1][offset + left + width/2] = '.'; } #else for (int i = 0; i < width; i++) s[2 * depth][offset + left + i] = b[i]; if (depth && is_left) { for (int i = 0; i < width + right; i++) s[2 * depth - 1][offset + left + width/2 + i] = '-'; s[2 * depth - 1][offset + left + width/2] = '+'; s[2 * depth - 1][offset + left + width + right + width/2] = '+'; } else if (depth && !is_left) { for (int i = 0; i < left + width; i++) s[2 * depth - 1][offset - width/2 + i] = '-'; s[2 * depth - 1][offset + left + width/2] = '+'; s[2 * depth - 1][offset - width/2 - 1] = '+'; } #endif return left + width + right; } void print_t(tnode *tree) { char s[20][255]; for (int i = 0; i < 20; i++) sprintf(s[i], "%80s", " "); _print_t(tree, 0, 0, 0, s); for (int i = 0; i < 20; i++) printf("%s\n", s[i]); } 

Sortie:

  .----------------------(006)-------. .--(001)-------. .--(008)--. .--(-02) .--(003)-------. (007) (009) .-------(-06) (002) .--(005) .--(-08)--. (004) (-09) (-07) 

ou

  (006) +------------------------+---------+ (001) (008) +----+---------+ +----+----+ (-02) (003) (007) (009) +----+ +----+---------+ (-06) (002) (005) +---------+ +----+ (-08) (004) +----+----+ (-09) (-07) 

Quelques indications: l’espacement entre les nœuds à la même profondeur (par exemple, 2 et 4 ou 3 et 8 dans votre exemple) est fonction de la profondeur.

Chaque ligne imprimée comprend tous les nœuds de même profondeur, imprimés du nœud le plus à gauche au nœud le plus à droite.

Ainsi, vous avez besoin d’un moyen, par exemple, d’organiser vos nœuds dans des tableaux de lignes, en fonction de leur profondeur, dans l’ordre de leur caractère le plus à gauche.

À partir du nœud racine, une recherche complète couvre les nœuds dans l’ordre de la profondeur et de l’extrême gauche.

L’espacement entre les noeuds peut être trouvé en trouvant la hauteur maximale de l’arbre, en utilisant une largeur constante pour les noeuds les plus profonds et en doublant cette largeur pour chaque profondeur inférieure, de sorte que la largeur pour toute profondeur = (1 + maxdepth – currentdepth) .

Ce nombre vous donne la “largeur horizontale” imprimée de chaque nœud à une profondeur donnée.

Un nœud gauche est positionné horizontalement dans la moitié gauche de la largeur de son parent, un nœud droit dans la moitié droite. Vous allez insérer des espaceurs factices pour tout nœud sans parents; un moyen plus simple d’y parvenir serait de s’assurer que toutes les feuilles sont à la même profondeur que le nœud le plus profond, avec une valeur vide comme valeur. De toute évidence, vous devrez également compenser la largeur des valeurs, peut-être en faisant la largeur de la plus grande profondeur au moins aussi large que celle imprimée (représentation décimale, probablement) du plus grand nœud valorisé.

Voici une autre prise quand une arborescence est implémentée dans array:

 #include  #include  #define PARENT(i) ((i-1) / 2) #define NUM_NODES 15 #define LINE_WIDTH 70 int main() { int tree[NUM_NODES]={0,1,2,3,4,5,6,7,8,9,1,2,3,4,5}; int print_pos[NUM_NODES]; int i, j, k, pos, x=1, level=0; print_pos[0] = 0; for(i=0,j=1; i 

Sortie:

  0 1-----------------------------------2 3-----------------4 5-----------------6 7---------8 9---------1 2---------3 4---------5 

J’ai cette petite solution en c ++ – elle pourrait facilement être convertie en c.

Ma solution nécessite une structure de données supplémentaire pour stocker la profondeur du nœud actuel dans l’arborescence (cela parce que si vous travaillez avec une arborescence incomplète, la profondeur d’un sous-arbre peut ne pas correspondre à sa profondeur dans l’arbre complet).

 #include  #include  #include  #include  namespace tree { template struct node { T data; node* l; node* r; node(T&& data_ = T()) : data(std::move(data_)), l(0), r(0) {} }; template int max_depth(node* n) { if (!n) return 0; return 1 + std::max(max_depth(n->l), max_depth(n->r)); } template void prt(node* n) { struct node_depth { node* n; int lvl; node_depth(node* 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 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  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 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 ce qui suit:

  0 1 2 3 4 5 6 

Regardez la sortie de la commande pstree sous Linux. Il ne produit pas la sortie dans la forme exacte que vous voulez, mais à mon humble avis, c’est plus lisible de cette manière.

Je seconde la recommandation de litb. Je devais le faire récemment pour imprimer l’arborescence VAD d’un processus Windows et j’ai utilisé le langage DOT (il suffit d’imprimer les nœuds de votre fonction de parcours d’arbre binary):

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

Par exemple, votre fichier DOT contiendrait:

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

Vous générez le graphique avec dotty.exe ou convertissez-le en PNG en utilisant dot.exe.

Une solution d’impression C ++ très simple dans un sens horizontal:

 5 1 5 9 7 14 

Le code (fonction Node::print() est ce qui compte):

 #include using namespace std; class Tree; class Node{ public: Node(int val): _val(val){} int val(){ return _val; } void add(Node *temp) { if (temp->val() > _val) { if (_rchild) _rchild->add(temp); else { _rchild = temp; } } else { if (_lchild) _lchild->add(temp); else { _lchild = temp; } } } void print() { for (int ix = 0; ix < _level; ++ix) cout << ' '; cout << _val << endl; ++_level; if (_lchild) { _lchild->print(); --_level; } if (_rchild) { _rchild->print(); --_level; } } private: int _val; Node *_lchild; Node *_rchild; static int _level; }; int Node::_level = 0; class Tree{ public: Tree(): _root(0){} void add(int val) { Node *temp = new Node(val); if (!_root) _root = temp; else _root->add(temp); } void print() { if (!_root) return; _root->print(); } private: Node *_root; }; int main() { Tree tree; tree.add(5); tree.add(9); tree.add(1); tree.add(7); tree.add(5); tree.add(14); tree.print(); } 

Je pense que vous ne devriez pas le coder vous-même, mais regardez Tree :: Visualize qui semble être une belle implémentation Perl avec différents styles possibles et utilisez / portez l’un des algorithmes.

J’ai un programme Ruby qui calcule les coordonnées où chaque noeud d’un arbre binary doit être dessiné ici: http://hectorcorrea.com/Blog/Drawing-a-Binary-Tree-in-Ruby

Ce code utilise un algorithme très basique pour calculer les coordonnées et ce n’est pas “efficace en surface” mais c’est un bon début. Si vous voulez voir le code “live”, vous pouvez le tester ici: http://binarytree.heroku.com/