|
 | 作者: bluezzb [bluezzb]
 论坛用户 |
登录 |
| status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType e)){ p=T-->lchild; while(p!=T){ while (p-->LTag==Link)p=p-->lchild; if(!Visit(p-->data))return Error; while(p-->RTag==Thread && p-->rchild!=T){ p=p-->rchild; Visit(p-->data); } p=p-->rchild; } return OK; } 这是书里面的一个遍历算法，看了Ｎ遍，但无奈智商有限，一直不能理解，请各位大侠帮帮忙， 如能详细解说，小弟不胜感激！ |
| 地主 发表时间: 04-04-20 06:49 |
| 回复: bluezzb [bluezzb] 论坛用户 |
登录 |
|
最主要是不理解它的前驱后继是如何实现的，（上面是中序遍历） |
| B1层 发表时间: 04-04-20 07:01 |
 | 回复: 286 [unique]  版主 |
登录 |
|
这是遍历算法吗？我印象中中序遍历应该是递归的吧？ 而这个程序只是找到最左子结点和第一右结点而已。 不象遍历。 |
| B2层 发表时间: 04-04-20 09:05 |
| 回复: bluezzb [bluezzb] 论坛用户 |
登录 |
|
这是遍历的非递归算法. 哪位大侠帮帮忙啊,,, |
| B3层 发表时间: 04-04-20 12:07 |
 | 回复: yingzike [yingzike]  论坛用户 |
登录 |
|
中序遍历，就是先找左边，再子根，再右边 N / \ L R 如上就是L->N->R 看语句： status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType e)){ p=T-->lchild; // 指向根子 while(p!=T){ //一直到根结点为止 while (p-->LTag == Link) p = p-->lchild; //访问根的左边子树为空的结点 if (!Visit(p-->data)) return Error; //调用函数显示，返回值非零就报错 while(p-->RTag == Thread && p-->rchild != T){ p = p-->rchild; Visit(p-->data); //继续找后继结点 } p = p-->rchild; //到右边了 } return OK; }  |
| B4层 发表时间: 04-04-20 12:48 |
| 回复: bluezzb [bluezzb] 论坛用户 |
登录 |
|
while (p-->LTag == Link) p = p-->lchild 当找到它最左的子树时,它是怎么找到它的后继的??? 好像没有返回语句呀... 谢谢 |
| B5层 发表时间: 04-04-20 12:55 |
| 回复: 286 [unique] 版主 |
登录 |
|
线索二叉树是由线索找的. |
| B6层 发表时间: 04-04-20 13:02 |
| 回复: bluezzb [bluezzb] 论坛用户 |
登录 |
|
哦,!!!!!明白了,,,,, 谢谢四楼的!!!!! thank you!!! |
| B7层 发表时间: 04-04-20 13:03 |
| 回复: bluezzb [bluezzb] 论坛用户 |
登录 |
|
一直以为 while(p-->RTag == Thread && p-->rchild != T){ p = p-->rchild; Visit(p-->data); } 到右边了,原来是在找后继... |
| B8层 发表时间: 04-04-20 13:09 |
| 回复: bluezzb [bluezzb] 论坛用户 |
登录 |
|
再问一下,先序遍历是怎样的? A / \ B C / \ / \ D E F G / \ / \ H I J K 不知是不是A B D H I E J K C F G ??? |
| B9层 发表时间: 04-04-20 16:15 |
| 回复: 286 [unique] 版主 |
登录 |
|
是的。 其实这里有个最保险的方法： 1 A (B树) (C树) 2 A (B (D树) (E树)) (C (F树) (G树)) 3 A (B (D (H树) (I树)) (E (J树) (K树))) (C F G) 4 A B D H I E J K C F G 也就是说，当你判断某个结点时，把他左下方的树看成一个点，右下方树看成一个点。 |
| B10层 发表时间: 04-04-20 17:31 |
| 回复: bluezzb [bluezzb] 论坛用户 |
登录 |
|
B9层 发表时间: 04-04-20 16:15 -------------------------------------------------------------------------------- 回复: 286 [unique] 版主 回复 收藏 是的。 其实这里有个最保险的方法： 1 A (B树) (C树) 2 A (B (D树) (E树)) (C (F树) (G树)) 3 A (B (D (H树) (I树)) (E (J树) (K树))) (C F G) 4 A B D H I E J K C F G 也就是说，当你判断某个结点时，把他左下方的树看成一个点，右下方树看成一个点。 thank you! |
| B11层 发表时间: 04-04-20 22:05 |
 | 回复: ysfilone [ysfilone]  论坛用户 |
登录 |
|
呵呵 二叉树线索化是有点难 我也是看了很久才看明白的 |
| B12层 发表时间: 04-04-21 11:49 |
| 回复: bluezzb [bluezzb] 论坛用户 |
登录 |
|
晕死,再想一下,又觉得不对劲.... while(p-->RTag==Thread && p-->rchild!=T){ p=p-->rchild; Visit(p-->data); 这句是在找后继,这时的指针应该是指向最左的结点G(假设是G). 并假设这时G的后继是它的parent,但上面那句并没有实现指向parent的语句啊 求解中......... |
| B13层 发表时间: 04-04-21 18:08 |
|
20CN网络安全小组版权所有
Copyright © 2000-2010 20CN Security Group. All Rights Reserved.
论坛程序编写：NetDemon
粤ICP备05087286号
论坛: 编程破解
标题: 求助:关于数据结构线索二叉树的一个算法.