关于前序,中序,后序的一个简单问题/(50分)

  • 主题发起人 主题发起人 ZHUOFUHAO
  • 开始时间 开始时间
Z

ZHUOFUHAO

Unregistered / Unconfirmed
GUEST, unregistred user!
假设一棵二叉树的后序遍历序列为DGJHEBIFCA,中序遍历序列为DBGEHJACIF,则其前序遍历序列为 ( ) 。
A、ABCDEFGHIJ B、ABDEGHJCFI C、ABDEGHJFIC D、ABDEGJHCFI
小弟在好多地方都看到过这样的题目,请问大富翁高手,请问做这样的题目有没有规律/
或者方法,是不是只能用一个一个排除!
 
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TForm1 = class(TForm)
Edit1: TEdit;
Edit2: TEdit;
Edit3: TEdit;
Button1: TButton;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;

var
Form1: TForm1;
implementation
{$R *.dfm}
function GetPStr(NStr, MStr: string): string;
type
TTree = ^TNode;
TNode = record
c: Char;
LChild, RChild: TTree
end;
var
Root: TTree;
function MakeTree(NStr, MStr: string): TTree;
var
p: Integer;
begin
if NStr='' then
Result:=nil
else
begin
New(Result);
Result^.c:=NStr[Length(NStr)];
p:=Pos(Result^.c, MStr);
Result^.LChild:=MakeTree(Copy(NStr, 1, p-1), Copy(MStr, 1, p-1));
Result^.RChild:=MakeTree(Copy(NStr, p, Length(NStr)-p), Copy(MStr, p+1, Length(NStr)-p))
end
end;
function TravelTree(Root: TTree): string;
begin
if Root=nil then
Result:=''
else
Result:=Root^.c+TravelTree(Root^.LChild)+TravelTree(Root^.RChild)
end;
begin
Root:=MakeTree(NStr, MStr);
Result:=TravelTree(Root)
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
Edit3.Text:=GetPStr(Edit1.Text, Edit2.Text)
end;

end.
 
数据结构的考试题就是这么考的,我比较笨,每次总是把树画出来。
但笔试时好像是画好的一棵树,让你写出前中后序排列
 
答案是B
这是基本的数据结构问题,回的方法很简单
就是根据二叉树的遍历方法画出对应的二叉树
而这个二叉数画出来就是:
A
/ /
B C
/ / /
D E F
/ / /
G H I
/
J
有中序DB 和后序DG
确定D 是最左子 B是D的父节点
再看B 发现后序是DGJHEB 中序为DBGEHJ 以B结束的后序是GJHE正好也是以B开头的GEHJ
就确定GEHJ是B的子树 而且是右子树 (GJHE GEHJ)
中序DBGEHJACIF 那么就可以确定A 是B的父节点了 B是A的左子树
再看A 中序AC 后序CA
确认 C是A 的右子树
在看 (GJHE GEHJ) 再看(CIF IFC)
依次类推 就是把其划分为几个小段 对小段分析后再划分更小的段
就可以得到一个二叉树了

9
依次类推
 
谢谢各位!
 
后退
顶部