C语言 将二叉树转化为静态数组.doc

/C语言，将动态二叉树转化为静态数组#include#include/建立二叉树struct treenode *createBiTree(struct treenode *p,int x);/显示二叉树void traverse(struct treenode *p);/获取二叉树总的节点数并返回int nodeNum(struct treenode *p);/初始化数组的data数据，并使二叉树里面的arrayorder数据与数组下标一致void initArray(struct treenode *p);/将二叉树转化为数组void transform(struct treenode *p);struct treenodeint data;struct treenode *left,*right;int arrayorder;/转化为数组之后该节点在数组里的元素下标;struct treenode *createBiTree(struct treenode *p,int x)if(*p=NULL)*p=(struct treenode *)malloc(sizeof(struct treenode);if (*p=NULL) printf(out of memory,press any key to quit.n);exit(0); (*p)-data=x;(*p)-left=(*p)-right=NULL;(*p)-arrayorder=0;else if(xdata)createBiTree(&(*p)-left,x);elsecreateBiTree(&(*p)-right,x);return (*p);static int length=0;int nodeNum(struct treenode *p)if(p!=NULL)length+;nodeNum(p-left);nodeNum(p-right);return length;void traverse(struct treenode *p)if(p!=NULL)printf(%d ,p-data);traverse(p-left);traverse(p-right);struct treeArrayint data;int lchild,rchild;static struct treeArray *a=NULL;/转化之后的数组static int num=0;void initArray(struct treenode *p)if(p!=NULL)anum.data=p-data;p-arrayorder=num;num+;initArray(p-left);initArray(p-right);static int i=0;void transform(struct treenode *p)if(p!=NULL)if(p-left!=NULL)ai.lchild=p-left-arrayorder;if(p-right!=NULL)ai.rchild=p-right-arrayorder;i+;transform(p-left);transform(p-right);void main(void)int x;struct treenode *root=NULL;/建立二叉树链表printf(输入数据以ctrl+z结束:n);while(scanf(%d,&x)!=EOF)createBiTree(&root,x);printf(先序输出二叉树:);traverse(root);/输出二叉链表printf(n);/动态分配跟二叉树节点个数一样的静态数组length=nodeNum(root);a=(struct treeArray *)malloc(sizeof(struct treeArray)*length); if (a=NULL) printf(out of memory,press any key to quit.n); exit(0); /用0初始化数组for(int i=0;ilength;i+)ai.data=ai.lchild=ai.rchild=0;initArray(root);/将动态二叉树链表转化为静态数组transform(root);/显示数组:printf(将二叉树转化为数组之后为:n);printf(下标 data lc