如何在C++中打印一棵树？ |21xrx.com

如何在C++中打印一棵树？

2023-07-04 19:37:18 深夜i -- --

C++ 打印树

在C++中打印一棵树是一件比较常见的任务，然而许多开发者对于这个问题可能不太了解该怎么处理。在本文中，我们将会介绍一些用于在C++中打印树的方法。

1. 递归法

递归是一种常用的方法，它可以用来打印一棵树。下面是一份简短的例子代码，它可以打印以“根节点”为起点的树：


void print_tree(Node* root, int depth) {
  if(root == NULL) return;
  print_tree(root->right, depth + 1);
  for(int i = 0; i < depth; i++) cout << "  ";
  cout << root->value << endl;
  print_tree(root->left, depth + 1);
}

这个方法使用深度优先搜索，先遍历右子树，再打印根节点，最后遍历左子树。为了使输出有序，我们使用了缩进来表示每个节点的深度。需要注意的是，本例中使用的是前序遍历，其他的遍历方式也可以被用来打印树。

2. 队列法

队列法是一种新颖的方法，它利用了队列的数据结构来打印树。这个方法需要把树的每一层节点按顺序加入队列中，然后依次取出每个节点并打印它们。具体的实现方法如下：


void print_tree(Node* root) {
  queue<Node*> que;
  int level = 0;
  que.push(root);
  while(!que.empty()) {
    int n = que.size();
    for(int i = 0; i < n; i++) {
      Node* cur = que.front();
      que.pop();
      cout << cur->value << " ";
      if(cur->left) que.push(cur->left);
      if(cur->right) que.push(cur->right);
    }
    level++;
    cout << endl;
  }
}

在这个方法中，每一次循环都会处理一层的节点。通过取出队列中的每个节点，我们能够逐层打印出树的结构。值得注意的是，该方法的时间复杂度为 O(n)，其中n是节点总数。

3. 树状数组法

树状数组法是一种基于树状数组数据结构来实现的方法。该方法将树中所有节点按层级和顺序储存到数组中，然后从左到右输出这个数组。具体的实现方法如下：


void print_tree(Node* root, vector<Node*>& nodes) {
  if(root == NULL) return;
  nodes.push_back(root);
  print_tree(root->left, nodes);
  print_tree(root->right, nodes);
}
void print_tree(Node* root) {
  vector<Node*> nodes;
  print_tree(root, nodes);
  int n = nodes.size();
  int depth = 0;
  while(pow(2, depth) <= n) depth++;
  int width = pow(2, depth) - 1;
  Node* null_node = new Node(0); // 用于表示树中的空节点
  for(int i = 0, offset = 0; i < depth; i++) {
    int level_width = pow(2, i);
    for(int j = 0; j < level_width; j++) {
      int index = offset + j;
      if(index >= n) break;
      if(nodes[index] == NULL) cout << "  ";
      else cout << setw(4) << nodes[index]->value;;
      for(int k = 0; k < width / level_width; k++) cout << "  ";
    }
    offset += level_width;
    cout << endl;
  }
}

在这个方法中，首先将树中所有节点按顺序储存到一个数组中，然后根据层数和节点数量计算出需要多少空间来打印这棵树。接下来，我们根据数组中的节点顺序，逐行输出树的结构。对于不存在的节点，我们可以用一个特殊的占位节点来补位。

总结

在C++中打印一棵树的方法有很多，上述的三种方法都可以帮助我们打印出树的结构。我们可以根据实际应用情况选择使用合适的方法。无论是递归法、队列法还是树状数组法，都可以让我们迅速清晰地了解树的结构。

上一篇: idea打包java可执行jar包

下一篇: C++类的实现代码

评论区

()

相似文章