|
作者: 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; } 这是书里面的一个遍历算法,看了N遍,但无奈智商有限,一直不能理解,请各位大侠帮帮忙, 如能详细解说,小弟不胜感激! |
地主 发表时间: 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号