21xrx.com
2024-12-22 20:06:57 Sunday
登录
文章检索 我的文章 写文章
如何在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++中打印一棵树的方法有很多,上述的三种方法都可以帮助我们打印出树的结构。我们可以根据实际应用情况选择使用合适的方法。无论是递归法、队列法还是树状数组法,都可以让我们迅速清晰地了解树的结构。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复