线索二叉树（中序创建）

╰+哭是因爲堅強的太久メ 2022-04-06 05:36 153阅读 0赞

#include"stdio.h"
    #include"string.h"
    //这里表示一个结点
    typedef struct NODE{
        char node;
        struct NODE *nextleft;
        struct NODE *nextright;
        int ltop;
        int rtop;
    }BiTNode,*BiTree;
    
    //用前序遍历创建一个树
    CreatBiTree(BiTree *T){
       char c;
       scanf("%c",&c);
       if(c==' ')
          *T=NULL;
       else{
        *T=(BiTNode *)malloc(sizeof(BiTNode));
        (*T)->node=c;
        (*T)->ltop=1;
        (*T)->rtop=1;
        CreatBiTree(&(*T)->nextleft);
        CreatBiTree(&(*T)->nextright);
       }
    }
    //前置结点 一开始指向根结点
    BiTNode *pre;
    //利用中序列表遍历并创建线索树
    InOrderTraverse(BiTNode *T){
         if(T!=NULL){
            //向左边的子树递归
             InOrderTraverse(T->nextleft);
           //上面一个递归结束之时，应是已到达了最左边的子树，且pre为最左边的子树的前置结点
    
             if(T->nextleft==NULL){
                T->ltop=0;
                T->nextleft=pre;//因为T->nextleft为NULL。所以将T->nextleft指向前置
    
             }
             //然后前置结点的后置应该为T。所以判断一下前置结点的右结点是否为NULL。看能否指向后置，还是已经指向了右子树
             if(pre->nextright==NULL){
                pre->rtop=0;
                pre->nextright=T;
             }
             //将前置的结点更新
             pre=T;
             InOrderTraverse(T->nextright);
         }
        }
    visit(char node){
         printf("%c",node);
        }
    //中序遍历二叉树 非递归
    InOrderTraversecheck(BiTNode *T){
        BiTNode *p;
        p=T->nextleft;
        while(p!=T){
            //利用循环，使p->nextleft为前置，不为子树。这样会使之指向最左边的子树
            while(p->ltop==1){
                p=p->nextleft;
            }
           //访问最左边的子树
            visit(p->node);
            //如果最左边的子树没有右子树。并且p->nextright不指向头指针。则使p回到上一层，即指向p的后置结点
            while(p->rtop==0&&p->nextright!=T){
                p=p->nextright;
                //访问此结点
                visit(p->node);
            }
            //并使之更新。指向的他的右边结点（这个更新未区分是子树还是后置）
            p=p->nextright;
        }
        }
    //这个函数的意义是创建一个头指针指向根结点
    InOrderThreading(BiTree *p,BiTree T){
        (*p)=(BiTree)malloc(sizeof(BiTNode));
        (*p)->nextright=(*p);
        (*p)->rtop=0;
        (*p)->ltop=1;
        if(T==NULL){
            (*p)->nextleft=(*p);
            (*p)->ltop=0;
        }
        else{
            (*p)->nextleft=T;
             pre=(*p);
             InOrderTraverse(T);
             pre->rtop=0;
             pre->nextright=(*p);
             (*p)->nextright=pre;
        }
       }
    //访问到此结点，现在对此结点进行操作
    visit1(BiTNode *T,int level){
        printf("%c是二叉树中的第%d层数据\n",T->node,level);
    }
    //中序遍历一颗二叉树
    PerOrderTraverse(BiTNode *T,int level){
        if(T!=NULL){
    
             PerOrderTraverse(T->nextleft,level+1);
             visit1(T,level);
             PerOrderTraverse(T->nextright,level+1);
        }
    }
    int main()
    {  int level=1;
        BiTree T,p;
        CreatBiTree(&T);
        printf("这里是用普通的递归遍历二叉树：\n");
        PerOrderTraverse(T,level);
        InOrderThreading(&p,T);
        printf("这里是用循环遍历二叉树：\n");
        InOrderTraversecheck(p);
        printf("\n");
    
    }