YTU 3022: 完全二叉树（1）

YTU 3022: 完全二叉树（1）

​

3022: 完全二叉树（1）

时间限制:  1 Sec   内存限制:  128 MB

提交:

26   解决:  7

题目描述

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

思想：根据二叉树以数组表示形式的定义，每一个节点的孩子节点所在位置是它本身位置的二倍与二倍加一，就这样。比如a[0]的位置是1，它的孩子节点是a[1*2-1]与a[1*2]   //减一是因为逻辑位序和物理位序差1然后利用递归的思想，便可以建立起整个二叉树的链状结构了！

算法部分：

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); //递归右孩子}

完整代码：

#include #include #include #include using namespace std;typedef char ElemType;#define SizeMax 205typedef 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。