统计
  • 建站日期:2021-03-10
  • 文章总数:699 篇
  • 评论总数:733 条
  • 分类总数:10 个
  • 最后更新:12月4日
文章 精密算法

JAVA 蓝桥杯 国赛 第六届 B组 试题 C:显示二叉树

程序员阿鑫
首页 精密算法 正文

排序二叉树的特征是:
某个节点的左子树的所有节点值都不大于本节点值。
某个节点的右子树的所有节点值都不小于本节点值。

为了能形象地观察二叉树的建立过程,小明写了一段程序来显示出二叉树的结构来。

class BiTree
{
    private int v;
    private BiTree l;
    private BiTree r;

    public BiTree(int v){
        this.v = v;
    }

    public void add(BiTree the){
        if(the.v < v){
            if(l==null) l = the;
            else l.add(the);
        }
        else{
            if(r==null) r = the;
            else r.add(the);
        }
    }

    public int getHeight(){
        int h = 2;
        int hl = l==null? 0 : l.getHeight();
        int hr = r==null? 0 : r.getHeight();
        return h + Math.max(hl,hr);
    }

    public int getWidth(){
        int w = (""+v).length();
        if(l!=null) w += l.getWidth();
        if(r!=null) w += r.getWidth();
        return w;
    }

    public void show(){
        char[][] buf = new char[getHeight()][getWidth()];
        printInBuf(buf, 0, 0);
        showBuf(buf);
    }

    private void showBuf(char[][] x){
        for(int i=0; i<x.length; i++){
            for(int j=0; j<x[i].length; j++)
                System.out.print(x[i][j]==0? ' ':x[i][j]);
            System.out.println();
        }
    }

    private void printInBuf(char[][] buf, int x, int y){
        String sv = "" + v;

        int p1 = l==null? x : l.getRootPos(x);
        int p2 = getRootPos(x);
        int p3 = r==null? p2 : r.getRootPos(p2+sv.length());

        buf[y][p2] = '|';
        for(int i=p1; i<=p3; i++) buf[y+1][i]='-';
        for(int i=0; i<sv.length(); i++) ________________________________;  //填空位置
        if(p1<p2) buf[y+1][p1] = '/';
        if(p3>p2) buf[y+1][p3] = '';

        if(l!=null) l.printInBuf(buf,x,y+2);
        if(r!=null) r.printInBuf(buf,p2+sv.length(),y+2);
    }

    private int getRootPos(int x){
        return l==null? x : x + l.getWidth();
    }
}

public class Main
{
    public static void main(String[] args)
    {        
        BiTree tree = new BiTree(500);
        tree.add(new BiTree(200));
        tree.add(new BiTree(509));
        tree.add(new BiTree(100));
        tree.add(new BiTree(250));
        tree.add(new BiTree(507));
        tree.add(new BiTree(600));
        tree.add(new BiTree(650));
        tree.add(new BiTree(450));
        tree.add(new BiTree(510));
        tree.add(new BiTree(440));
        tree.add(new BiTree(220));        
        tree.show();        
    }
}

对于上边的测试数据,应该显示出:

                  |
   /--------------500---
   |                    |
/--200---           /--509---
|        |           |        |
100   /--250---     507   /--600
      |        |           |     |
      220   /--450         510   650
            |
            440

(如有对齐问题,请参考【图1.png】)

请分析程序逻辑,填写划线部分缺失的代码。

注意,只填写缺少的部分,不要填写已有的代码或符号,也不要加任何说明文字。


JAVA蓝桥杯国赛第六届B组试题C:显示二叉树
-程序员阿鑫-带你一起秃头!
-第1
张图片

// 先把要填代码的那行注释,运行一下,根据结果就知道buf第一个索引是y+1,并且是要将sv这个字符串填到buf中,然后第二个呢,试出来的哈哈哈
buf[y + 1][p2+i] = sv.charAt(i);

以上是《JAVA 蓝桥杯 国赛 第六届 B组 试题 C:显示二叉树》的全部内容,

感谢您对程序员阿鑫博客的支持!

 

版权说明
文章采用: 《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权。
版权声明:未标注转载均为本站原创,转载时请以链接形式注明文章出处。如有侵权、不妥之处,请联系站长删除。敬请谅解!

-- 展开阅读全文 --
这篇文章最后更新于2020-12-3,已超过 1 年没有更新,如果文章内容或图片资源失效,请留言反馈,我们会及时处理,谢谢!
【Y-OS】Win7 SP1 x86&x64 纯净旗舰版v201903(带驱动)
« 上一篇
JAVA 蓝桥杯 国赛 第六届 B组 试题 B: 五星填数
下一篇 »
为了防止灌水评论,登录后即可评论!
注册登录

HI ! 请登录
注册会员,享受下载全站资源特权。
登陆 注册
上号,带你一起秃头!

IP地址

热门文章

1
抖音无限礼物模拟小工具分享
2
QQ假红包引流QQ群教程及代码
4
卡QQ永久大会员方法

最新文章

标签