完全二叉树（1）

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``

``````#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;
}  ``````

``````
#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;
}
``````