数据结构 ——二叉树转广义表

数据结构 ——二叉树转广义表

1、树转广义表
如下一棵树，转换为广义表

root=(c(a()(b()()))(e(d()())(f()(j(h()())())))) (根（左子树）（右子树）)

• 代码实现

#include<stdio.h>
#include<stdlib.h>//保存二叉树到文件
#define FNAME "../test16_save/out.txt"
#define NAMESIZE 32
struct node_st
{char data;struct node_st *l,*r;
};
struct node_st *tree=NULL;
//char型会存在不可预知的字符，不用它来传参
int insert(struct node_st **root,int data)
{struct node_st *node;//走到空节点或叶子节点if(*root==NULL){node=(struct node_st*)malloc(sizeof(struct node_st));if(node==NULL)return -1;node->data=data;node->l=NULL;//防止野指针的出现node->r=NULL;*root=node;//根节点指向创建出来的新节点，后面递归时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(root==NULL)return; //空节点或空的叶子结点//先画右子树，右子树不止一层，所以递归调用，画右子树的右子树（当前层的下一层）draw_(root->r,level+1);//画空格,即当前节点前面的空格for(int i=0;i<level;i++)printf("  ");//画根节点printf("%c\n",root->data);//画左子树draw_(root->l,level+1);}
void draw(struct node_st *root)
{//根据层数画出树和空格draw_(root,0);
}
//销毁二叉树，后序遍历思想：先销毁当前节点的左子树，再销毁当前节点的右子树，最后销毁当前节点
void destroy(struct node_st *root)
{if(root==NULL)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 *fp=fopen(path,"w");if(fp==NULL){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(i=0;i<sizeof(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()())())))) 画出该二叉树
实现过程：先拿到表的第一个字符，判断是不是（，是的话继续拿第二个字符，不是）的话，则为根节点，保存该根节点数据；继续左右子树的递归存值，读完左右子树后，继续读最后一个），递归结束，返回这棵树。

• 代码实现

#include<stdio.h>
#include<stdlib.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(root==NULL){//   printf("Empty node at level %d\n", level);  // Debug outputreturn;}//先画右子树，右子树不止一层，所以递归调用，画右子树的右子树（当前层的下一层）draw_(root->r,level+1);//画空格,即当前节点前面的空格for(int i=0;i<level;i++)printf("  ");//画根节点printf("%c\n",root->data);//画左子树draw_(root->l,level+1);}
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;c=fgetc(fp);//读到的第一个一定是（，不是说明文件有问题if(c!='('){fprintf(stderr,"fgetc():error\n");exit(1);}c=fgetc(fp);//读完（ 后，继续读到）,说明树为空if(c==')')return NULL;//读到根节点，保存到root中root=malloc(sizeof(*root));if(root==NULL){fprintf(stderr,"malloc():error\n");exit(1);}root->data=c;//继续读左右子树root->l=load_(fp);root->r=load_(fp);//读完左右子树后，继续读最后一个）c=fgetc(fp);if(c!=')'){fprintf(stderr,"fgetc():error\n");return NULL;}return root;  
}
struct node_st *load(const char *path)
{FILE *fp;fp=fopen(path,"r");struct node_st *root;if(fp==NULL){printf("open file %s failed\n",path);return NULL;}root=load_(fp);fclose(fp);return root;
}int main()
{struct node_st *root;root=load(FNAME);draw(root);return 0;
}