用c++实现拓展先序遍历（结点用小写字母，叶子用大写字母表示）还原二叉树

好的，这是一个经典的二叉树重构问题。首先，我们需要了解拓展先序遍历的定义：对于一棵二叉树，拓展先序遍历的方式是先输出根节点，然后对于每个非空节点，按照先左后右的顺序输出其左右子节点或者空节点（用 # 表示）。

例如，对于下面这棵二叉树：

    a
   / \
  B   C
 / \
D   e

它的拓展先序遍历为：aBDE#e##C##。

接下来，我们可以采用递归的方式来还原这棵二叉树：

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

struct Node {
    char val;
    Node* left;
    Node* right;
    Node(char v) : val(v), left(nullptr), right(nullptr) {}
};

Node* buildTree(string& s, int& i) {
    if (i >= s.length()) {
        return nullptr;
    }
    char c = s[i++];
    if (c == '#') {
        return nullptr;
    }
    Node* root = new Node(c);
    root->left = buildTree(s, i);
    root->right = buildTree(s, i);
    return root;
}

void inorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

int main() {
    string s = "aBDE#e##C##";
    int i = 0;
    Node* root = buildTree(s, i);
    inorderTraversal(root); // 输出 D B e a C
    return 0;
}

在上述代码中，我们首先定义了一个 `Node` 结构体来表示二叉树的节点，其中包含了节点的值以及左右子节点的指针。然后，我们定义了一个 `buildTree` 函数来递归地构建二叉树，输入参数为拓展先序遍历字符串 `s` 和当前遍历到的位置 `i`，输出结果为构建好的二叉树的根节点指针。具体来说，我们首先取出字符串 `s` 当前位置的字符 `c`，如果是 `#`，则返回空节点；否则，新建一个节点，并递归构建其左右子树。最后，我们在 `main` 函数中调用 `buildTree` 函数构建二叉树，并使用 `inorderTraversal` 函数中序遍历输出结果。

希望这个例子能够帮助你理解如何用 C++ 实现拓展先序遍历还原二叉树。