pascal中二叉树遍历
发布网友
发布时间：2022-04-24 18:34
共3个回答
热心网友
时间：2022-04-22 18:17
这是noi的教材的，我也没花多少时间去看。我先复制给你吧。
二叉树的遍历
在二叉树的应用中，常常要求在树中查找具有某种特征的结点，或者对全部结点逐一进行某种处理,这就是二叉树的遍历问题。所谓二叉树的遍历是指按一定的规律和次序访问树中的各个结点，而且每个结点仅被访问一次。“访问”的含义很广，可以是对结点作各种处理，如输出结点的信息等。遍历方法共有3种：先序（根）遍历，中序（根）遍历，后序（根）遍历。下面以图10所示的二叉树为例分别讲解这3种方法。
图10
1．先序遍历的操作定义如下：
若二叉树为空，则空操作，否则
① 访问根结点
② 先序遍历左子树
③ 先序遍历右子树
很明显，这是一种递归定义，下面给出一种手工方法（括号法）求先序遍历的结果。
={1，2，3，4，5，6，7，8，9} {所有结点}
={1，{2，4，5，7}，{3，6，8，9}} {按先序思想遍历，将根结点单独列出，左右子树分别用括号括起来}
={1，{2，{4，7}，{5}}，{3，{}，{6，8，9}}} {再对以2、3结点为根的树先序遍历}
={1，{2，{4，{7}，{}，5}，{3，{}，6，{8}，{9}}} {再对以4、5、6结点为根的树先序遍历，遇到无左、右子树的情况就用一对空括号，遇到叶子结点就脱到本层括号，遇到空括号就省略}
={1，2，4，7，5，3，6，8，9} {去掉内层所有括号，得到结果}
2．中序遍历的操作定义如下：
若二叉树为空，则空操作，否则
① 中序遍历左子树
② 访问根结点
③ 中序遍历右子树
可以根据以上方法，得出上图中序遍历的结果为：{7，4，2，5，1，3，8，6，9}
3．后序遍历的操作定义如下：
若二叉树为空，则空操作，否则
① 后序遍历左子树
② 后序遍历右子树
③ 访问根结点
可以根据以上方法，得出上图后序遍历的结果为：{7，4，5，2，8，9，6，3，1}
显然，以上3种遍历方法都是采用递归的思想，下面以先序遍历为例给出递归算法：
Procere preorder(bt:tree)；{先序遍历根结点为bt的二叉树的递归算法}
Begin
If bt<>Nil Then Begin
Write(bt^.data)；
preorder(bt^.lchild)；
preorder(bt^.rchild)；
End；
End；
我们也可以把递归过程改成用栈实现的非递归过程，下面给出先序遍历的非递归过程。
Procere inorder(bt:tree)； {先序遍历bt所指的二叉树}
Var stack:Array[1..n] Of tree； {栈}
top:integer； {栈顶指针}
p:tree；
Begin
top:=0；
While Not ((bt=Nil)And(top=0)) Do
Begin
While bt<>Nil Do Begin {非叶结点}
Write(bt^.data)； {访问根}
top:=top+1； {右子树压栈}
stack[top]:=bt^.rchild；
bt:=bt^.lchild； {遍历左子树}
End；
If top<>0 Then Begin {栈中所有元素出栈，遍历完毕}
b:=stack[top]；top:=top-1；
End；
End；
End；
关于前面讲的表达式树，我们可以分别用先序、中序、后
序的遍历方法得出完全不同的遍历结果，对于图11采用三种遍历后的结果如下，它们正好对应着表达式的三种表示方法：
-+a*b-cd/ef (前缀表示、波兰式)
a+b*c-d-e/f (中缀表示、代数式)
abcd-*+ef/- (后缀表示、逆波兰式)
参考资料：js noi 08 03 讲义
热心网友
时间：2022-04-22 19:35
哈，我也是编程爱好者，用Pascal，在北京。看看一下网址吧！经常不间断更新！
http://www.mydrs.org/program/
给你一个——二叉树后根遍历：
Program Tree (input,output);
Var
p : Word;
Mid,Pre : String;
Procere Init;
Begin
Write('In-order:');
Readln(Mid);
Write('Pre-order:');
Readln(Pre);
Write('Post-order:');
p:=0;
End;
Procere Find(s : String);
Var
i,q : Word;
Begin
If s='' Then Exit;
Inc(p);
q:=Pos(Pre[p],s);
If Length(s) > 1 Then
Begin
Find(Copy(s,1,q-1));
Find(Copy(s,q+1,Length(s)-q));
End;
Write(s[q]);
End;
Begin
assign(input,'tree.in');
assign(output,'tree.out');
reset(input);rewrite(output);
Init;
Find(Mid);
Writeln;
close(input);
close(output);
End.
（用字符串处理即可解决）
热心网友
时间：2022-04-22 21:09
请问你的二叉树是怎么输入的，中序先序还是后序输入？还是高级数据结构？还是完全二叉树层次遍历？请说得清楚点啊
