当前位置：文档库 › 趣谈数据结构(八)

趣谈数据结构(八)

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

例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 (inew(q);q^.son:=nil;q^.bro:=nil;
p^.son:=q;
reading(q);
end;
if (i

nd (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;
reads;
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则令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
lette

r=['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^.wdif 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 ...');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...');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=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 rightn:=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 (nif 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 (nif 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.