已知二叉树后序遍历序列是CDABE,中序遍历序列是CADEB,问它的前序遍历序列是?
求思考过程啊大神,学c的时候老师根本没详细讲数据结构的内容,课本上也没,求思考过程
后序遍历:若树不空,则先依次后根遍历各棵子树,然后访问根结点。(先左后右)
中序遍历:若树不空,则先访问左子树,再访问根,再访问右子树。
从后序遍历:CDABE得出E是最顶根节点。
然后中序遍历:CADEB得出CAD是E的左子树中的,B是E的右子树中的。
再分析后序遍历CDA可以知道A是CD的根,
而中序是CAD得到C是A的左子树,D是A的右子树。(如下图)
最后,先序遍历:若树不空,则先访问根结点,然后依次先根遍历各棵子树。