pascal 递归方法建立一个二叉树,完成如下任务:计算该二叉树的叶子结点数.求该二叉树的深度和宽度

论坛 期权论坛 期权     
chouxiaomaomi   2018-4-26 13:54   6653   2
3.      递归方法建立一个二叉树,完成如下任务:

(1)       计算该二叉树的叶子结点数。
(2) 求该二叉树的深度和宽度

样例,输入:
ABC##D##E#FG###
输出:
3
4  3

分享到 :
0 人收藏

2 个回复

倒序浏览
2#
BGHnnb  2级吧友 | 2018-4-30 01:58:59 发帖IP地址来自
输入理解:按先序遍历排列,#表示空
思路算法;模拟,同时不断更新深度和宽度,如果某一个节点没有左右孩子节点,那么他就是一个子节点,具体详见程序
本程序关键变量含义:
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.
经测试,本程序可以通过样例数据
若还是不理解,可以尝试数据跟踪进行调试
若还是不理解,欢迎追问。
若觉得好,请采纳!
3#
发动吧命运之骰  3级会员 | 2018-4-30 01:59:00 发帖IP地址来自
不懂输入格式
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

积分:
帖子:
精华:
期权论坛 期权论坛
发布
内容

下载期权论坛手机APP