设计一个程序,由给定的二叉树先序序列,建立其二叉链表存储结构,并求出二叉树的中序序列和后序序列。
时间: 2024-01-23 12:45:13 浏览: 173
好的,我可以为您提供这个程序的实现。
程序实现步骤如下:
1. 定义二叉树结构体,包括数据域和指向左右子树的指针。
2. 实现函数 buildTree,该函数接收一个数组作为先序序列,同时返回一个二叉树的根节点。在该函数内部,我们可以首先创建一个根节点,并将第一个元素作为其数据域。然后将数组分成两部分,分别为左子树和右子树的先序序列。递归调用 buildTree 函数分别创建左右子树,并将它们分别链接到根节点的左右指针上。
3. 实现函数 inorderTraversal,该函数接收一个二叉树的根节点,并返回二叉树的中序序列。在该函数内部,我们可以递归遍历左子树,输出当前节点的数据域,再递归遍历右子树。这样就可以得到二叉树的中序序列。
4. 实现函数 postorderTraversal,该函数接收一个二叉树的根节点,并返回二叉树的后序序列。在该函数内部,我们可以递归遍历左子树,递归遍历右子树,最后输出当前节点的数据域。这样就可以得到二叉树的后序序列。
下面是程序的完整实现,包括二叉树结构体定义和上述三个函数的实现:
```c++
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* buildTree(vector<int>& preorder, int& index, int left, int right) {
if (left > right) {
return NULL;
}
TreeNode* root = new TreeNode(preorder[index]);
int i;
for (i = left; i <= right; i++) {
if (preorder[index] == preorder[i]) {
break;
}
}
index++;
root->left = buildTree(preorder, index, left, i - 1);
root->right = buildTree(preorder, index, i + 1, right);
return root;
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorderHelper(root, res);
return res;
}
void inorderHelper(TreeNode* root, vector<int>& res) {
if (root == NULL) {
return;
}
inorderHelper(root->left, res);
res.push_back(root->val);
inorderHelper(root->right, res);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
postorderHelper(root, res);
return res;
}
void postorderHelper(TreeNode* root, vector<int>& res) {
if (root == NULL) {
return;
}
postorderHelper(root->left, res);
postorderHelper(root->right, res);
res.push_back(root->val);
}
int main() {
vector<int> preorder = {1, 2, 4, 5, 3, 6, 7};
int index = 0;
TreeNode* root = buildTree(preorder, index, 0, preorder.size() - 1);
vector<int> inorder = inorderTraversal(root);
vector<int> postorder = postorderTraversal(root);
cout << "Inorder: ";
for (int i = 0; i < inorder.size(); i++) {
cout << inorder[i] << " ";
}
cout << endl;
cout << "Postorder: ";
for (int i = 0; i < postorder.size(); i++) {
cout << postorder[i] << " ";
}
cout << endl;
return 0;
}
```
该程序的输出结果为:
```
Inorder: 4 2 5 1 6 3 7
Postorder: 4 5 2 6 7 3 1
```
其中 Inorder 表示中序序列,Postorder 表示后序序列。
阅读全文