数据结构高手帮忙看看？今年考研题目。

xgtd

今年参加考研，本来水平就很低的，碰到这样的题目，被打击的超级郁闷啊，请高手来帮忙解答一下。在此多谢了。

这样的一个二叉树，给出了该树的后续遍历序列。
B   0        E    0        D   1        G   0        H   0        F  3        C   3        A   3
每一个表格单元代表一个节点，节点的结构为：数据元素+节点描述。
节点描述说明：
0        叶子节点
1        该节点仅有左孩子
2        该节点仅有右孩子
3        该节点有左右孩子
试编制程序完成将该二叉树由给出的后序遍历序列转变为二叉链表。
procedure change(r[……],n,t)
其中的r代表存储该二叉树的数据结构，结构中采用data存储节点数据，num存储该节点的描述信息。
n代表节点数目，t指向二叉链表的根节点。二叉链表的数据结构中仅有如下项：lchild、data、rchild。
如果使用堆栈，可以使用函数init(s)——初始化堆栈，push(s,i)——入栈，pop(s)——出栈，empty(s)——测试栈是否为空。
因本人基础知识太差，文字表达水平太低，描述的不是很清楚。请热心的高手帮忙解答一下。本人不胜感激，在此多谢了。
题目给出的二叉树的结构图见附件。

[ 本帖最后由 xgtd 于 2006-1-16 14:27 编辑 ]

converse

没有时间编码,我写一下伪码,讲一下我的思路吧

初始化一个空栈用于保存结点
逐个扫描序列
    如果是叶子结点
          入栈
    如果是有左子树的结点
          取出栈中的栈顶元素做为它的左结点构成一个树,然后把新的树入栈
    如果是有右子树的结点
          取出栈中的栈顶元素做为它的右结点构成一个树,然后把新的树入栈
    如果是有左右子树的结点
          取出栈中的栈顶的两个元素元素做为它的左右右结点构成一个树,然后把新的树入栈
处理完毕

这个问题其实还是有点难度的,答上的人不会太多,所以你也不必觉得希望不大了.
我昨天在我订阅的新闻组看到南大考了一个比较偏的C++的问题,我当时就FT~~这个题目比起南大的那个问题有意思多了~~

mtx99

请问是哪个学校的题目啊?

月吻长河

这个可是最基础的题了啊

cjaizss

LZ加油，再仔细想想，数据结构入了门的人，做这道题目应该都不会有任何问题

xgtd

原帖由 cjaizss 于 2006-1-16 12:48 发表
LZ加油，再仔细想想，数据结构入了门的人，做这道题目应该都不会有任何问题

不会这么简单吧。反正不管怎么说，再把《数据结构》好好读几遍。看来还是没有读懂啊！！！
题目给的提示是说用堆栈的，跟“天桥底下的人”说的差不多，好好再琢磨一下啊。

这个题目是今年成都电子科技大学的题目，13分。

converse

这个题目涉及到对后序遍历概念的理解,递归的理解,树的概念的理解...说白了,还是基础知识的理解如何

我觉得在中国,如果你能把严蔚敏的数据结构和配套的习题搞定,任何学校的数据结构题目都不在话下...

PS:我上面有一点遗漏,因为是后序,所以最后有左右子树的结点应该是栈顶的第一个元素是右子树,第二个是左子树....

wz_uestc

师第们的考试题目

RobinHoo

n=0
while (true)
read data ;read num
make r->data=data;n++;
if num==0
r->lchild=NULL;r->rchild=NULL;push(r);continue
else if num>1
r->rchild=pop();push(r)
else if num%2==1
r->lchild=pop();push(r)
if empty() break;
loop
t=pop()

[ 本帖最后由 RobinHoo 于 2006-1-16 22:14 编辑 ]

cjaizss

我来说一下解题的思路，既然是后序遍历，如果一共有n个节点，那么最后一个节点当然是根节点，设为root.
如果root有右子，那么第n-1个节点是右子，否则为左子（除非只有一个节点）。
然后可以递归。
先给出一个递归的解法，然后再通过递归的解法考虑非递归的解法。