趣谈数据结构(八)83.doc

趣谈数据结构(八)83 读书破万卷，下笔如有神——杜甫 趣谈数据结构（八） 上一讲我们了解了树，并建立树的基本概念与基本的处理方式 这一讲我们通过几个例子，阐明树的存储方式，树的几个典型的应用，给出了一些常用的算法源程序如下 这些算法源程序如下意在给大家解决有关树问题时，提供一些思考的方向 　　例1 将一棵一般树（由单字符组成）转换成二叉树， 并将转换得到的二叉树按先序、中序、后序进行遍历，输出遍历后结点的序列 　　一般树输入方式用父亲与孩子间加括号的串表示 　　例如，图1所示的树，串表示输入为:A(B(E)C(FG)D(H(IJK))) 图　1　　 　　分析：一般树转化为二叉树的方法为：将结点的第一个孩子作为形成二叉树后结点的左孩子，结点的右邻兄弟作为形成二叉树后结点的右孩子 　　如图1的树，根结点Ａ的第一个孩子为结点Ｂ，则结点Ｂ为转化二叉树后结点Ａ的左孩子，结点Ｃ是结点Ｂ的右邻兄弟，则结点Ｃ为转化二叉树后结点Ｂ的右孩子，同样，结点Ｄ是结点Ｃ的右邻兄弟，则为其转化后的右孩子 类推，图2转化后的二叉树形式如图2所示 　　分析输入的树串形式可知，左括号后的字符为左括号前字符的左孩子，括号内的字符关系是兄弟，则转化为二叉树后，后面字符为其前一字符的右孩子 故依据左、右括号及字符间的关系，生成结点的左右孩子 　　算法步骤： 　　⒈输入串表示的树，并判断输入的树是否合法 　　⒉建立二叉树，设D$存储结点的内容，L、R为其左右孩子的指针，T为操作栈 　　建立方法：(1)取第一个字符作为根结点；(2)遇左括号，左括号后字符作为括号前字符结点的左孩子并入操作栈，其它字符为前一字符结点的右孩子，代替栈顶结点；(3) 遇右括号，栈顶指针减１，右括号后字符为栈顶指针指向字符结点的右孩子 　　⒊按先序遍历算法遍历二叉树 　　 　　　　　　　　　⒋按中序遍历算法遍历二叉树 　 　　　　　　　　　　⒌按后序遍历算法遍历二叉树 　　源程序如下： program tree1; uses crt; type tree=^tre; tre=record note:char; son,bro:tree; end; var root:tree; procedure err; begin writeln(Input Error!); halt; end; procedure reads; {读入树串,边判错边建立二叉树} const ch:set of char=[A..Z,a..z]; var st:string; ss:set of char; i:byte; procedure reading(var p:tree); var q:tree; begin inc(i); case st[i] of (:begin reading(p); INC(I); if st[i]) then err; end; A..Z,a..z: begin if (st[i] in ss) then err; p^.note:=st[i]; ss:=ss+[st[i]]; if (ilength(st)) and (st[i+1]=() then begin new(q);q^.son:=nil;q^.bro:=nil; p^.son:=q; reading(q); end; if (ilength(st)) and (st[i+1] in ch) then begin new(q);q^.son:=nil;q^.bro:=nil; p^.bro:=q; reading(q); end; end; else err; end; end; begin write(The String:); readln(st); if not (st[1] in ch) then err; new(root);root^.son:=nil;root^.bro:=nil; i:=0;ss:=[]; reading(root); if ilength(st) then err; end; procedure pro(p:tree);{先序遍历} begin if pnil then with p^ do begin write(note); pro(son); pro(bro); end; end; procedure mid(p:tree);{中序遍历} begin if pnil then with p^ do begin mid(son); write(note); mid(bro); end; end; procedure suc(p:tree);{后序遍历} begin if pnil then with p^ do begin suc(son); suc(bro); write(no