查找线索二叉树的前驱和后继_线索二叉树左右非空的节点前驱

作者：我家小花儿 | 2024-04-26 17:09:03

踩

线索二叉树左右非空的节点前驱

看书一直没想明白、、、二叉树即使有线索了，对于左右子树都非空的二叉树，从后继怎么找到的前驱啊，找不到啊。啊。啊。（中序的）

搜了个代码看看，果然清晰透彻，浑身酥爽。【自从上次看懂KMP算法时，体验到浑身颤抖的感觉后，就打算将数据结构继续学下去。

中序线索化算法：

[cpp]view plaincopy 
   
 //将二叉树按中序线索化算法  
 typedef enum   {Link,Thread} PointerTag;//枚举值分别为0,1  
 typedef struct node  
 {  
     DataType data;  
     PointerTag ltag,rtag;   //左右标志  
     struct node *lchild ,*rchild;  
 }BinThrNode;//线索二叉树节点类型  
 typedef BinThrNode *BinThrTree;  
 void InorderThreading(BinThrTree p)  
 {//将二叉树p中序线索化  
     if(p)//p非空时，当前访问结点是*p  
     {  
         InorderThreading(p->lchild);//左子树线索化  
         //建立正在访问节点的前驱结点之间的线索  
         t->ltag = (t->lchild)?Link:Thread;  
         t->rtag = (t->rchild)?Link:Thread;  
         if(pre)  
         {  
             if(pre->rtag==Thread)  
                 pre->rchild = p;  
             if(p->ltag==Thread)  
                 p->lchid = pre;  
         }  
         pre = p;  
         InorderThreading(t->rchild);//右子树线索化  
     }  
 }  

前驱和后继的查找

[cpp]view plaincopy 
   
 BinThrNode *InorderSuccessor(BinThrNode *p)  
 {//在中序线索树查找*p的后继  
     BinThrNode *q;  
     if(p->rtag==Thread)  
         return p->rchlid;//返回其所指的后继  
     else  
     {  
         q = p->rchild;//从*p的右孩子开始查找  
         while(q->ltag==Link)  
             q = q->lchild;//左子树为空，沿左链往下查找  
         return q;  
     }  
 }  
  BinThrNode *Inorderpre(BinThrNode *p)  
       {//在中序线索树中找结点*p的中序前趋，设p非空  
          BinThrNode *q；  
         if (p->ltag==Thread) //*p的左子树为空  
                return p->lchild； //返回左线索所指的中序前趋  
          else{  
                q=p->lchild； //从*p的左孩子开始查找  
                while (q->rtag==Link)  
                     q=q->rchild； //右子树为空时，沿右链往下查找  
                return q； //当q的右子树为空时，它就是最右下结点  
              } //end if  
       }  

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/492169

查找线索二叉树的前驱和后继_线索二叉树 左右非空的节点前驱

查找线索二叉树的前驱和后继_线索二叉树左右非空的节点前驱