数据结构八.doc

数据结构八
上一讲我们了解了"树"，并建立"树"的基本概念与基本的处理方式。这一讲我们通过几个例子，阐明树的存储方式，树的几个典型的应用，给出了一些常用的算法源程序如下。这些算法源程序如下意在给大家解决有关树问题时，提供一些思考的方向。

　　例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 (i<length(st)) and (st[i+1]='(') then
begin
new(q); q^.son:=nil; q^.bro:=nil;
p^.son:=q;
reading(q);
end;
if (i<length(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 i<>length(st) then err;
end;
procedure pro(p:tree);{先序遍历}
begin
if p<>nil then with p^ do begin
write(note);
pro(son);
pro(bro);
end;
end;
procedure mid(p:tree);{中序遍历}
begin
if p<>nil then with p^ do begin
mid(son);
write(note);
mid(bro);
end;
end;
procedure suc(p:tree);{后序遍历}
begin
if p<>nil then with p^ do begin
suc(son);
suc(bro);
write(note);
end;
end;
procedure show(p:tree);{输出二叉树}
begin
write(p^.note:10);
if p^.son<>nil then write(p^.son^.note:10) else write('^':10);
if p^.bro<>nil then writeln(p^.bro^.note:10) else writeln('^':10);
if p^.son<>nil then show(p^.son);
if p^.bro<>nil then show(p^.bro);
end;
begin{主源程序如下}
clrscr;
read s;
writeln('node':10,'son':10,'brother':14);
show(root);
write('Pro:':6);
pro(root); writeln;
write('Mid:':6);
mid(root);writeln;
write('Suc:':6);
suc(root); writeln;
writeln;
writeln('Press < Enter >...');
readln;
end.

　　例2 试将一段英文中出现的单词按词典的顺序打印出来，同时应注明每个单词在该段文章中出现的次数。
　　分析：将一段英文中的单词按词典顺序打印的过程， 就是由一个无序序列构造有序序列的过程，这个过程可以通过构造二叉排序树实现。
　　设A={a1,a2,a3,...,an}为一组元素的集合， 则按下列规则生成的二叉树就是一棵二叉排序树：
　　⒈令a1为二叉树的根；
　　⒉若a2<a1，则令a2为a1的左子树的根结点，否则，令a2为a1的右子树的根结点；
　　⒊对a3,a4,...,an递归重复步骤２。
　　二叉排序树的意义在于，对它按中根次序遍历得到的序列是有序的。
　　算法步骤：
　　⒈以输入的第一个单词作为生成二叉树的树根；
　　⒉读入单词作为新结点，将新结点值与根结点值比较，将小于根结点值的结点，插入到左子树中去，否则插入到右子树中；若相同对应结点的计数器值加１；
　　⒊重复步骤２，直到文章结束，则整棵二叉树构造完毕。
　　⒋按中序遍历原则遍历此树，所得到的顺序，便是单词的词典顺序，同时输出对应单词计数器值。
　　假设输入英文段落为：
　　Everyone round you can hear you when you sperk
按算法构造的二叉排序树为:　

　　　　　　　　　　　　　　　　　图　3
　　源程序如下：
program word_order;{93.11.11. 单词排序,用二叉排序树解决}
type
tree=^treetype;
treetype=record
wd:string;
tm:integer;
lt,rt:tree;
end;
link=^linktype;
linktype=record
wd:string;
tm:integer;
next:link;
end;
const
letter=['a'..'z','A'..'Z'];
var
head:link;
root:tree;
n,st:string;
procedure readword;{输入单词}
var
q,p:link;
w:string;
begin
head:=nil;
repeat
write('Word(return means end):');
readln(w);
if w<>'' then begin
p:=head;
while (p<>nil) and (p^.wd<>w) do p:=p^.next;
if p=nil then begin
new(q);q^.wd:=w;q^.tm:=1;q^.next:=head;head:=q;
end;
else inc(p^.tm);
end;
until w='';
end;
procedure create;{建立二叉排序树}
var
p,r:tree;
f:boolean;
q:link;
begin
new(root);
with root^ do begin
wd:=head^.wd;tm:=head^.tm;lt:=nil;rt:=nil;
end;
q:=head^.next;
while q<>nil do begin
p:=root;
new(r);
r^.lt:=nil;r^.rt:=nil;r^.wd:=q^.wd;r^.tm:=q^.tm;
f:=true;
while f do begin
if q^.wd<p^.wd then
if p^.lt<>nil then p:=p^.lt
else
begin p^.lt:=r;f:=false end
else
if p^.rt<>nil then p:=p^.rt
else
begin p^.rt:=r;f:=false end
end;
q:=q^.next;
end;
end;
procedure pr_tree(p:tree);{输出}
begin
if p^.lt<>nil then pr_tree(p^.lt);
writeln(p^.wd:20,p^.tm:5);
if p^.rt<>nil then pr_tree(p^.rt);
end;
begin
readword;
create;
pr_tree(root);
write('Press <Enter>...');readln;
end.

　　例3 输入一个算术表达式，判断该表达式是否合法， 输出合法表达式的表达式树。
　　分析：表达式不合法有以下三种情况：(1)左右括号不匹配；(2)变量名不合法；(3)算符两旁无参与运算的变量或数。
　　分析表达式树可以看到：表达式的根结点及其子树的根结点为算符，其在树中的顺序是按运算的先后顺序从后到先，表达树的叶子为参与运算的变量或数。
　　如表达式：　　ａ＋（ｂ－ｃ）/ ｄ　　
　　运算顺序：　　　③　　①　　②
　　表达式树为：

　　　　　　　　　　　　图　4
　　处理时，首先找到运算级别最低的运算符"＋"作为根结点，继而确定该根结点的左、右子树结点在表达式串中的范围为ａ和（ｂ－ｃ）/ｄ， 再在对应的范围内寻找运算级别最低的运算符作为子树的根结点，直到范围内无运算符，则剩余的变量或数为表达式树的叶子。
　　算法步骤：
　　⒈设数组X$存放表达式串的各字符，数组D$存放结点的字符，Lt、Rt作为结点的左右指针，数组L、R用于存放每次取字符范围的左右界。
　　⒉设置左界初值为１，右界初值为串长度。
　　⒊判断左右括号是否匹配，不匹配则输入出错。
　　⒋在表达式的左右界范围内寻找运算级别最低的运算符，同时判断运算符两旁有否参与运算的变量或数，若无则输入表达不合法。若有作为当前子树的根结点，设置左子树指针及其左右界值，设置右子树指针及其左右界值。
　　⒌若表达式在左右界范围内无算符，则为叶子结点，判断变量名或数是否合法。
　　⒍转４，直到表达式字符取完为止。
　　⒎源程序如下中数组H、D、W用于存放文本画图时结点的座标位置。
　　源程序如下：
program pr_exp;
uses crt;
type point=^tree;
tree=record
data:string;
lt:point;
rt:point;
end;
var n,len,k:integer;
ex:string;
letters:set of char;
root:point;
procedure error(er:byte);{出错信息提示}
begin
write('enter error :');
case er of
1:writeln('no letter');
2,3:writeln('no expressint');
4:writeln('no + , * , - or / ');
5:writeln('no ( or )');
end;
write('press<enter>...');readln;halt(1);
end;
procedure create(left,right:integer;var p:point);
var q:point;
k,n:integer;
begin {找运算级别最低的运算符}
if ex[left]='(' then
begin
n:=left+1;k:=0;
while (n<right) and (k>=0) do
begin
if ex[n]='(' then inc(k);
if ex[n]=')' then dec(k);
inc(n);
end;
if n=right then
begin
dec(right);inc(left);
end;
end;
if right<left then error(1);
n:=right;k:=0;
repeat
if ex[n]=')' then inc(k);
if ex[n]='(' then dec(k);
dec(n);
until (((ex[n]='+') or (ex[n]='-')) and (k=0)) or (n<left);
if n=left then error(3);
if n>left then
begin with p^ do
begin
data:=ex[n];
new(q);lt:=q;
new(q);rt:=q;
end;
create(left,n-1,p^.lt);
create(n+1,right,p^.rt);
end
else {not found '+''-'}
begin
n:=right;
repeat
if ex[n]=')' then inc(k);
if ex[n]='(' then dec(k);
dec(n);
until (((ex[n]='*') or (ex[n]='/')) and (k=0)) or (n<left);
if n=left then error(3);
if n>left then
begin with p^ do
begin
data:=ex[n];
new(q);rt:=q;
new(q);lt:=q;
end;
create(left,n-1,p^.lt);
create(n+1,right,p^.rt);
end
else {only string}
begin {求叶子结点的字串}
for k:=left to right do if not (ex[k] in letters) then error(1);
p^.data:='';
for k:=left to right do p^.data:=p^.data+ex[k];
p^.lt:=nil;
p^.rt:=nil;
end;
end;
end;
procedure pr_tree(w,dep:integer;p:point);{画出生成的表达式树}
var h,i,lt,rt:integer;
begin
h:=40;for i:=1 to dep do h:=h div 2;
gotoxy(w-1,dep*3);write('(',p^.data,')');
if p^.lt=nil then
lt:=w
else begin
lt:=w-h;pr_tree(lt,dep+1,p^.lt)
end;
if p^.rt=nil then rt:=w
else begin
rt:=w+h;pr_tree(rt,dep+1,p^.rt);
end;
if lt<>rt then
begin
gotoxy(w,dep*3+1);write('!');
gotoxy(lt,3*dep+2);write('!');
for i:=lt to rt-2 do write('-');write('!');
end;
end;
begin
clrscr;
letters:=['A'..'Z','a'..'z','0'..'9'];
repeat
write('enter expression:');readln(ex);
len:=length(ex)
until len>0;
n:=1;
k:=0;
while (n<=len) and (k>=0) do {判断左括号是否匹配}
begin
if ex[n]='(' then inc(k);
if ex[n]=')' then dec(k);
inc(n);
end;
if k<>0 then error(5);
new(root);create(1,len,root);
pr_tree(40,1,root);readln
end.