在线索二叉树中找前驱和后继

2022-06-13 382

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 在线索二叉树中找前驱和后继

一、线索二叉树找前驱和后继

（一）中序线索二叉树

1. 中序线索二叉树找中序后继

在这里插入图片描述

//找到以P为根的子树中，第一个被中序遍历的结点
ThreadNode *Firstnode(ThreadNode *p){
    //循环找到最左下结点（不一定是叶结点）
    while(p-> == 0) p=p->lchild;
    return p;
}
//在中序线索二叉树中找到结点p的后继结点
ThreadNode *Nextnode(ThreadNode *p){
    //右子树最左下结点
    if(p->rtag == 0) return Firstnode(p->rchild);
    else return p->rchild;//rtag==1直接返回后继线索
}

//对中序线索二叉树进行中序遍历（利用线索实现的非递归算法）
void Inorder(ThreadNode *T){
    for(ThreadNode *p = Firstnode(T);p!=NULL;p=Nextnode(p))
        visit(p);
}
123456789101112131415161718

空间复杂度：O(1)

2. 中序线索二叉树找中序前驱

在这里插入图片描述

//找到以P为根的子树中，最后一个被中序遍历的结点
ThreadNode *Lastnode(ThreadNode *p){
    //循环找到最右下结点（不一定是叶结点）
    while(p->rtag == 0) p = p->rchild;
    return p;
}
//在中序线索二叉树中找到结点p的前驱结点
ThreadNode *Prenode(ThreadNode *p){
    //左子树中最右下结点
    if(p->ltag == 0) return Lastnode(p -> lchild);
    else return p->lchild;//ltag==1直接返回前驱线索
}

//对中序线索二叉树进行逆向中序遍历
void RevInorder(ThreadNode *T){
    for(ThreadNode *p = LastNode(T); p!=NULL ; p=Prenode(p))
        visit(p);
}
123456789101112131415161718