c++后序遍历和中序遍历建树
时间: 2023-11-26 13:13:51 浏览: 29
您好!您可以使用后序遍历和中序遍历来构建一棵二叉树。下面是一个示例代码,可以帮助您理解:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树的结点定义
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// 根据后序遍历数组和中序遍历数组构建二叉树
struct Node* buildTree(int inOrder[], int postOrder[], int inStart, int inEnd, int* postIndex) {
// 如果中序遍历的起始位置大于结束位置,表示没有结点可以构建
if (inStart > inEnd) {
return NULL;
}
// 创建新的结点,并将当前后序遍历的元素赋值给它
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = postOrder[*postIndex];
(*postIndex)--;
// 如果中序遍历的起始位置等于结束位置,表示已经到达叶子结点
if (inStart == inEnd) {
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 在中序遍历数组中找到当前结点的位置
int inIndex;
for (int i = inStart; i <= inEnd; i++) {
if (inOrder[i] == newNode->data) {
inIndex = i;
break;
}
}
// 根据当前结点的位置,递归构建左右子树
newNode->right = buildTree(inOrder, postOrder, inIndex + 1, inEnd, postIndex);
newNode->left = buildTree(inOrder, postOrder, inStart, inIndex - 1, postIndex);
return newNode;
}
// 后序遍历二叉树
void postOrderTraversal(struct Node* root) {
if (root == NULL) {
return;
}
postOrderTraversal(root->left); postOrderTraversal(root->right);
printf("%d ", root->data);
}
int main() {
int inOrder[] = {4, 8, 2, 5, 1, 6, 3, 7};
int postOrder[] = {8, 4, 5, 2, 6, 7, 3, 1};
int size = sizeof(inOrder) / sizeof(inOrder[0]);
int postIndex = size - 1;
struct Node* root = buildTree(inOrder, postOrder, 0, size - 1, &postIndex);
printf("后序遍历结果为:");
postOrderTraversal(root);
return 0;
}
```
这段代码会根据中序遍历数组和后序遍历数组构建一棵二叉树,并进行后序遍历输出。您可以根据自己的需求修改中序遍历数组和后序遍历数组,来构建相应的二叉树。希望能够帮到您!如有需要,请随时提问。