线索二叉树的c++实现代码

Code_mzh

#include <iostream>
using namespace std;
typedef char ElemType;
typedef enum{Link,Thread} PointerTag;
//Link(0)，Thread(1)
// 0表示存储左右孩子的指针，1表示存放前驱和后继

typedef struct BNode{
    ElemType data;
    struct BNode *lchild,*rchild;
    PointerTag rtag,ltag;//记载线索的两个位置
}BNode,*BTree;
//全局变量始终指向刚刚访问的结点

BTree pre;
//创建树，并且初始化zhizhen
void CreatBiTree(BTree *T){
    char ch;
    cin>>ch;
    if( '#' != ch)
    {
        *T=new BNode;
        (*T)->data=ch;
        (*T)->ltag=Link;
        (*T)->rtag=Link;
        CreatBiTree(&(*T)->lchild);
        CreatBiTree(&(*T)->rchild);
    }
}
//中序遍历
void InOrder(BTree T) {
    if (T)
    {
        InOrder(T->lchild);
        if (!T->lchild) //如果左孩子不存在，将左孩子线索化，指向前趋结点
        {
            T->ltag = Thread;
            T->lchild = pre;
        }
        if(!pre->rchild)//如果上一个结点的右孩子不存在，就让他指向后继结点
        {
            pre->rtag=Thread;
            pre->rchild=T;
        }
        pre=T;
        InOrder(T->rchild);
    }
}
//创建头结点，并且完成左右指针的初始化
void InOrderPre(BTree *p,BTree T){
    *p=new BNode;
    (*p)->ltag=Link;
    (*p)->rtag=Thread;//因为最后这个要指向中序遍历最后一个结点，所以先把他线索化
    //(*p)->lchild=T;
    (*p)->rchild=*p;//首先让他的右边的指针指向自己
    if(!T)
    {
        (*p)->lchild=*p;//如果是空树，左孩子也指向自己了
    }else{
        (*p)->lchild=T;
        pre=*p;//将pre变成了头指针
        InOrder(T);
        //下面是将头结点和中序遍历最后一个结点构成循环
        pre->rchild=*p;
        pre->rtag=Thread;
        (*p)->rchild=pre;
    }
}
//迭代进行中序遍历，并且打印出结果
void InOrderTraverse(BTree T){
    BTree p;
    p=T->lchild;
    while(p != T)
    {
        while(p->ltag == Link)
        {
            p=p->lchild;
        }
        cout<<p->data<<"\t";
        while(p->rtag == Thread && p->rchild != T)
        {
            p=p->rchild;
            cout<<p->data<<"\t";
        }
        p=p->rchild;
    }
}
int main(){
    BTree T;
    BTree p;
    CreatBiTree(&T);
    InOrderPre(&p,T);
    cout<<"输出中序遍历："<<endl;
    InOrderTraverse(p);
    //InOrder( T);
    return 0;
}

本人亲自调试过了，还加了注释