首页 > 试题广场 >

证明：如果一棵二叉树的先序序列是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条回答 1870浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号