24小时热门版块排行榜

>论坛更新日志 (4019)
>虫友互识 (838)
>导师招生 (373)
>文献求助 (274)
>考博 (226)
>休闲灌水 (217)
>硕博家园 (177)
>论文投稿 (143)
>博后之家 (114)
>考研 (106)
>公派出国 (57)
>教师之家 (56)
>招聘信息布告栏 (54)
>精细化工 (53)
>基金申请 (46)
>论文道贺祈福 (32)

返回列表

秦时明月s

金虫 (小有名气)

应助: 0 (幼儿园)
金币: 751.4
帖子: 239
在线: 68.4小时
虫号: 1100199

[交流] 【求助】关于二叉树的遍历问题？

今天看数据结构的时候，发现一句话不理解，请教各位？麻烦了？
若一个节点是某子树在中序下的最后一个节点，则它必是该子树在先序下的最后一个节点。
若 A为某树的根节点，B为左孩子，B的右孩子为C,B没有左孩子。。
那先序遍历为 ABC
中序遍历为 BCA
那么中序遍历的最后一个节点，为什么不是先序遍历的最后一个节点？？
不知道，大家看明白了没有。。在这里先谢谢大家了

  题目是：在中序线索二叉树上查找任意节点在先序下的后继
算法如下：
typedef enum PointerTag { Link, Thread};
typedef struct BiThrNode{
      TElemType    data;
      struct BiThrNode *lchild ,*rchild;
      PointerTag          LTag, RTag;

      } BiThrNode, * BiThrTree;

BiThrTree  IPrePostNode(BiThrTree head,BiThrTee p) {
//中序线索二叉树上寻找节点P的先序后继节点，head 为线索树的头结点
BiThrTree post;
if(p->LTag==0)  post=p->lchild;
  else{
            post=p;
            while(post->RTag==1&&post->rchild!=head)
            post=post->rchild;
               post=post->rchild;
            }
         return(post);
}

[ Last edited by 秦时明月s on 2011-4-4 at 19:50 ]

回复此楼

» 猜你喜欢

为什么中国大学工科教授们水了那么多所谓的顶会顶刊，但还是做不出宇树机器人？已经有9人回复
版面费该交吗已经有9人回复
体制内长辈说体制内绝大部分一辈子在底层，如同你们一样大部分普通教师忙且收入低已经有13人回复
面上可以超过30页吧？已经有4人回复
“人文社科而论，许多学术研究还没有达到民国时期的水平” 已经有5人回复
什么是人一生最重要的？已经有4人回复

» 本主题相关价值贴推荐，对您同样有帮助:

【分享】数据结构算法与应用 C++语言描述已经有9人回复

» 抢金币啦！回帖就可以得到:

查看全部散金贴

1楼 2011-04-04 18:51:54

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

sudo

木虫 (正式写手)

秦时明月s(金币+5): 2011-04-04 19:54:28

原文是什么？“若一个节点是某子树在中序下的最后一个节点，则它必是该子树在先序下的最后一个节点”

里面的树指的是“什么树”，更具体地，指的是“什么种类的二叉树”？

另外你举的例子的分析结果是对的，至于为什么和这句话矛盾，需要仔细考察一下上面的问题

赞一下

回复此楼

2楼2011-04-04 19:28:38

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

秦时明月s

金虫 (小有名气)

应助: 0 (幼儿园)
金币: 751.4
帖子: 239
在线: 68.4小时
虫号: 1100199

引用回帖:

Originally posted by sudo at 2011-04-04 19:28:38:
原文是什么？“若一个节点是某子树在中序下的最后一个节点，则它必是该子树在先序下的最后一个节点”

里面的树指的是“什么树”，更具体地，指的是“什么种类的二叉树”？

另外你举的例子的分析结果是对的， ...

是中序线索二叉树啊。。我具体了题目，麻烦了

赞一下

回复此楼

3楼2011-04-04 19:51:06

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖