设一棵二叉树的先序序列为：A B D E G C F H中序遍历序列为：D B G E A C H F （1）画出这棵二叉树。 （2）写出该二叉树的先序、中序、后序遍历序列。 比较你写的先序和中序序列与题目的是否一致。

(1) 画出的二叉树如下所示：

        A
       / \
      B   C
     / \   \
    D   E   F
       /     \
      G       H

(2) 该二叉树的先序、中序、后序遍历序列分别为：

先序遍历序列：A B D E G C F H

中序遍历序列：D B G E A C H F

后序遍历序列：D G E B H F C A

其中，题目给出的先序遍历序列和中序遍历序列与我们求得的一致。

相关问题

创建二叉树，打出创建的实验源代码。 A B C D E # # # # F G # # #，其中 # 表示空节点。 先序遍历序列为：A B C D E F G 中序遍历序列为：D C E B A G F 后序遍历序列为：D E C B G F A

二叉树是一种重要的数据结构，它可以应用于各种场景。以下是创建二叉树的示例源代码，包括先序、中序和后序遍历。

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

struct TreeNode {
    char val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* buildTree(vector<char>& preorder, vector<char>& inorder) {
        return buildTreeHelper(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }

    TreeNode* buildTreeHelper(vector<char>& preorder, vector<char>& inorder, int p_left, int p_right, int i_left, int i_right) {
        if (p_left > p_right) return NULL;

        char root_val = preorder[p_left];
        int root_index = i_left;
        while (inorder[root_index] != root_val) {
            root_index++;
        }

        TreeNode* root = new TreeNode(root_val);
        int left_size = root_index - i_left;

        root->left = buildTreeHelper(preorder, inorder, p_left + 1, p_left + left_size, i_left, root_index - 1);
        root->right = buildTreeHelper(preorder, inorder, p_left + left_size + 1, p_right, root_index + 1, i_right);

        return root;
    }

    void preorder(TreeNode* root) {
        if (!root) return;

        cout << root->val << " ";
        preorder(root->left);
        preorder(root->right);
    }

    void inorder(TreeNode* root) {
        if (!root) return;

        inorder(root->left);
        cout << root->val << " ";
        inorder(root->right);
    }

    void postorder(TreeNode* root) {
        if (!root) return;

        postorder(root->left);
        postorder(root->right);
        cout << root->val << " ";
    }
};

int main() {
    Solution s;

    vector<char> preorder = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    vector<char> inorder = {'D', 'C', 'E', 'B', 'A', 'G', 'F'};

    TreeNode* root = s.buildTree(preorder, inorder);

    cout << "先序遍历序列为：";
    s.preorder(root);
    cout << endl;

    cout << "中序遍历序列为：";
    s.inorder(root);
    cout << endl;

    cout << "后序遍历序列为：";
    s.postorder(root);
    cout << endl;

    return 0;
}

运行结果如下：

先序遍历序列为：A B C D E F G 
中序遍历序列为：D C E B A G F 
后序遍历序列为：D E C B G F A 

以上代码中，我们首先定义了二叉树的结构体 TreeNode，其中包含节点值和左右子节点的指针。然后，我们定义了一个 Solution 类，其中包含了用于构建二叉树和遍历二叉树的函数。

在 buildTree 函数中，我们使用递归的方式构建二叉树。我们首先在先序遍历序列中找到根节点，然后在中序遍历序列中找到根节点的位置，从而可以确定左右子树的先序和中序遍历序列。然后递归构建左右子树，最终返回根节点。

在 preorder、inorder 和 postorder 函数中，我们分别实现了先序、中序和后序遍历。这些函数都使用递归的方式实现，具体过程可以参考代码。

以上就是创建二叉树的示例代码，希望对你有所帮助！

若一棵二叉树后序遍历和中序遍历序列分别为： DHEBFIGCA和DBEHAFCIG,则该二叉树对应的先序遍历序列为_和层次遍历序列为_。

根据中序遍历和后序遍历序列，可以得到该二叉树的结构如下：

         C
        / \
       /   \
      /     \
     /       \
    /         \
   /           \
  /             \
 D               I
  \             / \
   E           /   \
    \         /     \
     F       A       G
      \     /
       H   B

其中，根据后序遍历序列，最后一个节点为根节点，即G；根据中序遍历序列，G的左边为其左子树的节点，右边为其右子树的节点，因此可以划分出左子树和右子树的中序遍历序列，分别为DBEHAFC和CIG。由于中序遍历中根节点在左子树和右子树的中序遍历序列中间，因此可以得到左右子树的后序遍历序列，分别为BEHDFA和IGHC。接下来可以分别对左右子树进行递归，重建整棵二叉树。

根据先序遍历的定义，先访问根节点，然后先序遍历左子树，最后先序遍历右子树。因此，该二叉树的先序遍历序列为CGDHEFABI，层次遍历序列为GCIDFBEAH。