输入理解:按先序遍历排列,#表示空
思路算法;模拟,同时不断更新深度和宽度,如果某一个节点没有左右孩子节点,那么他就是一个子节点,具体详见程序
本程序关键变量含义:
k表示当前的层数,t表示当前节点的父亲节点的编号,x=1表示这是左孩子节点,x=2表示这是右孩子节点
n表示节点个数,因为n随时变动,所以设置一个nn表示这个节点的编号
p表示当前正在扫描s的第p个字符
a[n]表示第n个节点的编号(基本可以无视,因为a[n]=n)
c[k]表示第k层节点的个数(与宽度有关)
b[t,1]表示第t个节点的左孩子节点的编号,b[t,2]表示第t个节点的右孩子节点的编号
maxh表示最大的深度,maxw表示最大的宽度,及题目中的该二叉树的深度和宽度
参考程序:var
a,c:array[0..100000] of longint;
b:array[0..100000,1..2] of longint;
p,n,i,ans,maxw,maxh:longint;
s:ansistring;
procedure init(k,t,x:longint);
var
nn:longint;
begin
p:=p+1;//扫描下一个字符
if s[p]='#' then exit else//如果是#,那么就回到上一层
begin
n:=n+1;//节点数加一
a[n]:=n;
b[t,x]:=n;//父亲节点的子节点编号进行统计
c[k]:=c[k]+1;//当前高度节点的个数+1,即k高度的宽度+1
if c[k]>maxw then maxw:=c[k];
if k>maxh then maxh:=k;//刷新数的深度和高度
nn:=n;//保存当前节点的编号,避免n的变动引起误差
init(k+1,nn,1);//递归到左孩子节点
init(k+1,nn,2);//递归到右孩子节点
end;
end;
begin
readln(s);
init(1,0,1);//为了方便起见,设置1号节点为0号节点的左孩子节点,对结果无影响
for i:=1 to n do
if (b[i,1]=0) and (b[i,2]=0) then ans:=ans+1;//扫描,如果左孩子和右孩子节点都不存在(即=0),那么子节点个数+1
writeln(ans);
writeln(maxh,' ',maxw);//输出结果
end.
经测试,本程序可以通过样例数据
若还是不理解,可以尝试数据跟踪进行调试
若还是不理解,欢迎追问。
若觉得好,请采纳! |