计算机科学论坛--[求助]一道DS程序设计题

贴子主题： [求助]一道DS程序设计题

本主题类别:

以下是引用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;                      //左子树根节点的前序前驱为其父结点


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	78.125ms