二叉树的先序遍历序列为ABCDEF,中序遍历序列为CBDAEF,则后序遍历序列为
时间: 2024-05-29 22:14:12 浏览: 104
二叉树的前,中,后序遍历
4星 · 用户满意度95%
根据先序遍历序列找到根节点为A,再在中序遍历序列中找到A的位置,可以将中序遍历序列分为CBDA和EF两部分。由于是二叉树,因此先序遍历序列中B和C一定是A的左右子节点,同理D、E、F一定是A的右子树的节点。
接下来可以递归处理左子树和右子树。左子树的先序遍历序列为BCD,中序遍历序列为CBD,可以依此求得左子树的后序遍历序列DCB。右子树的先序遍历序列为EF,中序遍历序列为EAF,可以依此求得右子树的后序遍历序列AFE。
因此,整棵树的后序遍历序列为DCBAFE。
阅读全文