Pascal二叉树后序中序转前序
在二叉树的应用中,常常要求在树中查找具有某种特征的结点,或者对全部结点逐一进行某种处理。
这就是二叉树的遍历问题。所谓二叉树的遍历是指按一定的规律和次序访问树中的各个结点,而且每个结
点仅被访问一次。“访问”的含义很广,可以是对结点作各种处理,如输出结点的信息等。遍历一般按照从
左到右的顺序,共有3 种遍历方法,先(根)序遍历,中(根)序遍历,后(根)序遍历。
一先序遍历的操作定义如下:
若二叉树为空,则空操作,否则
①访问根结点
②先序遍历左子树
③先序遍历右子树
先序遍历右图结果为:124753689
procedure preorder(bt:tree); //先序遍历根结点为bt 的二叉树的递归算法
begin
if btnil then begin
write(bt^.data);
preorder(bt^.lchild);
preorder(bt^.rchild);
end;
end;
二中序遍历的操作定义如下:
若二叉树为空,则空操作,否则
①中序遍历左子树
②访问根结点
③中序遍历右子树
中序遍历右图结果为:742513869
procedure inorder(bt:tree); //中序遍历根结点为bt 的二叉树的递归算法
begin
if btnil then begin
preorder(bt^.lchild);
write(bt^.data);
preorder(bt^.rchild);
end;
end;
三后序遍历的操作定义如下:
若二叉树为空,则空操作,否则
①后序遍历左子树
②后序遍历右子树
③访问根结点
后序遍历右图结果为:745289631
procedure postorder(bt:tree); //后序遍历根结点为bt 的二叉树的递归算法
begin
if btnil then begin
preorder(bt^.lchild);
preorder(bt^.rchild);
write(bt^.data);
end;
end;
当然,我们还可以把递归过程改成用栈实现的非递归过程,以先序遍历为例,其它的留给作者完成。
Procedure preorder(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 btnil do begin //非叶结点
Write(bt^.data); //访问根
top:=top+1; //右子树压栈
stack[top]:=bt^.rchild
bt:=bt^.lchild; //遍历左子树
end;
If top0 then begin //栈中所有元素出栈,遍历完毕
bt:=stack[top];
top:=top-1;
End;
End;
End;
首先知道:
先序:根左右;后序,左右根;中序,左根右。
看过程:是递归调用的:
if length(s2)=1 then write(s2){如果当前后序遍历只有一个就直接输出该位置}
else begin
k:=pos(s2[length(s2)],s1);{后序排序的最后一个是当前序列的根,寻找根在中序排序中的位置,则中序排序被跟分成前面后面两节,前面那节是左子树,后面是右子树}
write(s1[k]);{先序是先输出根}
if k>1 then solve(copy(s1,1,k-1),copy(s2,1,k-1));{如果左子树存在就递归调用}
if k<length(s1)
then
solve(copy(s1,k+1,length(s1)-k),copy(s2,k,length(s2)-k));{如果存在右子树递归调用}
end;
solve(copy(s1,1,k-1),copy(s2,1,k-1))本句话的意思是,s1序列从第1个到第k-1个是左子树,s2前面同样的长度也是左子树,所以,相当于把这个问题又分成了个新的和先一样的问题,已知中序和后序,求先序,那不就是可以递归了,只不过长度改变了,变成原来的左子树。
其实意思很简单,就是每次都找到根输出,然后遍历左子树,遍历右子树,然后对左子树同样,先输出根,再访问左子树,右子树,。。。递归调用。
那么每次就是要找到根是哪个就可以,所以我门根据: 先序:根左右;后序,左右根;中序,左根右。特点知道怎么找根,然后递归调用。
同理可以知道
solve(copy(s1,k+1,length(s1)-k),copy(s2,k,length(s2)-k));
是在访问递归调用右子树。
procedure solve(mid,post:string);
var i:integer;
begin
if (mid='') or (post='') then exit;
pre:=pre+post[length(post)];
i:=pos(post[length(post)],mid);
solve(copy(mid,1,i-1),copy(post,1,i-1));
solve(copy(mid,i+1,length(mid)-i),copy(post,i,length(post)-i));
end;
begin
readln(st1);//中序
readln(st2);//后序
solve(st1,st2);
writeln(pre);//前序
end.
有必要怀疑你是常训班上的,这张图是前序中序转后序,改一下细节吧
中级程序员考什么?
(9)熟练掌握软件设计的方法和技术;(10)掌握常用信息技术标准、安全性,以及有关法律、法规的基本知识;(11)了解信息化、计算机应用的基础知识;(12)正确阅读和理解计算机领域的英文资料。如果你以后专攻C++的话,把C的基础打好就可以了,不用学的那么精通,但一定要打好基础。
哈夫曼树与哈夫曼编码、集合
如何根据结点不同的查找频率 构造更有效的搜索树?带权路径长度(WPL):设二叉树有n个叶子结点,每个叶子结点带有权值(即频率)Wk,从根结点到每个叶子结点的长度为Lk,则每个叶子结点的带权路径长度之和为 WPL=W1 L1+W2 L2+ …… +Wn*Ln 目标:将WPL降到最低。最优二叉树或哈夫曼树就...
霍夫曼(Huffman)编码学习的重点和难点是什么
(nDesIndex>>3): >>3 以8位为界限右移后到达右边字节的前面 (nDesIndex&7): &7 得到最高位.注意:在压缩缓冲区中,我们必须保存哈夫曼树的节点以及位序列,这样我们才能在解压缩时重新构造哈夫曼树(只需保存ASCII值和对应的位序列)。解压缩 解压缩比构造哈夫曼树要简单的多,将输入缓冲区中...
历年计算机软件水平考试程序员部分真题
考虑具有如下性质的二叉树:除叶子结点外, ○n1 崐每个结点的值都大于其左子树上的一切结点的值, \/\\ 崐并小于等于其右子树上的一切结点的值。 ○n2 ○n3 现把9个数1,2,3,4…8,9填入右图 \/\\\\ 所示的二叉树的9个结点中,并使之具有上述性质 ○n4 ○n5 ○n6崐此时,n1的值是_a_,n2的值是_b_,n9...
编程时怎样把计算机里面的0和1编写成文字.
如100的阶乘、链表的操作、二叉树的遍历等问题等。完成了以上问题后基本上对编程就有了概念,这时候在开始学习一些可视化编程工具,如VB、VC等,你可以参照别人已经编写好的程序开始学习一些如俄罗斯方块、连连看等游戏了,等你到这个地步后就要看你个人的发展了。可以向算法设计、数据库编程、网络编程等...
排序算法概述
所谓二叉堆,是一个完全二叉树的结构,同时满足堆的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。在一个二叉堆中,根节点总是最大(或者最小)节点。 堆排序算法就是抓住了这一特点,每次都取堆顶的元素,然后将剩余的元素重新调整为最大(最小)堆,依次类推,最终得到排序的序列。 推论1:对于位置为K的...
patricia tree是什么
(3) 递归执行第2步,将CUHK、HK、K进一步插入到PAT tree中。流程如下图所示。所有sistring都插入以后结束。注意:既然PAT tree 是二叉查找树,那么一定要满足二叉查找树的特点。所以,内部结点中的bit 位就需要满足,左孩子的bit 位< 结点bit 位< 右孩子的bit 位。PAT tree的检索过程 利用PAT tree...
急求计算机二级考试的试题(C语言)
程序运行后,文件t1.dat中的内容是 A)start B)end C)startend D)endrt 1.某二叉树中度为2的结点有18个,则该二叉树中有___个叶子结点。 答案:19 2.在面向对象方法中,类的实例称为___. 答案:对象 3.诊断和改正程序中错误的工作通常称为___. 答案:调试 4.在关系数据库中,把数据表示成二维表,每一...
有一个根结点,且只有一个叶子结点的数据结构一定是线性结构,对吗?为 ...
这个判断是不完整的。有一个根结点,且只有一个叶子结点的树形结构一定是线性结构。这句话才对。
第十五届全国青少年信息学奥林匹克联赛初赛试题答案带分析PASCAL_百度...
B高级语言可以使用底层硬件,编译后生成目标代码,可以在硬件系统上执行 C 以前的真题中出现过该选项,高级语言的特点 第十题:选择D 64+9=74 第十三题:主要是考树的遍历,要明白前缀、中缀和后缀表达式。构造二叉树,操作数做叶子节点,运算符做非叶节点。按中序遍历就可以得到中缀表达式。第十四题...
宗圣寿排毒: 自己写个stack 我给你写的前后中写法吧. 前MyStack<TreeNode *> stack;while(true){while (lpCurNode){if (lpfun!=NULL){(this->*lpfun)(lpCurNode);stack.Push(lpCurNode);}lpCurNode=lpCurNode->m_lpLeft;}if (!stack.Pop(lpCurNode))...
江洲区15739981400: 二叉树的已知后序中序求先序算法 - ?
宗圣寿排毒: /* 树中已知中序和后序求先序.如中序为:bdac 后序为:dbca则程序可以求出先序为:abdc .此种题型为数据结构常考题型. 算法思想:后序遍历树的规则为左右中,则说明最后一个元素必为树的根节点,比如上例 中的a就为根节点,由于...
江洲区15739981400: 已知二叉树的后序和中序怎么求前序 - ?
宗圣寿排毒: 根据所给两条序列找出根结点,再根据此两序列画出示意图,自然可以写出前序序列
江洲区15739981400: 已知二叉树的后序遍历序列和中序遍历序列,怎样求其前序遍历序列! - ?
宗圣寿排毒: 首先理解概念: 前序遍历:访问根结点的操作发生在遍历其左右子树之前. 中序遍历:访问根结点的操作发生在遍历其左右子树之中(间). 后序遍历:访问根结点的操作发生在遍历其左右子树之后. eg:后序遍历为DBCEFGHA,中序遍历为EDCBAHFG,求前序遍历(网上例子) 解:首先 看后序遍历DBCEFGHA,A为总根节点然后 寻找中序遍历EDCBAHFG中A位置,则EDCB在A的左枝,HFG在A的右枝;重复前两步,从后序遍历最后一位找,在中序遍历寻找对应点,得出左右分枝...最后得到AECDBHGF,再自己验证即可...
江洲区15739981400: 二叉树先知道后序和中序,求先序 - ?
宗圣寿排毒: 后序DABEC 中序DEBAC 由后序最后一个字母知:整个树的开始结点为C; 由中序C的位置知:C前面的为结点C的左子树;C后面的为结点C的右子树; 所以经过第一次推理,C为根结点,DEBA为其左子树; 然后去掉C,考虑下面的左子树; 后序DABE 中序DEBA 由后序最后一个字母知:整个左子树的开始结点为E; 由中序E的位置知:E前面的为结点E的左子树;E后面的为结点E的右子树; 所以经过第一次推理,E为开始结点,D为E的左结点.BA为E的右结点. 然后去掉DE,考虑下面E的右子树; 后序AB 中序BA 易知:B为根结点,A为其右结点. 所以整个树为:C(E(D,B(,A))); 先序:CEDBA
江洲区15739981400: 输入两个字符串,分别是一颗二叉树的中序和后序,编程输出其先序.(Pascal) - ?
宗圣寿排毒: program qiuqianxu; var s1,s2,s:string; procedure sou(s1,s2:string); var t,k,l:longint; c:char; begin c:=s2[length(s2)]; {后序排列的尾是先序排列的头} for t:=1 to length(s1) do if s1[t]=c then break; write(c); if t>1 then sou(copy(s1,1,t-1),copy(s2,1,t-1)); ...
江洲区15739981400: 已知二叉树的中、后遍历序列,推导出前序遍历. - ?
宗圣寿排毒: 1、确定树的根.树根是当前树中所有元素在后序遍历中最后出现的元素.2、求解树的子树.找出根节点在中序遍历中的位置,根左边的所有元素就是左子树,根右边的所有元素就是右子树.若根节点左边或右边为空,则该方向子树为空;若根节点左边和右边都为空,则根节点已经为叶子节点.3、递归求解树.将左子树和右子树分别看成一棵二叉树,重复1、2、3步,直到所有的节点完成定位.
江洲区15739981400: 跪求知道二叉树的中序遍历和后续遍历求前序遍历程序.必须是pascal的.好的程序一定给采纳.跪求! - ?
宗圣寿排毒: 程序: vars1,s2:string; procedure solve(s1,s2:string); vark:integer; beginif length(s2)=1 then write(s2)else begink:=pos(s2[length(s2)],s1);write(s1[k]);if k>1 then solve(copy(s1,1,k-1),copy(s2,1,k-1));if k<length(s1)thensolve(copy(s1,k+1,...
江洲区15739981400: 由二叉树的后序遍历和中序遍历,怎么推出它的前序遍历? - ?
宗圣寿排毒: 这个简单啊,都能口算了,从后序中得c为根节点 然后到中序中找,c右边没有所以没有右孩子 在后序中a为最后,所以a是左孩子的根节点 在中序中d在其左边be在其右边 所以分别为其左子树和右子树 e为b的右子树 前序:cadbe
江洲区15739981400: pascal二叉树 - ?
宗圣寿排毒: 我来告诉你啊.前序的顺序是:根,左,右 中序的顺序是:左,根,右 后序的顺序是:左,右,根 如果你要求中序,那么我出个例子 前序ABCDE 后序CEBDA 中序就是:CBAED 推断过程就是:第一步,确定根A(因为后序的最后一个字母和...