将树转换成数组

#include <stdio.h> #include <stdlib.h> #include <memory.h> struct treenode { int data; struct treenode *left,*right; int arrayorder; //转换为数组之后该元素为数组的下标 }; struct treeArray { int data; int lchild,rchild; }; struct treenode* createBiTree(struct treenode **p, int x); void traverse(struct treenode *p); int nodeNum(struct treenode* p); void initArray(struct treenode* p,struct treeArray* pArr); void transform(struct treenode* p,struct treeArray* pArr); int main() { int x; struct treenode *root = NULL; //建立二叉树链表 printf("input data is continum?(ctrl+z): \n"); while(scanf("%d",&x) != EOF) { createBiTree(&root,x); } //顺序输出二叉树表 traverse(root); printf("\n"); //动态分配跟二叉树节点个数一样的静态数组 int nodeLen = nodeNum(root); //给数组分配内存 struct treeArray* tArr = (struct treeArray*)malloc(sizeof(struct treeArray) * nodeLen); if (tArr == NULL) { printf("out of memory,press any key to quit...\n"); exit(0); } //用0初始化数组 for (int i = 0; i < nodeLen; ++i) { tArr[i].data = tArr[i].lchild = tArr[i].rchild = 0; } //将树放到数组中 initArray(root,tArr); //将root中的左右下标放到数组中的lchild rchild transform(root,tArr); //显示数组: printf("将二叉树转化为数组之后为:\n"); printf("下标 data lchild rchild\n"); for(int j=0;j<nodeLen;j++) { printf("%2d%8d%8d%8d\n",j,tArr[j].data,tArr[j].lchild,tArr[j].rchild); } free(tArr); tArr = NULL; return 0; } void transform(struct treenode* p,struct treeArray* pArr) { static int i = 0; if (p != NULL) { if(p->left != NULL) pArr[i].lchild = p->left->arrayorder; if(p->right != NULL) pArr[i].rchild = p->right->arrayorder; ++i; transform(p->left,pArr); transform(p->right,pArr); } } void initArray(struct treenode* p,struct treeArray* pArr) { static int num = 0; if (p != NULL) { pArr[num].data = p->data; p->arrayorder = num; ++num; initArray(p->left,pArr); initArray(p->right,pArr); } } //二叉树就是根部 有两根枝干的 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(x < (*p)->data) //小数据放在左边 { createBiTree(&(*p)->left,x); } else createBiTree(&(*p)->right,x); return *p; } void traverse(struct treenode *p) { if (p != NULL) { printf("%d ",p->data); traverse(p->left); //递归 traverse(p->right); } } int nodeNum(struct treenode* p) { static int num = 0; if (p != NULL) { ++num; nodeNum(p->left); nodeNum(p->right); } return num; }