趣谈数据结构（八）上一讲我们了解了"树"，并建立"树"的基本概念与基本的处理方式。这一讲我们通过几个例子，阐明树的存储方式，树的几个典型的应用，给出了一些常用的算法源程序如下。这些算法源程序如下意在给大家解决有关树问题时，提供一些思考的方向。例1将一棵一般树（由单字符组成）转换成二叉树，并将转换得到的二叉树按先序、中序、后序进行遍历，输出遍历后结点的序列。一般树输入方式用父亲与孩子间加括号的串表示。例如，图1所示的树，串表示输入为:A(B(E)C(FG)D(H(IJK)))图1分析：一般树转化为二叉树的方法为：将结点的第一个孩子作为形成二叉树后结点的左孩子，结点的右邻兄弟作为形成二叉树后结点的右孩子。如图1的树，根结点Ａ的第一个孩子为结点Ｂ，则结点Ｂ为转化二叉树后结点Ａ的左孩子，结点Ｃ是结点Ｂ的右邻兄弟，则结点Ｃ为转化二叉树后结点Ｂ的右孩子，同样，结点Ｄ是结点Ｃ的右邻兄弟，则为其转化后的右孩子。类推，图2转化后的二叉树形式如图2所示。分析输入的树串形式可知，左括号后的字符为左括号前字符的左孩子，括号内的字符关系是兄弟，则转化为二叉树后，后面字符为其前一字符的右孩子。故依据左、右括号及字符间的关系，生成结点的左右孩子。算法步骤：⒈输入串表示的树，并判断输入的树是否合法。⒉建立二叉树，设D$存储结点的内容，L、R为其左右孩子的指针，T为操作栈。建立方法：(1)取第一个字符作为根结点；(2)遇左括号，左括号后字符作为括号前字符结点的左孩子并入操作栈，其它字符为前一字符结点的右孩子，代替栈顶结点；(3)遇右括号，栈顶指针减１，右括号后字符为栈顶指针指向字符结点的右孩子。⒊按先序遍历算法遍历二叉树。⒋按中序遍历算法遍历二叉树。⒌按后序遍历算法遍历二叉树。源程序如下：programtree1;usescrt;typetree=^tre;tre=recordnote:char;son,bro:tree;end;varroot:tree;procedureerr;beginwriteln('InputError!');halt;end;procedurereads;{读入树串,边判错边建立二叉树}constch:setofchar=['A'..'Z','a'..'z'];varst:string;ss:setofchar;i:byte;procedurereading(varp:tree);varq:tree;begininc(i);casest[i]of'(':beginreading(p);INC(I);ifst[i]<>')'thenerr;end;'A'..'Z','a'..'z':beginif(st[i]inss)thenerr;p^.note:=st[i];ss:=ss+[st[i]];if(i<length(st))and(st[i+1]='(')thenbeginnew(q);q^.son:=nil;q^.bro:=nil;p^.son:=q;reading(q);end;if(i<length(st))and(st[i+1]inch)thenbeginnew(q);q^.son:=nil;q^.bro:=nil;p^.bro:=q;reading(q);end;end;elseerr;end;end;beginwrite('TheString:');readln(st);ifnot(st[1]inch)thenerr;new(root);root^.son:=nil;root^.bro:=nil;i:=0;ss:=[];reading(root);ifi<>length(st)thenerr;end;procedurepro(p:tree);{先序遍历}beginifp<>nilthenwithp^dobeginwrite(note);pro(son);pro(bro);end;end;proceduremid(p:tree);{中序遍历}beginifp<>nilthenwithp^dobeginmid(son);write(note);mid(bro);end;end;proceduresuc(p:tree);{后序遍历}beginifp<>nilthenwithp^dobeginsuc(son);suc(bro);write(note);end;end;procedureshow(p:tree);{输出二叉树}beginwrite(p^.note:10);ifp^.son<>nilthe