写出根据后序和中序遍历输出先序遍历的代码
时间: 2023-07-21 07:22:12 浏览: 45
以下是根据后序和中序遍历输出先序遍历的代码,采用递归实现:
```
void postInToPre(int post[], int in[], int pre[], int postStart, int postEnd, int inStart, int inEnd, int& preIndex) {
if (postStart > postEnd || inStart > inEnd) {
return;
}
int root = post[postEnd];
int rootIndex = -1;
for (int i = inStart; i <= inEnd; i++) {
if (in[i] == root) {
rootIndex = i;
break;
}
}
pre[preIndex++] = root;
postInToPre(post, in, pre, postStart, postStart + rootIndex - inStart - 1, inStart, rootIndex - 1, preIndex);
postInToPre(post, in, pre, postStart + rootIndex - inStart, postEnd - 1, rootIndex + 1, inEnd, preIndex);
}
void printPreFromPostIn(int post[], int in[], int n) {
int pre[n];
int preIndex = 0;
postInToPre(post, in, pre, 0, n - 1, 0, n - 1, preIndex);
for (int i = 0; i < n; i++) {
cout << pre[i] << " ";
}
}
```
其中,`post` 是后序遍历数组,`in` 是中序遍历数组,`pre` 是输出的先序遍历数组,`n` 是节点数。可以通过调用 `printPreFromPostIn(post, in, n)` 来输出先序遍历结果。