数据结构—二叉链顺序存储结构

忘是亡心i 2022-08-22 15:23 135阅读 0赞

/*
    （1）设计一个算法，将二叉树的顺序存储结构转换成二叉链存储结构；
    （2）一棵具有n个节点的完全二叉树以顺序存储方式存储在数组中，构造该树的二叉链存储结构；
    （3）将一棵以二叉链方式存储的二叉树t按顺序方式存储到数组A中。
    */
    #include <iostream>
    #include <malloc.h>
    #define MaxSize 11   //注意MaxSize直接为二叉树顺序存储的个数
    typedef char ElemType;
    using namespace std;
    typedef struct node
    {
        ElemType data;   //数据元素
        struct node *lchild;  //指向左孩子节点
        struct node *rchild;  //指向右孩子节点
    } BTNode;
    
    typedef ElemType SqBTree[MaxSize];
    
    /*
    递归模型：
       f(a,i)=NULL      i>MaxSize
       f(a,i)=NULL      i对应节点为空
       f(a,i)=b(创建根节点b,其data值为a[i]);
            b->lchild=f(a,2*i);
            b->rchild=f(a,2*i+1);
    */
    BTNode *trans(SqBTree a,int i)
    {
        BTNode *b;
        if(i>MaxSize)
            return (NULL);
        if(a[i]=='#')      //当节点不存在时返回NULL
            return (NULL);
        b=(BTNode *)malloc(sizeof(BTNode));   //创建根节点
        b->data=a[i];
        b->lchild=trans(a,2*i);       //递归创建左子树
        b->rchild=trans(a,2*i+1);     //递归创建右子树
        return (b);
    }
    
    void trans2(BTNode *&b,char a[],int i)
    {
        if(i>MaxSize||a[i]=='#')
            b= NULL;
        else
        {
            b=(BTNode *)malloc(sizeof(BTNode));   //创建根节点
            b->data=a[i];
            trans2(b->lchild,a,2*i);       //递归创建左子树
            trans2(b->rchild,a,2*i+1);     //递归创建右子树
        }
    }
    
    void tran3(BTNode *b,SqBTree a,int i)
    {
        a[0]='#';
        if(b!=NULL)
        {
            a[i]=b->data;
            tran3(b->lchild,a,2*i);
            tran3(b->rchild,a,2*i+1);
        }
        else
            a[i]='#';
    }
    
    void DispBTNode(BTNode *b)  //输出二叉树
    {
        if(b!=NULL)
        {
            cout<<b->data;
            if(b->lchild!=NULL||b->rchild!=NULL)
            {
                cout<<"(";       //有孩子节点才输出
                DispBTNode(b->lchild);   //递归处理左子树
                if(b->rchild!=NULL)
                    cout<<",";          //有右孩子节点时才输出
                DispBTNode(b->rchild);   //递归处理右子树
                cout<<")";             //有孩子节点时才输出
            }
        }
    }
    
    int main()
    {
        BTNode *bt,*bt2;
        SqBTree a="#ABCD#EF#G",b;
        bt=trans(a,1);
        cout<<"构造二叉链存储结构：";
        DispBTNode(bt);
        cout<<endl;
        trans2(bt2,"#ABCD#EF#G",1);
        cout<<"构造二叉链存储结构：";
        DispBTNode(bt2);
        cout<<endl;
        tran3(bt,b,1);
        cout<<"构造顺序存储结构：";
        for(int i=0;i<MaxSize;i++)
            cout<<b[i];
        cout<<endl;
        return 0;
    }

运行结果：

![Center][]

[Center]: /images/20220722/2bc5b5f407724d42bef02dfb4ef47368.png