首页 > 试题广场 >

证明：如果一棵二叉树的先序序列是u1，u2，…，un，中序序

[问答题]

证明：如果一棵二叉树的先序序列是u1，u2，…，un，中序序列是up1，up2，…，upn，则序列1,2，…，n可以通过一个栈得到序列p1，p2，…，pn；反之，若以上述中的结论作为前提，则存在一棵二叉树，若其前序序列是u1，u2，…，un，则其中序序列为up1，up2，…，upn。

推荐

赞花婆

两个方向的证明都利用数学归纳法。前一个结论的证明要着重研究前序序列和中序序列的性质，参见6.31题的提示；后一个结论的证明应研究序列进出栈的特点，结合考虑6.31题的提示。

发表于 2018-03-25 10:05:53 回复(0)

提交观点

问题信息

树

上传者：赞花婆

难度：

1条回答 2收藏 1902浏览

扫一扫，把题目装进口袋