从前序遍历构造非二叉树

Question

给定一个节点列表和它拥有的子节点的数量，根据这个列表（在先序遍历中）构造一棵（非二叉）树

例如，我得到以下内容：

这是一棵看起来像

的树

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

Answer 1

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

研究图像并注意如何仅在特定节点存在 children 时才开始递归（并且它们持续输入中指示的 children 数量）。

尝试在纸上想出一个代码（或伪代码）。

解决这个问题的代码非常简单：使用 vector<Node> 来存储你的 children

#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());

内部 children 先于其他处理。

最后的警告：

我没有实现内存处理（上面的代码泄漏内存）。做一个好公民，释放你分配的内存，或者更好的是，使用智能指针。
没有错误处理（即不检查有效输入的输入节点）

从前序遍历构造非二叉树

Construct non-binary tree from pre-order traversal

c++

tree