给出后序遍历构建二叉树c++
时间: 2023-04-09 17:04:39 浏览: 60
可以使用递归的方式来实现,具体代码如下:
struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize){
if (inorderSize == 0 || postorderSize == 0) {
return NULL;
}
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = postorder[postorderSize - 1];
int i;
for (i = 0; i < inorderSize; i++) {
if (inorder[i] == root->val) {
break;
}
}
root->left = buildTree(inorder, i, postorder, i);
root->right = buildTree(inorder + i + 1, inorderSize - i - 1, postorder + i, postorderSize - i - 1);
return root;
}
相关问题
中序后序构建二叉树C++代码
以下是中序后序构建二叉树的C++代码实现:
```
#include <iostream>
#include <string>
using namespace std;
struct BinTree {
char data;
struct BinTree *left, *right;
};
void preOrderTraversal(BinTree *root) //先序遍历
{
if (root == NULL)
return;
cout << root->data;
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
BinTree *PostIncreat(string in, string post)
{
int n = in.length(); //获取字符串长度
if (n == 0)
{
return NULL;
} //递归出口,当长度为0,则回溯。
BinTree *root = new BinTree;
char last = post[n - 1]; //获取根节点
root->data = last;
int i = 0;
while (in[i] != last)
{
i++;
}
root->left = PostIncreat(in.substr(0, i), post.substr(0, i));
root->right = PostIncreat(in.substr(i + 1, n - i - 1), post.substr(i, n - i - 1));
return root;
}
int main()
{
string in, post;
cin >> in >> post;
preOrderTraversal(PostIncreat(in, post));
return 0;
}
```
注意:要想构建二叉树,必须知道中序遍历,这样才可以知道根节点,进而确定左右子树。有前序和后序不能够构建二叉树。
用C++实现以下功能,建立一棵含有n个结点的二叉树,采用二叉链表存储; ⑵ 输出前序、中序、后序遍历该二叉树的遍历结果
以下是C++实现代码:
```cpp
#include <iostream>
using namespace std;
// 二叉树结点结构体
struct Node {
int val;
Node* left;
Node* right;
Node(int v) : val(v), left(nullptr), right(nullptr) {}
};
// 构建二叉树
Node* buildTree(int n) {
if (n == 0) return nullptr;
int rootVal;
cin >> rootVal; // 输入根节点的值
Node* root = new Node(rootVal);
root->left = buildTree(n/2); // 递归构建左子树
root->right = buildTree(n-n/2-1); // 递归构建右子树
return root;
}
// 前序遍历
void preOrder(Node* root) {
if (!root) return;
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
// 中序遍历
void inOrder(Node* root) {
if (!root) return;
inOrder(root->left);
cout << root->val << " ";
inOrder(root->right);
}
// 后序遍历
void postOrder(Node* root) {
if (!root) return;
postOrder(root->left);
postOrder(root->right);
cout << root->val << " ";
}
int main() {
int n;
cout << "请输入二叉树的结点个数:";
cin >> n;
cout << "请按照前序遍历的顺序输入结点的值:" << endl;
Node* root = buildTree(n);
cout << "前序遍历结果为:";
preOrder(root);
cout << endl << "中序遍历结果为:";
inOrder(root);
cout << endl << "后序遍历结果为:";
postOrder(root);
cout << endl;
return 0;
}
```
这里采用递归的方式构建二叉树,每次读入根节点的值,然后递归构建左子树和右子树。前序、中序、后序遍历也采用递归的方式实现。