如果二叉搜索树的前序遍历是6、2、1、4、3、7、10、9、11，那么如何得到后序遍历呢？
问问题
80047 次
11 回答
28
给定树的前序遍历，它是通过执行以下操作构建的：输出，向左遍历，向右遍历。
由于后序遍历来自于 BST，因此您可以通过对数字进行排序，从后序遍历中推导出中序遍历（左遍历、输出、右遍历）。在您的示例中，按顺序遍历是 1、2、3、4、6、7、9、10、11。
然后我们可以从两次遍历中构造原始树。让我们为此使用一个更简单的示例：
- 预购：2、1、4、3
- 按顺序：1、2、3、4
前序遍历给我们树的根为 2。中序遍历告诉我们 1 落入左子树，3、4 落入右子树。左子树的结构很简单，因为它包含一个元素。右子树的前序遍历是通过从原始的前序遍历中取该子树中元素的顺序来推导出的：4, 3。由此我们知道右子树的根是 4 和从有序遍历 (3, 4) 我们知道 3 落入左子树。我们的最终树如下所示：
2
/ \
1 4
/
3
有了树形结构，我们可以通过遍历树得到后序遍历：向左遍历，向右遍历，输出。对于此示例，后序遍历为 1、3、4、2。
泛化算法：
- 前序遍历中的第一个元素是树的根。小于根的元素形成左子树。大于根的元素形成右子树。
- 使用步骤 1 找到左右子树的结构，其中包含我们计算出的元素在该子树中的前序遍历，这些元素按照它们在原始前序遍历中出现的顺序排列。
- 以后序遍历生成的树以获得与给定的前序遍历关联的后序遍历。
使用上述算法，问题中与前序遍历相关的后序遍历为：1、3、4、2、9、11、10、7、6。到达那里作为练习。
于 2010-12-27T10:36:46.977 回答
9
Pre-order = 按当前节点、左子树、右子树的顺序输出二叉树的值。
后序= 按左子树、右子树、当前节点的顺序输出二叉树的值。
在二叉搜索树中，左子树中所有节点的值都小于当前节点的值；和右子树一样。因此，如果您知道二叉搜索树的前序转储的开始（即其根节点的值），您可以轻松地将整个转储分解为根节点值、左子树节点的值以及右子树的节点。
为了以后序输出树，应用递归和输出重新排序。这个任务留给读者。
于 2010-12-27T10:28:49.740 回答
4
基于 Ondrej Tucny 的回答。仅适用于 BST
示例：
20
/ \
10 30
/\ \
6 15 35
预购 = 20 10 6 15 30 35
后购 = 6 15 10 35 30 20
对于 BST，先序遍历；数组的第一个元素是 20。这是我们树的根。数组中所有小于 20 的数字形成其左子树，大于 20 的数字形成右子树。
//N = number of nodes in BST (size of traversal array)
int post[N] = {0};
int i =0;
void PretoPost(int pre[],int l,int r){
if(l==r){post[i++] = pre[l]; return;}
//pre[l] is root
//Divide array in lesser numbers and greater numbers and then call this function on them recursively
for(int j=l+1;j<=r;j++)
if(pre[j]>pre[l])
break;
PretoPost(a,l+1,j-1); // add left node
PretoPost(a,j,r); //add right node
//root should go in the end
post[i++] = pre[l];
return;
}
如果有任何错误，请纠正我。
于 2011-04-04T23:28:24.663 回答
3
您将获得预购遍历结果。然后将这些值放到合适的二叉搜索树中，然后按照后序遍历算法获得 BST。
于 2011-10-18T05:28:26.650 回答
3
这是python中前序到后序遍历的代码。我正在构建一棵树，因此您可以找到任何类型的遍历
def postorder(root):
if root==None:
return
postorder(root.left)
print(root.data,end=" ")
postorder(root.right)
def preordertoposorder(a,n):
root=Node(a[0])
top=Node(0)
temp=Node(0)
temp=None
stack=[]
stack.append(root)
for i in range(1,len(a)):
while len(stack)!=0 and a[i]>stack[-1].data:
temp=stack.pop()
if temp!=None:
temp.right=Node(a[i])
stack.append(temp.right)
else:
stack[-1].left=Node(a[i])
stack.append(stack[-1].left)
return root
class Node:
def __init__(self,data):
self.data=data
self.left=None
self.right=None
a=[40,30,35,80,100]
n=5
root=preordertoposorder(a,n)
postorder(root)
# print(root.data)
# print(root.left.data)
# print(root.right.data)
# print(root.left.right.data)
# print(root.right.right.data)
于 2018-07-29T20:35:11.407 回答
1
我知道这很旧，但有更好的解决方案。
我们不必重建 BST 来从预购中获取后购。
这是一个简单的python代码，它递归地执行它：
import itertools
def postorder(preorder):
if not preorder:
return []
else:
root = preorder[0]
left = list(itertools.takewhile(lambda x: x < root, preorder[1:]))
right = preorder[len(left) + 1:]
return postorder(left) + postorder(right) + [root]
if __name__ == '__main__':
preorder = [20, 10, 6, 15, 30, 35]
print(postorder(preorder))
输出：
[6, 15, 10, 35, 30, 20]
说明：
我们知道我们已经预订了。这意味着根位于0BST 中值列表的索引处。我们知道根之后的元素是：
- first：小于 的元素
root，属于根的左子树 - 第二：大于 的元素
root，属于根的右子树
然后我们只是递归地调用两个子树上的函数（它们仍然是前序的），然后是链式left + right + root的（这是后序的）。
于 2015-01-21T21:22:19.360 回答
1
如果您已获得预购，并且您想将其转换为后购。然后你应该记住，在 BST 中，顺序总是按升序给出数字。因此，你既有 Inorder 又有构造树的前序。
预购：6, 2, 1, 4, 3, 7, 10, 9, 11
为了：1, 2, 3, 4, 6, 7, 9, 10, 11
及其后序：1 3 4 2 9 11 10 7 6
于 2017-10-19T09:06:23.860 回答
1
这里二叉搜索树的前序遍历在数组中给出。所以前序数组的第一个元素将是BST的根。我们将找到BST的左边部分和BST的右边部分。前序数组中所有小于根的元素将是左节点，并且所有前序中的元素-order 数组大于根将是右节点。
#include <bits/stdc++.h>
using namespace std;
int arr[1002];
int no_ans = 0;
int n = 1000;
int ans[1002] ;
int k = 0;
int find_ind(int l,int r,int x){
int index = -1;
for(int i = l;i<=r;i++){
if(x<arr[i]){
index = i;
break;
}
}
if(index == -1)return index;
for(int i =l+1;i<index;i++){
if(arr[i] > x){
no_ans = 1;
return index;
}
}
for(int i = index;i<=r;i++){
if(arr[i]<x){
no_ans = 1;
return index;
}
}
return index;
}
void postorder(int l ,int r){
if(l < 0 || r >= n || l >r ) return;
ans[k++] = arr[l];
if(l==r) return;
int index = find_ind(l+1,r,arr[l]);
if(no_ans){
return;
}
if(index!=-1){
postorder(index,r);
postorder(l+1,index-1);
}
else{
postorder(l+1,r);
}
}
int main(void){
int t;
scanf("%d",&t);
while(t--){
no_ans = 0;
int n ;
scanf("%d",&n);
for(int i = 0;i<n;i++){
cin>>arr[i];
}
postorder(0,n-1);
if(no_ans){
cout<<"NO"<<endl;
}
else{
for(int i =n-1;i>=0;i--){
cout<<ans[i]<<" ";
}
cout<<endl;
}
}
return 0;
}
于 2017-12-30T04:04:03.017 回答
1
正如我们所知，preOrder 遵循父、左、右系列。
为了构建树，我们需要遵循几个基本步骤：
您的问题包括系列 6、2、1、4、3、7、10、9、11
点-：
- 系列的第一个数字将是根（父），即 6
2.找到大于6的数字，所以在这个系列中，7是这个系列中的第一个更大的数字，所以右节点将从这里开始，左边到这个数字（7）是你的左子树。
6
/ \
2 7
/ \ \
1 4 10
/ / \
3 9 11
3.同样的方式遵循BST的基本规则，即left，root，right
后序序列为 L、R、N，即 1、3、4、2、9、11、10、7、6
于 2018-02-03T14:32:09.140 回答
0
这是完整的代码）
class Tree:
def __init__(self, data = None):
self.left = None
self.right = None
self.data = data
def add(self, data):
if self.data is None:
self.data = data
else:
if data < self.data:
if self.left is None:
self.left = Tree(data)
else:
self.left.add(data)
elif data > self.data:
if self.right is None:
self.right = Tree(data)
else:
self.right.add(data)
def inOrder(self):
if self.data:
if self.left is not None:
self.left.inOrder()
print(self.data)
if self.right is not None:
self.right.inOrder()
def postOrder(self):
if self.data:
if self.left is not None:
self.left.postOrder()
if self.right is not None:
self.right.postOrder()
print(self.data)
def preOrder(self):
if self.data:
print(self.data)
if self.left is not None:
self.left.preOrder()
if self.right is not None:
self.right.preOrder()
arr = [6, 2, 1, 4, 3, 7, 10, 9, 11]
root = Tree()
for i in range(len(arr)):
root.add(arr[i])
print(root.inOrder())
于 2019-05-27T06:17:38.817 回答
0
由于它是二叉搜索树，因此中序遍历将始终是已排序的元素。（左 < 根 < 右）
所以，你可以很容易地先写出它的中序遍历结果，即：1,2,3,4,6,7,9,10,11
给定预购：6、2、1、4、3、7、10、9、11
中序：左、根、右 预序：根、左、右 后序：左、右、根
现在，我们从预购中得到，那个根是 6。
现在，使用有序和预购结果： 步骤 1：
6
/ \
/ \
/ \
/ \
{1,2,3,4} {7,9,10,11}
第 2 步：下一个根是，使用中序遍历，2：
6
/ \
/ \
/ \
/ \
2 {7,9,10,11}
/ \
/ \
/ \
1 {3,4}
第 3 步：类似地，下一个根是 4：
6
/ \
/ \
/ \
/ \
2 {7,9,10,11}
/ \
/ \
/ \
1 4
/
3
第 4 步：下一个根是 3，但没有其他元素可以适合“3”的子树。现在考虑下一个根为 7，
6
/ \
/ \
/ \
/ \
2 7
/ \ \
/ \ {9,10,11}
/ \
1 4
/
3
第 5 步：下一个根是 10 ：
6
/ \
/ \
/ \
/ \
2 7
/ \ \
/ \ 10
/ \ / \
1 4 9 11
/
3
就是这样，你可以构造一棵树，最后找到它的后序遍历，即：1、3、4、2、9、11、10、7、6
于 2019-10-03T10:57:48.613 回答