二叉树，文本双向转换

reiase

现在在做一个多分类程序，需要保存二叉树
要求将内存中的二叉树保存成文本形式，文本具有可读性，可编辑性。并且从文本恢复的二叉树与原二叉树相同

目前我想到的方式是保存父子关系，比如：
ABC
BED
CFG
EHI
...

哪位高人给个更好的方案阿

cjaizss

A(B(C,D),E)

converse

我觉得你那个方案就蛮好了,第一个元素是root,第二个是左子树,第三个是右子树

思一克

这个好, 程序简单, 和树结构一致.

缺点是不容易看懂.

原帖由 cjaizss 于 2008-3-31 16:16 发表
A(B(C,D),E)

converse

或者你可以考虑再多一个域保存父节点的,这样一个节点保存的信息就很完备了.

reiase

原帖由 cjaizss 于 2008-3-31 16:16 发表
A(B(C,D),E)

这种表达怎么从文本恢复二叉树呢，是不是要写个解析表达式的代码，具体说清楚下，谢谢

reiase

解决了，使用中序遍历，加栈方式来解决
A(B(C,D),E)实质上是对树的中序遍历，恢复的时候算法如下

take A, make node A
take ( , push A into stack
take B, make node B,left child of A
take ( , push B into stack
take C, make node C,left child of B
take , , nothing
take D, make node D,right child of B
take ) , pop D from stack
take , , nothing
take E, make node E,right child of A
take ) , pop A from stack

reiase

贴下实现代码，很简洁，缺点是有点不稳定

typedef struct _node{     char name[10];     char tempfile0[10];     char tempfile1[10];     uint8_t temp0[stdWidth*stdHeight];     uint8_t temp1[stdWidth*stdHeight];     struct _node *child0;     struct _node *child1; } Node; int readTree(char *filename,Node *tree,int32_t treesize) {     FILE * f;     char lastToken = -1;     char CurrToken = -1;     int32_t CurrTokenLen;     int32_t pn = 0;     int32_t stack[30];     int32_t *stacktop = stack-1;     char whitechar[3]=" \n\t";     memset(tree,0,treesize*sizeof(Node));     f = fopen (filename,"r");     while (!feof(f)){         if (!fscanf(f,"%c",&CurrToken)) goto die;         switch (CurrToken){         case ':':             fscanf(f,"%s",(tree[pn].name));             fscanf(f,"%s",(tree[pn].tempfile0));             fscanf(f,"%s",(tree[pn].tempfile1));             if (lastToken == '(')                 tree[*stacktop].child0 = tree + pn;             if (lastToken == ',')                 tree[*stacktop].child1 = tree + pn;             break;         case '(':             *(++stacktop) = pn;             pn++;             break;         case ')':             stacktop --;             break;         case ',':             pn++;             break;         case ' ':             break;         default:             break;         }         if (CurrToken == ',' || CurrToken == '(' || CurrToken == ')')             lastToken = CurrToken;     } die:     fclose(f);     return 0; } int codeTree(FILE *f,Node *tree) {     int retval = 0;     printf(" : %s %s %s ",tree->name,tree->tempfile0,tree->tempfile1);     if (tree->child0 && tree->child1)     {         printf("\n (");         retval = codeTree(f,tree->child0);         printf(" , ");         retval += codeTree(f,tree->child1);         printf(" ) \n");         return retval;     }     return 1; }

能够解析下述文本

: a a a ( : b b b ( : d d d , : e e e ) , : c c c )

程序中序遍历的输出是

: a a a  ( : b b b  ( : d d d  ,  : e e e  )  ,  : c c c  )

目前文本格式还很难看，正在想办法美化成如下形式

(a a a) {(b b b) {(c c c) , (d d d)},(e e e)}

[ 本帖最后由 reiase 于 2008-4-1 15:01 编辑 ]

converse

LZ,你用递归,而不是循环来实现,可能看起来会好些,如果对性能要求不是很高的话.

reiase

原帖由 converse 于 2008-4-1 14:55 发表
LZ,你用递归,而不是循环来实现,可能看起来会好些,如果对性能要求不是很高的话.

感谢LS的意见，请说清楚点，我不太清楚你指得是哪里