数据结构—线索化二叉树（中序）

末蓝、 2022-08-22 15:26 287阅读 0赞

/*
    线索化二叉树。
    （1）中序线索化二叉树；
    （2）遍历线索化二叉树。
    */
    #include <iostream>
    #include <malloc.h>
    #define MaxSize 100
    typedef char ElemType;
    using namespace std;
    typedef struct node
    {
        ElemType data;
        int ltag,rtag;
        struct node *lchild;
        struct node *rchild;
    } TBTNode;
    
    /*
    对以*p为根节点的二叉树中序线索化。
    算法思路：
     在指针不为NULL时，先对*p节点的左子树线索化，若*p没有左孩子节点，则将其lchild指针线索化为指向其前驱节点*pre，将其ltag置为1，
     若*pre节点的rchild指针为NULL，将其rchild指针线索化为指向其后继节点*p，将其rtag置为1；最后对*p节点的右子树线索化。
    */
    TBTNode *pre;
    void Thread(TBTNode *&p)
    //先对*p进行前驱节点线索化，再对*pre进行后继节点线索化，而并不是*p的后继节点，方便。
    {
        if(p!=NULL)
        {
            Thread(p->lchild);     //左子树线索化
            if(p->lchild==NULL)    //*p左孩子不存在：进行前驱节点线索化
            {
                p->lchild=pre;
                p->ltag=1;
            }
            else
                p->ltag=0;
            if(pre->rchild==NULL)   //*pre右孩子不存在，进行后继节点线索化
            {
                pre->rchild=p;
                pre->rtag=1;
            }
            else
                pre->rtag=0;
            pre=p;
            Thread(p->rchild);     //右子树线索化
        }
    }
    
    /*
    将以二叉链存储的二叉树b进行中序线索化，并返回线索化后头节点指针root。
    */
    TBTNode *CreaThread(TBTNode *b)   //中序线索化二叉树
    {
        TBTNode *root;
        root=(TBTNode *)malloc(sizeof(TBTNode));
        root->ltag=0;
        root->rtag=1;             //建立头节点
        root->rchild=b;           //建立头节点与二叉树的联系
        if(b==NULL)
            root->lchild=root;    //空二叉树
        else
        {
            root->lchild=b;
            pre=root;
            Thread(b);            //中序遍历线索化二叉树
            //最后处理，加入指向头节点的线索
            pre->rchild=root;
            pre->rtag=1;
            root->rchild=pre;      //头节点右线索化
        }
        return root;
    }
    
    void CreateTBTNode(TBTNode * &b,char *str)
    {
        TBTNode *St[MaxSize],*p=NULL;
        int top=-1,k,j=0;
        char ch;
        b=NULL;             //建立的二叉树初始时为空
        ch=str[j];
        while (ch!='\0')    //str未扫描完时循环
        {
            switch(ch)
            {
            case '(':
                top++;
                St[top]=p;
                k=1;
                break;      //为左结点
            case ')':
                top--;
                break;
            case ',':
                k=2;
                break;                          //为右结点
            default:
                p=(TBTNode *)malloc(sizeof(TBTNode));
                p->data=ch;
                p->lchild=p->rchild=NULL;
                if (b==NULL)                    //*p为二叉树的根结点
                    b=p;
                else                            //已建立二叉树根结点
                {
                    switch(k)
                    {
                    case 1:
                        St[top]->lchild=p;
                        break;
                    case 2:
                        St[top]->rchild=p;
                        break;
                    }
                }
            }
            j++;
            ch=str[j];
        }
    }
    
    void DispTBTNode(TBTNode *b)  //输出二叉树
    {
        if(b!=NULL)
        {
            cout<<b->data;
            if(b->lchild!=NULL||b->rchild!=NULL)
            {
                cout<<"(";       //有孩子节点才输出
                DispTBTNode(b->lchild);   //递归处理左子树
                if(b->rchild!=NULL)
                    cout<<",";          //有右孩子节点时才输出
                DispTBTNode(b->rchild);   //递归处理右子树
                cout<<")";             //有孩子节点时才输出
            }
        }
    }
    
    /*
    遍历线索化二叉树：
      算法思想：
         遍历某种次序的线索二叉树，从该次序的开始节点出发；反复找到该节点在该次序下的后继节点，直到终端节点，
         其rchild指针被线索化为指向头节点。
      （在中序二叉树中，开始节点就是根节点的最左下节点）
    */
    void ThInOrder(TBTNode *tb)
    {
        TBTNode *p=tb->lchild;      //指向根结点
        while (p!=tb)
        {
            while (p->ltag==0)     //找开始节点
                p=p->lchild;
            cout<<p->data<<" ";   //访问开始节点
            while (p->rtag==1 && p->rchild!=tb)
            {
                p=p->rchild;
                cout<<p->data<<" ";
            }
            p=p->rchild;
        }
    }
    
    int main()
    {
        TBTNode *b,*tb;
        CreateTBTNode(b,"A(B(D(,G)),C(E,F))");
        cout<<" 二叉树:";
        DispTBTNode(b);
        cout<<endl;
        tb=CreaThread(b);
        cout<<" 线索中序序列:";
        ThInOrder(tb);
        cout<<endl;
        return 0;
    }

运行结果：

![Center][]

[Center]: /images/20220722/28632b96ce6148e9aad77c78009a875c.png