[数据结构与算法]中序遍历线索二叉树

?//查找某个结点的后继

第一步，先用一个循环找到二叉树的第一个节点

第二步，访问第一个节点

第三步，调用next函数找到下一个节点，依次访问下一个节点。

//如果结点p的右标志为1,则表明该结点的右指针是线索；

//如果结点p的右标志为0，则表明该结点有右孩子，根据中序遍历的操作定义，它的后继结点应该是遍历其右子树时的第一个访问的结点，即右子树中的最左下的结点.
ThreadNode* next(ThreadNode *p)  //参数传入一个你想要查找的那个结点的地址,回该结点的后继结点
{
  node *q;  中序遍历是左根右
  if(p->rtag == 1)  //右标志为1，没有右孩子，下一个结点是被线索化的rchild结点，
  {
      q = p->rchild;   //q是一个静态变量或者一个属性变量,直接可以得到他的右孩子
  }

  else  
  {      
      q = p->rchild;       //说明有右孩子，先指向结点的右孩子。

    while(q->ltag==0) //根据二叉树中序遍历知,下一个结点是该结点的左子树递归找到最左下角的结点
    {                   
         q = q->lchild;  //当ltag=0说明有左孩子，因为已经线索化,lchild就代表该结点的左孩子，
     }
  }

  return q;
}
        
这里不使用递归，递归是因为不知道有没有左孩子，通过访问其扩展，返回才知道有没有左孩子，现在已经知道
有没有左孩子，直接通过while循环访问即可

//中序线索链表遍历算法

void inOrder()  //通过线索链表遍历,所以不用传入结点参数
{
    node *p;
    if(root == NULL)
    {
        return;   //判断是不是空树，如果是空树，就不用遍历
    }
    
    p = root;
    while(p->ltag==0)  //当ltag=0,说明有左孩子,则用循环查找中序遍历的第一个结点p
    {
        p = p->lchild;
    }
    visit(p->data);    //访问第一个元素，之后利用循环访问链表，不许根据二叉树形式访问
   


    //通过线索化后，所有的结点的右孩子都指向了下一个结点，只有最后一个结点的右孩子才为NULL;
    while(p->rchild !=NULL)  
    {
        p = next(p);   //next函数上面已经写了,就是用来返回下一个结点的
        visit(p->data);
    }





}