完全二叉树（1）

完全二叉树（1）

时间： 1ms        内存：128M

描述：

一棵具有n个节点的完全二叉树以顺序方式存储在数组A中，设计一个算法构造该二叉树的链存储结构。

即编写一个函数，将二叉树数组存储形式转移到*Tree中。

  

其中二叉树的节点定义为

typedef struct Node

{

    ElemType data;

    Node* lchild;

    Node* rchild;

} TBNode;

 

编写一个函数

void solve(TBNode *&Tree,char *c,int pos);  完成相应操作。

// Tree为二叉树根节点，c为二叉树数组的形式表示，main()中传入的pos=1

输入：

输入只有一行，为二叉树的数组表示形式。

输出：

输出只有一行，为二叉树链存储结构的层序遍历.

示例输入：

ABCD#EF#G##H##I

示例输出：

ABCDEFGHI

提示：

参考答案（内存最优[0]）：

#include <iostream>  
#include <stdio.h>  
#include <string.h>  
#include <stdlib.h>  
using namespace std;  
typedef char ElemType;  
#define SizeMax 205  
typedef struct Node  
{  
    ElemType data;  
    Node* lchild;  
    Node* rchild;  
} TBNode;  
void solve(TBNode *&Tree,char *c,int pos)  
{  
    if(c[pos-1]=='#'||pos>(int)strlen(c))   //递归出口为该节点为NULL  
    {  
        Tree=NULL;  
        return;  
    }  
    Tree=(TBNode*)malloc(sizeof(Node));     //开辟空间  
    Tree->data=c[pos-1];  
    solve(Tree->lchild,c,pos*2);            //递归左孩子  
    solve(Tree->rchild,c,pos*2+1);          //递归右孩子  
}  
void Print(TBNode *Tree)  
{  
    TBNode *p;  
    TBNode *qu[SizeMax];  
    int front,rear;  
    front=rear=-1;  
    rear++;  
    qu[rear]=Tree;  
    if(Tree==NULL)return;  
    while(front!=rear)  
    {  
        front=(front+1%SizeMax);  
        p=qu[front];  
        printf("%c",p->data);  
        if(p->lchild!=NULL)  
        {  
            rear=(rear+1)%SizeMax;  
            qu[rear]=p->lchild;  
        }  
        if(p->rchild!=NULL)  
        {  
            rear=(rear+1)%SizeMax;  
            qu[rear]=p->rchild;  
        }  
    }  
}  
int main()  
{  
    char c[205];  
    TBNode *Tree;  
    gets(c);  
    solve(Tree,c,1);  
    Print(Tree);  
    return 0;  
}  

参考答案（时间最优[0]）：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
typedef char ElemType;
#define SizeMax 205
typedef struct Node
{
    ElemType data;
    Node* lchild;
    Node* rchild;
} TBNode;void solve(TBNode *&Tree,char *c,int pos)
{
    if(c[pos-1]=='#'||pos>(int)strlen(c))
    {
        Tree=NULL;
        return;
    }
    Tree=(TBNode*)malloc(sizeof(Node));
    Tree->data=c[pos-1];
    solve(Tree->lchild,c,pos*2);
    solve(Tree->rchild,c,pos*2+1);
}
void Print(TBNode *Tree)
{
    TBNode *p;
    TBNode *qu[SizeMax];
    int front,rear;
    front=rear=-1;
    rear++;
    qu[rear]=Tree;
    if(Tree==NULL)return;
    while(front!=rear)
    {
        front=(front+1%SizeMax);
        p=qu[front];
        printf("%c",p->data);
        if(p->lchild!=NULL)
        {
            rear=(rear+1)%SizeMax;
            qu[rear]=p->lchild;
        }
        if(p->rchild!=NULL)
        {
            rear=(rear+1)%SizeMax;
            qu[rear]=p->rchild;
        }
    }
}
int main()
{
    char c[205];
    TBNode *Tree;
    gets(c);
    solve(Tree,c,1);
    Print(Tree);
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。