文档库

最新最全的文档下载
当前位置:文档库 > 趣谈数据结构(八)

趣谈数据结构(八)

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

  例1 将一棵一般树(由单字符组成)转换成二叉树
并将转换得到的二叉树按先序、中序、后序进行遍历
输出遍历后结点的序列

  一般树输入方式用父亲与孩子间加括号的串表示

  例如
图1所示的树
串表示输入为:A(B(E)C(FG)D(H(IJK)))

图 1  
  分析:一般树转化为二叉树的方法为:将结点的第一个孩子作为形成二叉树后结点的左孩子
结点的右邻兄弟作为形成二叉树后结点的右孩子

  如图1的树
根结点A的第一个孩子为结点B
则结点B为转化二叉树后结点A的左孩子
结点C是结点B的右邻兄弟
则结点C为转化二叉树后结点B的右孩子
同样
结点D是结点C的右邻兄弟
则为其转化后的右孩子
类推
图2转化后的二叉树形式如图2所示

  分析输入的树串形式可知
左括号后的字符为左括号前字符的左孩子
括号内的字符关系是兄弟
则转化为二叉树后
后面字符为其前一字符的右孩子
故依据左、右括号及字符间的关系
生成结点的左右孩子

  算法步骤:
  ⒈输入串表示的树
并判断输入的树是否合法

  ⒉建立二叉树
设D$存储结点的内容
L、R为其左右孩子的指针
T为操作栈

  建立方法:(1)取第一个字符作为根结点;(2)遇左括号
左括号后字符作为括号前字符结点的左孩子并入操作栈
其它字符为前一字符结点的右孩子
代替栈顶结点;(3) 遇右括号
栈顶指针减1
右括号后字符为栈顶指针指向字符结点的右孩子

  ⒊按先序遍历算法遍历二叉树

            ⒋按中序遍历算法遍历二叉树

            ⒌按后序遍历算法遍历二叉树

  源程序如下:
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