内存:128  时间:1

题目描述

一棵具有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

提示

 请使用C++编译并提交

代码如下

#include<iostream>
#include<malloc.h>
#include<queue>
#include<string.h>
#define Maxsize 205
using namespace std;
typedef char ElemType;
typedef struct Node 
{
	ElemType data;
	Node *lchild;
	Node *rchild;
} TBTree;
void solve(TBTree* & tree, char *c, int pos)
{
	 if(pos>(int)strlen(c)||c[pos-1]=='#')
	 {
	 	tree=NULL;
	 	return;
	 }
	 tree=(TBTree *)malloc(sizeof(Node));
     tree->data=c[pos-1];
     solve(tree->lchild,c,pos*2);
     solve(tree->rchild,c,pos*2+1);	
}
void Print(TBTree * tree)
{
	 if(tree==NULL) return ;
	 TBTree *q;
	 TBTree *qu[Maxsize];
	 int head,rear;
	 head=0;
	 rear=1;
	 qu[rear]=tree;
	 while(head<rear)
	 {
		cout<<qu[++head]->data;
		q=qu[head];
		if(q->lchild!=NULL) qu[++rear]=q->lchild;
		if(q->rchild!=NULL) qu[++rear]=q->rchild; 	 
     }
}                   
int main(void)
{
      char c[100];
	  TBTree *Tree;
	  gets(c);
	  solve(Tree,c,1);
	  Print(Tree);	
} 

代码来源于互联网,仅供参考!