请问两个算法问题,热心人来帮个忙 : )

主题：请问两个算法问题,热心人来帮个忙 : )

hermione [专家分：0] 发布于 2006-09-13 17:50:00

请问两个问题:
1, 已知一个二叉树的先序遍历和层次遍历的次序,根据这两个次序来建立二叉链表.
之前看到过一个根据先序和中序次序来建立的算法, 但是这个好象不一样.那个是用
递归做的, 这个我本来打算用队列,根据位置来做, 但是又好象不对,请热心人帮帮忙!

2, 已知深度为n的二叉树采用顺序存储结构存放数组B[1...2n-1]中, 请编写一个非递归
算法产生该二叉树的二叉链表结构.
给出的题目就是这样子,我很迷惑, 这样的树唯一吗?

请热心的高手来帮帮忙, 出出点子, 谢谢哈!

本帖地址： http://bbs.pfan.cn/post/192032.html

回复列表（共7个回复）

沙发

rickone [专家分：15390] 发布于 2006-09-13 19:37:00

1题不太确定，我想如果是中序+层次应该可以确定

2题容易啊，顺序存储的求子结点和双亲都有公式，变成链表也不难吧

板凳

hermione [专家分：0] 发布于 2006-09-13 20:41:00

不好意思哈,斑竹, 有点小问题
第一题应该是中序和层次遍历;
第二题问题是在于, 结点个数是2n-1, 要求深度是n.那么这样构造的话,二叉树
不就不唯一吗?

3 楼

rickone [专家分：15390] 发布于 2006-09-13 21:04:00

第二题我想应该是2^n-1，不是2n-1

4 楼

hermione [专家分：0] 发布于 2006-09-13 21:09:00

可是题目就是2n-1, 是真题上的, 应该不会错哦!
那第一题怎么解呢?

谢谢!!

5 楼

boxertony [专家分：23030] 发布于 2006-09-14 10:58:00

对于第一题：
1。首先对于层次序列，第一个元素即二叉树的根r，在中序序列中找到r，则r的左边所有元素为r的左子树的元素，右边的为右子树的元素。
2。根据r的左右元素个数确定r的子女的个数x（0，1，2），这样根据层次序列，r后面的x个元素即为r的左右子女
3。对r的左右子女进行同样的处理，即可逐步建立起该二叉树

6 楼

boxertony [专家分：23030] 发布于 2006-09-14 11:00:00

至于第二题，要么你看错了（也许n作为上标很小），要么题目错了。

7 楼

雨523 [专家分：200] 发布于 2006-10-21 15:32:00

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：请问两个算法问题,热心人来帮个忙 : )

回复列表（共7个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：请问两个算法问题,热心人来帮个忙 : )

回复列表 （共7个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共7个回复）