首页 > 其他分享 >13、线索二叉树

13、线索二叉树

时间:2024-09-29 08:51:41浏览次数:6  
标签:13 return cur 节点 二叉树 BinTreeNode NULL root 线索

1、线索化二叉树的定义和初始化

#include<stdio.h>
#include<malloc.h>
#include<assert.h>

#define ElemType char

typedef struct BinTreeNode{
    ElemType data;
    struct BinTreeNode* leftChild;
    struct BinTreeNode* rightChild;
    int lTage;//左标记[0:左孩子节点 1:前驱节点] 
    int rTage;//右标记[0:右孩子节点 1:后继节点] 
}BinTreeNode;

typedef struct BinTree{
    BinTreeNode* root;
    ElemType refvalue;//停止标志 
}BinTree; 


//初始化
void initBinTree(BinTree* bt,ElemType ref){
    bt->root = NULL;
    bt->refvalue = ref;
} 

2、二叉树的创建和线索化

//创建节点
BinTreeNode* malloc_node(ElemType data){
    BinTreeNode* t = (BinTreeNode*) malloc(sizeof(BinTreeNode));
    assert(t != NULL);
    t->data = data;
    t->leftChild = NULL;
    t->rightChild = NULL;
    t->lTage = t->rTage = 0;
    return t;
} 

//创建二叉树
void createBinTree(BinTree* bt,BinTreeNode** node,char** str){
    if(**str == bt->refvalue){
        (*node) = NULL;
        ++(*str);
    } else {
        (*node) = malloc_node(**str);
        ++(*str);
        createBinTree(bt,&(*node)->leftChild,str);
        createBinTree(bt,&(*node)->rightChild,str);
    }
} 

//二叉树中序线索化
void BinTreeNodeInThread(BinTreeNode** t,BinTreeNode** pre){
    if(*t == NULL)
        return;
    else {
        //遍历当前节点的所有左子树
        BinTreeNodeInThread(&(*t)->leftChild,pre);
        
        //运行到此处说明该节点 的左子树已全部遍历完
        //处理该节点 将左节点进行线索化
        if((*t)->leftChild == NULL){
            (*t)->lTage = 1;
            (*t)->leftChild = *pre;
        }
        //处理该节点的前驱节点,将该节点的前驱节点线索化[前驱节点的后继指向t] 
        if((*pre) != NULL && (*pre)->rightChild == NULL){
            (*pre)->rTage = 1;
            (*pre)->rightChild = *t;
        }
        //更新前驱节点
        *pre = *t;

        //遍历当前节点的所有右子树
        BinTreeNodeInThread(&(*t)->rightChild,pre);
    }
} 

void BinTreeInThread(BinTree* bt){
    //记录前驱节点 
    BinTreeNode* pre = NULL;
    BinTreeNodeInThread(&bt->root,&pre); 
    //处理最后一个节点
    if(pre != NULL){
        pre->rightChild = NULL;
        pre->rTage = 1; 
    }

} 

3、线索化二叉树的其他方法

//求中序遍历第一个节点
BinTreeNode* First(BinTreeNode* node){
    
    BinTreeNode* p = node;
    //遍历左孩子,当遍历到左标记为1说明是第一个节点 
    //由于已经线索化了,所有节点的左右孩子都不为NULL 
    while(p != NULL && p->lTage == 0)
        p = p->leftChild;
    return p;
} 

//求中序遍历最后一个节点
BinTreeNode* Last(BinTreeNode* node){
        
    BinTreeNode* p = node;
    while(p != NULL && p->rTage == 0){
        p = p->rightChild;
    }
        
    return p;
} 

//求cur节点的后继
BinTreeNode* Next(BinTreeNode* root,BinTreeNode* cur){
    if(root == NULL || cur == NULL)
        return NULL;
    if(cur->rTage == 1)
        return cur->rightChild;
    //由于是中序遍历,说明cur左子树的节点都遍历完了,
    //所以cur的后继节点为它的右子树遍历的第一个节点
    return First(cur->rightChild); 
} 

//求cur节点的前驱
BinTreeNode* Prio(BinTreeNode* root,BinTreeNode* cur){
    if(root == NULL || cur == NULL)
        return NULL;
    if(cur->lTage == 1)
        return cur->leftChild;
    //由于是中序遍历,cur的前驱为它的左子树遍历的最后一个节点 
    return Last(cur->leftChild); 
} 

//中序遍历[由于二叉树已经线索化,不能再用之前的遍历方法,
//线索化将二叉树 由非线性变为线性关系] 
void InOrder(BinTreeNode* root){
    BinTreeNode* p = root;
    for(p = First(p);p != NULL;p = Next(root,p)){
        printf("%c ",p->data);
    }
    printf("\n");
} 

BinTreeNode* search(BinTreeNode* root,ElemType key){
    if(root == NULL)
        return NULL;
    if(root->data == key)
        return root;
    BinTreeNode* p = root;
    for(p = First(p);p != NULL;p = Next(root,p)){
        if(p->data == key)
            return p;
    }    
    return NULL;
}

BinTreeNode* Parent(BinTreeNode* root, BinTreeNode* cur){
     if (root == NULL || cur == NULL || root == cur) {
        return NULL;
    }
    
    BinTreeNode* p;
    //cur存在线索 注意:if中一定要判断p是否为空 
    if(cur->lTage == 1){
        p = cur->leftChild;
        //由于是中序遍历,cur的左孩子为前驱节点,既然是前驱说明cur一定在指向的右子树这边 
        if(p != NULL && p->rightChild == cur)
            return p;
    }
    if(cur->rTage == 1){
        p = cur->rightChild;
        if(p != NULL  && p->leftChild == cur)
            return p;
    }
     
    //cur不存在线索 ,说明cur存在左子树,那么左子树在cur前面
    //找到cur左子树要显示的第一个节点,该节点一定没有左子树
    //故该节点的左孩子节点会指向它的前驱,这个前驱有可能就是cur的父节点 
    p = First(cur->leftChild);
    p = p->leftChild;
    if(p != NULL && p->rightChild == cur)
        return p;
    
    //如果上诉都没找到,那就找cur节点的右孩子最后中序遍历的最后一个节点
    //这个节点的后继就是cur的父节点,因为这个节点在cur右边,说明cur已经访问了
    //cur的中序遍历最后一个右节点也访问,根据左根右说明下一个就是cur的父节点
    p = Last(cur->leftChild);
    if (p != NULL && p->rightChild == cur) {
        return p;
    }
    return NULL; 
} 
int main(){
    BinTree myTree;
    initBinTree(&myTree,'#');
    char* str = "ABC##DE##F##G#H##";
    createBinTree(&myTree,&myTree.root,&str);
    BinTreeInThread(&myTree);
//    BinTreeNode* node = Last(myTree.root);
//    printf("%c",node->data);
    InOrder(myTree.root);
    BinTreeNode* p = search(myTree.root,'C');
//    BinTreeNode* next = Next(myTree.root,p);
    BinTreeNode* parent = Parent(myTree.root,p);
    printf("%c",parent->data);
    
    return 0;
}

 

标签:13,return,cur,节点,二叉树,BinTreeNode,NULL,root,线索
From: https://www.cnblogs.com/xpp3/p/18438804

相关文章

  • 2024-2025-1 20241328《计算机基础与程序设计》第壹周学习总结
    2024-2025-120241328《计算机基础与程序设计》第壹周学习总结作业信息计算机基础与程序设计2024-2025-1-计算机基础与程序设计作业要求2024-2025-1计算机基础与程序设计第一周作业作业目标1、参考教程安装Linux系统;2、快速浏览一遍教材计算机科学概论(第七版),课本......
  • 2024-2025-1 20241310 《计算机基础与程序设计》第一周学习总结
    2024-2025-120241300《计算机基础与程序设计》第一周学习总结作业信息这个作业属于哪个课程2024-2025-1-计算机基础与程序设计这个作业要求在哪里2024-2025-1计算机基础与程序设计第一周作业这个作业的目标1.基于VirtualBox虚拟机安装Ubuntu图文教程安装Linux系......
  • 20241308《计算机基础与程序设计》第一周学习总结
    班级:https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP作业要求:https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP/homework/13276作业目标:快速浏览教材作业正文:第一章1.我们目前使用的第四代计算机是否可以继续改进,功能更加强大?第二章1.为什么计算机中的每个......
  • 2024-2025-1 学号20241315《计算机基础与程序设计》第一周学习总结
    作业信息这个作业属于哪个课程2024-2025-1-计算机基础与程序设计)这个作业要求在哪里2024-2025-1计算机基础与程序设计第一周作业)这个作业的目标快速浏览一遍教材计算机科学概论(第七版),课本每章提出至少一个自己不懂的或最想解决的问题并在期末回答这些问题--......
  • 2024-2025 20241312 《计算机基础与程序设计》第一周学习总结
    作业信息|这个作业属于哪个课程|2024-2025-1-计算机基础与程序设计)|||这个作业要求在哪里|2024-2025-1计算机基础与程序设计第一周作业)|----||这个作业的目标|快速浏览一遍教材计算机科学概论(第七版),课本每章提出至少一个自己不懂的或最想解......
  • 13安卓手机端自动化框架常用的辅助命令
    一.adb命令1.查询已连接的设备C:\Users\Administrator>adbdevicesListofdevicesattached127.0.0.1:21503device2.连接设备adbconnect127.0.0.1:215033.登录设备shellC:\Users\Administrator>adbshellMI9:/#4.查询安装的软件包MI9:/#pmlistpackage......
  • 2024-2025-1 学号20241315《计算机基础与程序设计》第一周学习总结
    作业信息|这个作业属于哪个课程|2024-2025-1-计算机基础与程序设计)|||这个作业要求在哪里|2024-2025-1计算机基础与程序设计第一周作业)|----||这个作业的目标|快速浏览一遍教材计算机科学概论(第七版),课本每章提出至少一个自己不懂的或最想解......
  • 树莓派pico rp2040 使用rust 在ssd1306上显示中文信息
    在rp2040上用DHT22+ssd1306显示温度信息, 用embedded-graphics库和ssd1306库来实现。但实现的效果不是很理想,无法在ssd1306屏幕上显示中文。 为了解决这个问题,在github和crates.io上面找了几天。解决方法还是找到了,利用 u8g2-font这个库实现。。。 实现的办法如下:Car......
  • 2024-2025-1 20241316 《计算机基础与程序设计》第一周学习总结
    2024-2025-120241316《计算机基础与程序设计》第一周学习总结作业信息这个作业属于哪个课程2024-2025-1-计算机基础与程序设计这个作业要求在哪里2024-2025-1计算机基础与程序设计第一周作业这个作业的目标<浏览教材并提出问题>作业正文https://www.cnblog......
  • CF EDU 139 略解
    E观察到\(0\&(1,2,3)=0\),除此之外只剩下\((1\&2=0)\)然后我也不知道有什么用了。这个暴力应该是非常好写的,直接统计\(0/1/2/3\)的个数即可。不对啊,感觉这个暴力怎么写出来还需要链表呢。。。不重要,但是我总感觉这个拆分之后的序列个数应该不会很大(?草了,\(n\)个\(0\)......