输入一棵二叉树的先序和中序遍历序列,输出其后序遍历序列。请用c++,不使用类(class)实现
时间: 2025-06-29 07:09:22 浏览: 8
### 构建二叉树并输出后序遍历
为了实现从先序和中序遍历构建二叉树并输出后序遍历序列,在C++中可以定义一系列全局变量以及辅助函数来代替类结构。通过递归方法,利用先序遍历的第一个元素作为根节点,并从中序遍历中定位该根节点的位置从而划分左右子树。
#### 定义全局变量存储输入数据
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 假设已经获取到的先序(preorder)和中序(inorder)遍历序列
vector<int> preorder;
vector<int> inorder;
int preIndex = 0; // 记录当前处理的preorder索引位置
```
#### 辅助查找函数用于确定根节点在inorder中的位置
```cpp
int search(vector<int>& arr, int startIn, int endIn, int value){
for (int i=startIn;i<=endIn;i++){
if(arr[i]==value)
return i;
}
return -1;
}
```
#### 主要逻辑:重建二叉树并通过后续遍历打印结果
```cpp
void buildAndPrintPostOrder(int inStart, int inEnd){
if(inStart > inEnd){
return ;
}
// 当前子树的根节点值来自preorder数组
int currentRootValue = preorder[preIndex++];
// 找到这个根节点在inorder里的位置以便分割成左右两部分
int rootPosition = search(inorder,inStart ,inEnd,currentRootValue);
// 首先递归建立左子树
buildAndPrintPostOrder(inStart,rootPosition-1);
// 接着递归建立右子树
buildAndPrintPostOrder(rootPosition+1,inEnd);
// 后续遍历时才访问根节点
cout << currentRootValue << " ";
}
```
#### 调用上述功能完成整个过程
```cpp
int main(){
// 初始化preorder与inorder向量(这里假设已经有了具体的数值)
vector<int> examplePreorder = { /*...*/ };
vector<int> exampleInorder = { /*...*/ };
preorder = examplePreorder;
inorder = exampleInorder;
// 开始构建并输出postorder顺序
buildAndPrintPostOrder(0,exampleInorder.size()-1);
return 0;
}
```
此代码片段展示了如何基于给定的先序和中序遍历来恢复一棵二叉树,并最终以后序的方式输出这棵树上的所有节点[^1][^2][^3][^4][^5]。
阅读全文
相关推荐



















