C如何将二进制树"绘制"到控制台

Question

可以使用哪些算法在控制台中绘制二叉树？树以C实现.例如,数字:2 3 4 5 8的BST将在控制台中显示为:

Answer 1

码:

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]);
}

输出:

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

要么

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

Answer 2

查看Ascii中的打印二进制树

来自@AnyOneElse Pastbin:

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!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];  
    };

输出:

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

Answer 3

一些提示:相同深度的节点之间的间距(例如,在您的示例中为2和4或3和8)是深度的函数.

每个打印的行由具有相同深度的所有节点组成,从最左边的节点到最右边的节点打印.

因此,您需要一种方法,例如,根据它们的深度,按照它们最左边的顺序排列行数组中的节点.

从根节点开始,广度优先搜索将按深度和最左边的顺序访问节点.

节点之间的间距可以通过找到树的最大高度,使用最深节点的一些恒定宽度,以及每个较小深度的宽度加倍来找到,以便任何深度的宽度=(1 + maxdepth - currentdepth)*deepestwidth .

该数字为您提供任何特定深度的每个节点的打印"水平宽度".

左节点被水平地定位在其父代的宽度,在右半右击节点的左半部分.你将为任何没有父母的节点插入虚拟间隔; 更简单的方法是确保所有叶子与最深节点处于同一深度,并将空白作为其值.显然,您还必须补偿值的宽度,可能是通过使最大深度的宽度至少与其最大值节点的打印(十进制表示,可能)一样宽.

Answer 4

在数组中实现树时,还有以下内容:

#include <stdio.h>
#include <math.h>


#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<NUM_NODES; i++,j++) {
        pos = print_pos[PARENT(i)] + (i%2?-1:1)*(LINE_WIDTH/(pow(2,level+1))+1);

        for (k=0; k<pos-x; k++) printf("%c",i==0||i%2?' ':'-');
        printf("%d",tree[i]);

        print_pos[i] = x = pos+1;
        if (j==pow(2,level)) {
            printf("\n");
            level++;
            x = 1;
            j = 0;
        }
    }
    return 0;
}

输出:

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

Answer 5

我在c ++中有这个小解决方案 - 它可以很容易地转换为c.

我的解决方案需要一个补充数据结构来存储树中当前节点的深度(这是因为如果您使用的是不完整的树,则给定子树的深度可能与整个树中的深度不一致.)

#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;
}

它打印出以下内容:

        0                                                                                                
    1       2                                                                                            
  3   4   5   6