贵阳建立网站,东莞做网站 动点官网,网页设计怎么分析网站啊,东坑镇网站建设公司数据结构 ——二叉树转广义表
1、树转广义表 如下一棵树#xff0c;转换为广义表 root(c(a()(b()()))(e(d()())(f()(j(h()())())))) (根#xff08;左子树#xff09;#xff08;右子树#xff09;)
代码实现
#includestdio.h
#includestdlib.h//保存…数据结构 ——二叉树转广义表
1、树转广义表 如下一棵树转换为广义表 root(c(a()(b()()))(e(d()())(f()(j(h()())())))) (根左子树右子树)
代码实现
#includestdio.h
#includestdlib.h//保存二叉树到文件
#define FNAME ../test16_save/out.txt
#define NAMESIZE 32
struct node_st
{char data;struct node_st *l,*r;
};
struct node_st *treeNULL;
//char型会存在不可预知的字符不用它来传参
int insert(struct node_st **root,int data)
{struct node_st *node;//走到空节点或叶子节点if(*rootNULL){node(struct node_st*)malloc(sizeof(struct node_st));if(nodeNULL)return -1;node-datadata;node-lNULL;//防止野指针的出现node-rNULL;*rootnode;//根节点指向创建出来的新节点后面递归时root为传入的左或右子树的指针return 0; }//比当前节点小的插入左子树比节点大的插入右子树,递归遍历if(data(*root)-data)return insert((*root)-l,data);return insert((*root)-r,data);
}
void draw_(struct node_st *root,int level)
{/*往左边倒画出树的结构先画当前节点的右子树再跟节点最后root-rrootroot-l*/if(rootNULL)return; //空节点或空的叶子结点//先画右子树右子树不止一层所以递归调用画右子树的右子树当前层的下一层draw_(root-r,level1);//画空格,即当前节点前面的空格for(int i0;ilevel;i)printf( );//画根节点printf(%c\n,root-data);//画左子树draw_(root-l,level1);}
void draw(struct node_st *root)
{//根据层数画出树和空格draw_(root,0);
}
//销毁二叉树后序遍历思想先销毁当前节点的左子树再销毁当前节点的右子树最后销毁当前节点
void destroy(struct node_st *root)
{if(rootNULL)return ;destroy(root-l);destroy(root-r);free(root);
}
//保存为广义表的形式根左子树右子树
int save_(struct node_st *root,FILE *fp)
{fputc((,fp);//为空或走到叶子结点if(root NULL){fputc(),fp);return 0;}//不为空把根节点打印出来fputc(root-data,fp);//递归保存左子树save_(root-l,fp);//递归保存右子树save_(root-r,fp);fputc(),fp);return 0;
}
int save(struct node_st *root,const char *path)
{FILE *fpfopen(path,w);if(fpNULL){printf(open file %s failed\n,path);return -1;}// save_(root,fp);save_(tree,fp);fclose(fp);return 0;
}
int main()
{char arr[]cefadjbh;int i;for(i0;isizeof(arr)/sizeof(arr[0])-1;i) //-1是为了去掉最后一个\0{//无头节点要改变指针的指向传二级指针insert(tree,arr[i]);}draw(tree);save(tree,FNAME);destroy(tree);return 0;
}2、根据广义表画出二叉树 假设广义表为 (c(a()(b()()))(e(d()())(f()(j(h()())())))) 画出该二叉树 实现过程先拿到表的第一个字符判断是不是是的话继续拿第二个字符不是的话则为根节点保存该根节点数据继续左右子树的递归存值读完左右子树后继续读最后一个递归结束返回这棵树。
代码实现
#includestdio.h
#includestdlib.h#define FNAME ../test16_save/out.txt
#define NAMESIZE 32
struct node_st
{char data;struct node_st *l,*r;
};
void draw_(struct node_st *root,int level)
{/*往左边倒画出树的结构先画当前节点的右子树再跟节点最后root-rrootroot-l*/if(rootNULL){// printf(Empty node at level %d\n, level); // Debug outputreturn;}//先画右子树右子树不止一层所以递归调用画右子树的右子树当前层的下一层draw_(root-r,level1);//画空格,即当前节点前面的空格for(int i0;ilevel;i)printf( );//画根节点printf(%c\n,root-data);//画左子树draw_(root-l,level1);}
void draw(struct node_st *root)
{//根据层数画出树和空格printf(draw tree:\n);draw_(root,0);
}
struct node_st *load_(FILE *fp)
{int c;struct node_st *root;cfgetc(fp);//读到的第一个一定是不是说明文件有问题if(c!(){fprintf(stderr,fgetc():error\n);exit(1);}cfgetc(fp);//读完 后继续读到,说明树为空if(c))return NULL;//读到根节点保存到root中rootmalloc(sizeof(*root));if(rootNULL){fprintf(stderr,malloc():error\n);exit(1);}root-datac;//继续读左右子树root-lload_(fp);root-rload_(fp);//读完左右子树后继续读最后一个cfgetc(fp);if(c!)){fprintf(stderr,fgetc():error\n);return NULL;}return root;
}
struct node_st *load(const char *path)
{FILE *fp;fpfopen(path,r);struct node_st *root;if(fpNULL){printf(open file %s failed\n,path);return NULL;}rootload_(fp);fclose(fp);return root;
}int main()
{struct node_st *root;rootload(FNAME);draw(root);return 0;
}
