c++ - 从前序遍历构造非二叉树

Question

给定一个节点列表和它拥有的子节点的数量，从这个列表(在先序遍历中)构建一个(非二叉)树

例如我得到以下内容:

1 3
2 1
3 0
4 0
5 0

这是一棵看起来像的树

           1
          /|\
         / | \
        2  4  5
       /
      3

我知道我应该使用递归来构造这棵树，但因为它不是二叉树，所以我对应该如何实现这个算法一头雾水。

Answer 1

在向您提供解决问题的代码之前，我想和您玩一个思维游戏。看看下图，它表示递归应该如何为您的输入展开

研究图像并注意如何仅在特定节点有子节点时才开始递归(并且它们持续输入中指示的子节点数)。

尝试在纸上想出一个代码(或伪代码)。

---

解决这个问题的代码非常简单:使用 vector<Node>存放您的 child

#include <iostream>
#include <vector>
using namespace std;

struct Node {
  Node(int v) : val(v) {}
  int val;
  vector<Node*> children;
};

Node *readTreeNode() {
  int val, children;
  cin >> val >> children;
  Node *node = new Node(val);
  for (int i = 0; i<children; ++i)
    node->children.push_back(readTreeNode());
  return node;
}

int main() {
  Node *root = readTreeNode();
  // Do the cleanup..
  return 0;
}

Live Example

注意 readTreeNode() 所在的循环函数被递归调用

for (int i = 0; i<children; ++i)
    node->children.push_back(readTreeNode());

内在 child 先于其他 child 被处理。

最后的警告:

1. 我没有实现内存处理(上面的代码泄漏内存)。做一个好公民，释放你分配的内存，或者更好的是，使用智能指针。

2. 没有错误处理(即没有检查有效输入的输入节点)