中序线索二叉树问题

Question

中序二叉线索树的建立

    typedef enum { Link, Thread } PointerTag;           
    //Link==0,表示指向左右孩子指针
2.  //Thread==1,表示指向前驱或后继的线索

      void InThreading(BiThrTree B,BiThrTree *pre) {
  if(!B) return;

  InThreading(B->lchild,pre);   
//--------------------中间为修改空指针代码---------------------

  if(!B->lchild){                   //没有左孩子 
    B->LTag = Thread;               //修改标志域为前驱线索
    B->lchild = *pre;               //左孩子指向前驱结点
  }

  if(!(*pre)->rchild && pre!=NULL){              //没有右孩子
    (*pre)->RTag = Thread;          //修改标志域为后继线索
    (*pre)->rchild = B;             //前驱右孩子指向当前结点
  }

  *pre = B;                         //保持pre指向p的前驱
//---------------------------------------------------------
  InThreading(B->rchild,pre);
}

2
知道如何运用，但是不明白它的原理有几个疑问？
1

  if(!B->lchild){                   //没有左孩子 
    B->LTag = Thread;               //修改标志域为前驱线索
    B->lchild = *pre;               //左孩子指向前驱结点
  }

  if(!(*pre)->rchild && pre!=NULL){              //没有右孩子
    (*pre)->RTag = Thread;          //修改标志域为后继线索
    (*pre)->rchild = B;             //前驱右孩子指向当前结点

为什么在满足以上条件时就能判断前驱和后继 ，这与它的遍历的顺序有关吗 ，它是什么原理呢？
2 在定义中满足所有的空左指针指向前驱，所有的空的右指针指向后继的它为什么满足，可以进行改变吗？
3 左右孩子和前驱后继的关系是左右孩子是在二叉树中结点的关系，前驱后继是遍历的先后关系这样理解正确吗？
希望解释一下

Answer 1

1.为什么在满足以上条件时就能判断前驱和后继 ，这与它的遍历的顺序有关吗 ，它是什么原理呢？

你要先去看看线索二叉树的定义。

2.在定义中满足所有的空左指针指向前驱，所有的空的右指针指向后继的它为什么满足，可以进行改变吗？

我不知道你说的改变是什么，是空的左右指针指向？还是上面的代码？前者肯定是不行，因为定义如此，后者主要看每个人的实现，只要结果相同，过程不要太差就行。

3.左右孩子和前驱后继的关系是左右孩子是在二叉树中结点的关系，前驱后继是遍历的先后关系这样理解正确吗？

同一。

建议：

先看看维基的解释 ：https://zh.wikipedia.org/wiki...，再看看这篇文章：https://ethsonliu.com/2018/04...

Answer 2

你自己画一棵最简单的3层的树，手工递归遍历一下就能理解了。前驱和后继不是判断出来的，而是利用空指针来存储线索，构建双向链表的一种方法。你可以按照先序、中序、后序遍历，都能完成遍历，只不过每个节点的前驱和后继不一样而已。截图的代码是按照左中右中序遍历的，你可以按照右中左遍历，那么前驱和后继就刚好反过来。