线索二叉树

线索二叉树的定义 n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为"线索"）。
为了区分这个指针是指向前驱（或后继）还是指向孩子节点的，我们需要加上标志 lTag，rTag 来区分
这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(ThreadedBinaryTree)。
根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

因为线索二叉树保存了每个节点的前去后继信心，对于需要频繁查询树中节点的前驱，后继的情况，线索二叉树是个不错的选择

Code
[cpp]
#include<stdio.h>
#include<malloc.h>

typedef struct ThreadBiTreeNode
{
    char data;
    struct ThreadBiTreeNode *lChild;
    struct ThreadBiTreeNode *rChild;
    int lTag,rTag;
}BiTNode,*BiTree;

void CreateBTree(BiTree &biTree){
    char data;
    data = getchar();
    if(data=='0'){
        biTree = NULL;
    }
    else {
        biTree = (BiTree)malloc(sizeof(BiTNode));
        biTree->data = data;
        CreateBTree(biTree->lChild);
        CreateBTree(biTree->rChild);
    }
}

void InOrder(BiTree biTree){
    if(biTree != NULL){
        InOrder(biTree->lChild);
        printf("%c ",biTree->data);
        InOrder(biTree->rChild);
    }return ;
}

void InThreading(BiTree & p,BiTree & pre)
{
    if(p){
        InThreading(p->lChild,pre);

        if(!p->lChild){ //左孩子空，左孩子指针指向前驱
            p->lTag=1;
            p->lChild=pre;
        }
        else p->lTag=0;

        if(pre && !pre->rChild){ //前驱的右孩子空，前驱的右孩子指针指向后继
            pre->rTag=1;
            pre->rChild=p;
        }

        pre = p;
        pre->rTag = 0;

        InThreading(p->rChild,pre);
    }
}

BiTree InOrderThreading(BiTree biTree)
{
    BiTree threadTree = new BiTNode;
    //新加的节点（头节点），树中没有这个点
    //中序线索化出的链表的第一个节点的前驱（左孩子指针）指向这个头节点，
    //同时链表最后一个节点的后继（右孩子指针）也指向这个头结点，
    //而这个头结点的左孩子指针指向二叉树的根节点，右孩子指针指向中序线索化链表的最后一个节点
    //类似双向链表

    threadTree->lTag = 0;    //没有左孩子
    threadTree->rTag = 1;    //有右孩子
    threadTree->rChild = threadTree; //右指针回指

    if(!biTree){//空树左指针回指
        threadTree->lChild = threadTree;
    }
    else {
        threadTree->lChild = biTree;
        BiTree pre = threadTree;
        InThreading(biTree,pre);//中序线索化

        pre->rChild = threadTree;
        pre->rTag = 1;
        threadTree->rChild = pre;
    }
    return threadTree;
}

void InOrderTraverse_Thr(BiTree biTree)//中序遍历线索二杈树的非递归算法, biTree 指向头结点
{
    BiTree p = biTree->lChild; //p指向根结点
    while (p != biTree) //空树或遍历结束时，p == biTree
    {
        //从根开始寻找第一个结点，中根序列第一个节点是没有左孩子的，也就是lTag = 0
        //这点是区分中序线索化的标志，同样的，其它的线索化也都根据相应的特点来做
        while (p->lTag == 0)
        {
            p = p->lChild;
        }
        printf("%c ",p->data);

        while (p->rTag == 1 && p->rChild != biTree)//访问后继结点
        {
            p = p->rChild;
            printf("%c ",p->data);
        }
        p = p->rChild;
    }
}

BiTree NewBTree(char x)//构造一个数据域为x的新结点
{
    BiTree s = new BiTNode;
    s->data = x;
    s->lChild = s->rChild = NULL;
    s->lTag = s->rTag = 0;
    return s;
}

void Insert(BiTree & b, BiTree s)//在二杈排序树中插入新结点s
{
    if (b == NULL)
        b = s;
    //else if(b->data == s->data)//不做任何插入操作
    // return;
    else if(b->data > s->data)//把s所指结点插入到左子树中
        Insert(b->lChild, s);
    else &

补充：软件开发 , C++ ,