带头结点的中序线索化

佚名 5年前 (2019-11-16) 算法 2131人围观抢沙发百度已收录

可能编译时会有些语法小错误（比如分号，->，等），很容易就自己纠正了哦，思路绝对是完全正确的，所以用的话就自己试着改改吧，直接复制粘贴，就正确，岂不是太没写代码体验了，自己改改才印象更加深刻的呢(^▽^)~~~~；

//带头结点的中序线索化
#include<iostream>
using namespace std;

typedef struct BiThrNode{
    char data;
    struct BiThrNode *lchild,*rchild;
    int LTag,RTag;
}BiThrNode,*BiThrTree;

BiThrNode *pre=new BiThrNode;

void CreateBiTree(BiThrTree &T){
    char ch;
    cin>>ch;
    if(ch=='#') T=NULL;
    else{
        T=newBiThrNode;
        T->data=ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

void InThreading(BiThrTree p){
    if(p){
        InThreading(p->lchild);
        if(!p->lchild){
            p->LTag=1;
            p->lchild=pre;
        }else{
            p->LTag=0;
        }

        if(!pre->rchild){
            pre->RTag=1;
            pre->rchild=p;
        }else{
            pre->RTag=0;
        }
        pre=p;
        InThreading(p->rchild);
    }
}

void InOrderThreading(BiThrTree &Thrt,BiThrTree T){
    Thrt=new BiThrNode;
    Thrt->LTag=0;
    Thrt->RTag=1;
    Thrt->rchild=Thrt;
    if(!T) Thrt->lchild=Thrt;
    else{
        Thrt->lchild=T;pre=Thrt;
        InThreading(T);
        pre->rchild=Thrt;
        pre->RTag=1;
        Thrt->rchild=pre;
    }
}

void main(){
    pre->RTag=1;
    pre->rchild=NULL;
    BiThrTree tree,Thrt;
    cout<<"please:\n";
    CreateBiTree(tree);
    InThreading(Thrt,tree);
    cout<<"finish：\n";
}