以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  [求助]一道DS程序设计题  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=57115)

--  作者：sunnylee
--  发布时间：12/24/2007 12:17:00 AM

--  [求助]一道DS程序设计题
一道北邮的DS真题；
某二叉树存储结构为：flag=0,1,2，lchild,rchild两个指针域；
要求对二叉树不用堆栈、不用递归对其后序遍历，可以在不需要保留原树的情况下对其进行遍历。
--  作者：hanshumin
--  发布时间：12/24/2007 11:19:00 AM

--  
是不是穿线二叉树，如果是的，应该不是很难，关键是如何找到遍历的第一个节点，以及其之后的后继节点。这一点好象很多课本上有算法。
--  作者：daizw
--  发布时间：12/24/2007 11:42:00 AM

--  
以下是引用sunnylee在2007-12-24 0:17:00的发言：
某二叉树存储结构为：flag=0,1,2，lchild,rchild两个指针域；

flag是什么东东?

--  作者：chenminyi
--  发布时间：12/24/2007 1:33:00 PM

--  
这个题以前好像讨论过，不用递归不用堆栈就只能用反链，反链只用一个link地域但可以实现双链表的功能。我以前上机验证过单链表反链的代码。基本思想就是这样的：
...<-front-<cur  rear->...
游标向右操作是temp = rear; rear = rear->link; temp->link = cur; front = cur; cur = temp;
游标向左操作是temp = cur; cur = front; front = front->link; temp->link = rear; rear = temp;
还要注意处理最左端和最右端的情况，即front或rear为NULL的情况，你说的flag = 0|1|2，我想应该就是用来标记该结点是front,cur还是rear。
树的反链操作比较复杂考试应该不会考，实现可以先做单链表的反链实现，然后树调用单反链的成员函数，这样不容易出错。北大习题指导上面好像也有反链实现的，不过没有划分出单链类，逻辑比较复杂看着比较吃力，你可以参考下～
--  作者：applestar
--  发布时间：12/24/2007 6:59:00 PM

--  
这类问题主要是采用逆转链法，主要用在内存空间管理，目的是节约空间浪费时间
对于二叉树，广义表的遍历都可以采用，因为他们本质差别不大，注意的是遍历完之后
还要把它逆转过来，清华大学以前的教材和北大以前的教材都有介绍
--  作者：chenminyi
--  发布时间：12/24/2007 10:37:00 PM

--  
顺便说一下数据结构的问题，现在计算机内存不再紧缺，因此一些比较复杂的数据结构用的很少，特别单存为了节省存储空间而增加操作复杂性与稳定性的数据结构。
      记得以前看国防科大翻译的一本数据结构上面的课后习题，也是要求用单link地域实现双链表前向迭代和后向迭代功能，那个更巧妙。基本思想是 (a异或b)异或a = a异或(a异或b) = b这个基本公式。对于非bool值，应用C语言中的按位异或运算符上式也成立(要不是那个题，我都忘了还有^这个运算符，呵呵) 因此，可以在指针域中保存LeftLink异或RightLink，即front异或(front异或rear) = rear，这样可以从头结点开始前向遍历链表也可以从尾结点开始后向遍历链表，遍历过程中保存front或rear，与其指针域做异或运算便可得到下个结点的地址。
      上面的例子仅供大家消遣，这种数据结构很不稳定，异或出来的指针可能指向某非法位置，没人敢在工程中用这样的数据结构，呵呵～记得看算法导论的时候，里面的树一概都是有指向父结点的指针域的，而且从不用堆栈来模拟递归。我前几天写的Ackermann函数的非递归堆栈实现比用递归函数的实现慢了至少有一倍，用的是标准库的stack，难道stack比程序栈还要慢吗？～
--  作者：chenminyi
--  发布时间：12/24/2007 11:02:00 PM

--  
以下是引用applestar在2007-12-24 18:59:00的发言：
主要用在内存空间管理，目的是节约空间浪费时间

这个好像浪费不了多少时间吧～每次指针右移或左移增加一个赋值操作，不影响时间复杂度大O估计。看操作系统的时候没见提过

--  作者：sunnylee
--  发布时间：12/24/2007 11:56:00 PM

--  
以下是引用chenminyi在2007-12-24 13:33:00的发言：
这个题以前好像讨论过，不用递归不用堆栈就只能用反链，反链只用一个link地域但可以实现双链表的功能。我以前上机验证过单链表反链的代码。基本思想就是这样的：
...<-front-<cur  rear->...
游标向右操作是temp = rear; rear = rear->link; temp->link = cur; front = cur; cur = temp;
游标向左操作是temp = cur; cur = front; front = front->link; temp->link = rear; rear = temp;
还要注意处理最左端和最右端的情况，即front或rear为NULL的情况，你说的flag = 0|1|2，我想应该就是用来标记该结点是front,cur还是rear。
树的反链操作比较复杂考试应该不会考，实现可以先做单链表的反链实现，然后树调用单反链的成员函数，这样不容易出错。北大习题指导上面好像也有反链实现的，不过没有划分出单链类，逻辑比较复杂看着比较吃力，你可以参考下～


链表的反链到能明白，北大DS指导书上看过，不过树的反链不太明白，也不知道
该怎样在后序中遍历应用。
--  作者：buddha
--  发布时间：12/25/2007 1:26:00 PM

--  
还有一道类似题目。
要求有父指针，左孩子指针，右孩子指针。遍历二叉树。
要求不能用递归和堆栈。
--  作者：sunnylee
--  发布时间：12/25/2007 1:33:00 PM

--  
以下是引用buddha在2007-12-25 13:26:00的发言：
还有一道类似题目。
要求有父指针，左孩子指针，右孩子指针。遍历二叉树。
要求不能用递归和堆栈。


如果有父指针的话就会容易很多，而且用两个FLAG就可以实现。
但只用三个FLAG真的好难啊。。
--  作者：chenminyi
--  发布时间：12/25/2007 9:30:00 PM

--  
以下是引用hanshumin在2007-12-24 11:19:00的发言：
是不是穿线二叉树，如果是的，应该不是很难，关键是如何找到遍历的第一个节点，以及其之后的后继节点。这一点好象很多课本上有算法。


北大增补题中有用穿线树做后序遍历的，也有找前序前驱后序后继的。今天刚做了这两个题目，比较复杂，我只做了前序前驱的，后序后继的应该与之类似，不过后序遍历我没用找后续结点的方法。
l = r = point
while(l->left!=NULL && l->ltag==0) l = l->left;       //找point最左子节点
while(r->right!=NULL && r->rtag==0) r = r->right; //找point最右子节点
l = l->left;     r = r->right;   //最左子节点和最右子节点中必有一个的线索指向point的父结点
if(l->right = point){            //最左子节点指向point的父结点，point必为父结点的右孩子
    q = l->left;                   //右子树根结点的前序前驱为左子树最右子节点
    while(q->right && q->right==0)
         q = q->right;
     return q;
}
if(r->left = point)              //最右子节点指向point的父结点，point必为父结点的左孩子
    return r;                      //左子树根节点的前序前驱为其父结点
--  作者：chenminyi
--  发布时间：12/25/2007 9:47:00 PM

--  
上面是找指定节点point的前序前驱，后序后继也是类似的。不过我做后序遍历不是用这个方法。不过思路是差不多的～总之用穿线树任意结点可以找到其父结点，找到父结点了就可以求后继结点。在后序遍历的算法中，只有右子树需要向上回溯找父结点，因此可简化上面的算法。
而且还不用flag = 0/1/2 只需要0/1即可
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 172.119ms