创建二叉树,打出创建的实验源代码。 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
时间: 2024-02-24 22:54:52 浏览: 21
二叉树是一种重要的数据结构,它可以应用于各种场景。以下是创建二叉树的示例源代码,包括先序、中序和后序遍历。
```cpp
#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 函数中,我们分别实现了先序、中序和后序遍历。这些函数都使用递归的方式实现,具体过程可以参考代码。
以上就是创建二叉树的示例代码,希望对你有所帮助!