数据结构-线索二叉树

定义

typedef struct BiThrNode
{
  TelemType data;
  struct BitThrNode *lchild,*rchild;
  int  lRag,rtag;
}BiThrNode,*BiThrTree;

• 以上述结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树就是线索二叉树

• 结点前驱： 遍历左子树时最后访问的结点。
• 结点后继： 遍历右子树时访问的第一个结点。
  将结点为p的子树中序线索化

BiThrTree pre;
void InThreading(BiThrTree p) {
    if (p) {
        InThreading(p->lchild);  //讲左子树进行线索化
        {
            if (!p->lchild) {  //如果左子树为空
                p->lRag = 1;   //p加上左线索
                p->lchild = pre;//p的左孩子的指针指向前驱
            } else {
                p->lRag = 0;   //p的左子树不为空 
            }
            if (!pre->rchild) {  //pre 结点加右线索
                pre->rtag = 1;   
                pre->rchild = p;     //pre 有孩子指向后继
            } else {
                p->rtag = 0;
            }
            pre = p;   //保持pre指向p的前驱，反之后继
            InThreading(p->rchild); //讲右子树进行线索化
        }
    }
}