专栏首页Android知识点总结D12-Android自定义控件之--二分搜索树

D12-Android自定义控件之--二分搜索树

Android自定义控件和二分搜索树貌似八竿子打不着啊,最近在看数据结构,感觉还好,但是就是有点枯燥 咱也是会玩安卓的人,搞一个View模拟一下二分搜索树呗,寓学于乐。 绘图部分使用我的LogicCanvas库,使用详见Github: 当然你也可以使用安卓原生的canvas绘制,这都不是重点,思路最重要。 本项目源码在此,点击查看

功能: 1.将数据以二分搜索树的树状结构展现 2.数据添加操作,此处上滑添加随机元素 3.数据移除操作,此处下滑移除随机元素 4.不止支持数字,也支持泛型(T extends Comparable<T>)

效果:

二分搜索字符串.png

数字二叉树.png

TreeView

1.成员变量
    /**
     * 数据
     */
    private List<T> mData = new ArrayList<>();
    /**
     * 根节点
     */
    private Node root = new Node(null, v2(0, 0));

    /**
     * 绘画者
     */
    private Painter mPainter;

    /**
     * 度量标尺=网格宽度=小球直径 也决定文字大小、连线长度
     */
    private int STEP = 50;

2.先看一下节点类

比起常规的二分搜索树,为了方便绘制,增加pos变量,记录当前节点坐标 有一个很头疼的问题就是如果节点距离都相同,那么第三层开始就会出现点盖住点的情况 所以打算维护一个节点的当前深度来让深层的连线变短,为变相获取当前节点的深度,维护father变量

  /////////////////////////////////Node节点类
    private class Node {
        public T el;
        public Node right;
        public Node left;

        //为了确定节点的位置,增加了pos变量:即点位
        public Pos pos;
        //为了确定节点所在的层级来决定每层现场,增加了father变量
        public Node father;

        /**
         * 构造函数
         *
         * @param left  左子
         * @param right 右子
         * @param el    储存的数据元素
         */
        public Node(Node left, Node right, T el, Pos pos) {
            this.el = el;
            this.left = left;
            this.right = right;
            this.pos = pos.dotC(STEP);
        }

        public Node(T el, Pos pos) {
            this(null, null, el, pos);
        }

        /**
         * 获取当前节点所在层数
         *
         * @return 当前节点所在层数
         */
        public int getDeep() {
            int deep = 0;
            Node node = this;
            while (node.father != null) {
                node = node.father;
                deep++;
            }
            return deep;
        }

        /**
         * 树的类型
         *
         * @return 树的类型
         */
        public NodeType getType() {
            if (this.right == null) {
                if (this.left == null) {
                    return NodeType.LEAF;
                } else {
                    return NodeType.RIGHT_NULL;
                }
            }
            if (this.left == null) {
                return NodeType.LEFT_NULL;
            } else {
                return NodeType.FULL;
            }
        }
    }

    /**
     * 节点类型
     */
    enum NodeType {
        FULL,//左右非空
        LEAF,//左右皆空
        RIGHT_NULL,//右空左非空
        LEFT_NULL;//左空右非空
    }

3.添加节点的方法

float len = STEP * 5 / ((target.getDeep() + 1));是根据节点深度控制与子节点的连线长度 这个计算方法也许不是太好,如果你能给出更好的方式,欢迎讨论

    /**
     * 返回插入新节点后的二分搜索树的根
     *
     * @param target 目标节点
     * @param el     插入元素
     * @return 插入新节点后的二分搜索树的根
     */
    private Node addNode(Node target, T el) {
        if (target == null) {
            return new Node(null, null, el, v2(0, 0));
        }
        //根据节点深度控制与子节点的连线长度
        float len = STEP * 5 / ((target.getDeep() + 1));
        
        if (el.compareTo(target.el) < 0) {
            target.left = addNode(target.left, el);
            //维护目标节点左节点坐标,减去len
            target.left.pos = target.pos.minus(v2(len, len));
            //维护父亲节点
            target.left.father = target;
        } else if (el.compareTo(target.el) > 0) {
            target.right = addNode(target.right, el);
            //维护目标节点左节点坐标,X加len,Y减去len,
            target.right.pos = target.pos.add(v2(len, -len));
            //维护父亲节点
            target.right.father = target;
        }
        return target;
    }
4.删除节点
/**
     * 删除掉以target为根的二分搜索树中值为e的节点, 递归算法 返回删除节点后新的二分搜索树的根
     *
     * @param target 
     * @param el
     * @return
     */
    private Node removeNode(Node target, T el) {
        if (target == null) {
            return null;
        }

        if (el.compareTo(target.el) < 0) {
            target.left = removeNode(target.left, el);
        } else if (el.compareTo(target.el) > 0) {
            target.right = removeNode(target.right, el);
            return target;
        } else {//相等时
            switch (target.getType()) {
                case LEFT_NULL://左残--
                case LEAF:
                    Node rightNode = target.right;
                    target.right = null;
                    return rightNode;
                case RIGHT_NULL:
                    Node leftNode = target.left;
                    target.left = null;
                    return leftNode;
                case FULL:
                    //找后继节点
                    Node successor = getMinNode(target.right);
                    successor.right = removeMinNode(target.right);
                    successor.left = target.left;
                    target.left = target.right = null;
                    return successor;
            }
        }
        return target;
    }

4.绘制
    @Override
    protected void onDraw(Canvas canvas) {
        super.onDraw(canvas);
        //绘制网格
        CanvasUtils.drawGrid(getContext(), STEP, canvas);
        //获取绘图者
        mPainter = PainterEnum.INSTANCE.getInstance(canvas);
        //将数据添加入节点
        if (mData != null) {
            for (T data : mData) {
                root.el = mData.get(0);
                root = addNode(root, data);
            }
            //绘制以node为根的所有节点
            drawNode(root);
        }
    }

这里使用后续遍历时绘制

/**
     * 绘制以node为根的所有节点
     *
     * @param node
     */
    public void drawNode(Node node) {

        if (node == null) {
            return;
        }
        drawNode(node.left);
        drawNode(node.right);

        //坐标系取X中间
        Pos theCoo = v2(STEP * (mWinSize.x / STEP / 2 + 1), STEP / 2);
        //sa绘制弧形命令--360度,直径STEP,偏移node.pos,颜色黑色,坐标系原点mcoo
        mPainter.draw(
                sa.ang(360).r(STEP / 2)
                        .p(node.pos).fs(Color.BLACK).coo(theCoo));

        //绘制文字--根据节点位置确定文字位置
        Pos txtPos = node.pos.add(STEP * (mWinSize.x / STEP / 2 + 1), -STEP / 2 - STEP / 5);
        //st绘制文字命令
        mPainter.drawText(
                st.str(node.el + "").size(STEP / 3 * 2).fs(Color.WHITE)
                        .p(txtPos.refY()));

        //如果有右节点,画右线
        if (node.right != null) {
            //node.pos是节点的中心坐标,这里做了一些偏移,不会压到字
            Pos startPos = node.pos.add(STEP / 4, -STEP / 4);
            //右子的坐标
            Pos endPos = node.right.pos.add(-STEP / 4, STEP / 4);
            //sl绘制直线命令
            mPainter.draw(
                    sl.ps(startPos, endPos)
                            .coo(theCoo).b(3).ss(Color.BLACK));
        }

        //如果有左节点,画左线--同上
        if (node.left != null) {
            mPainter.draw(
                    sl.ps(node.pos.add(-STEP / 4, -STEP / 4), node.left.pos.add(STEP / 4, STEP / 4))
                            .coo(theCoo).b(3).ss(Color.BLACK));
        }

    }

暴漏的方法

    /**
     * 添加节点
     *
     * @param el 节点元素
     */
    public void add(T el) {
        mData.add(el);
    }

    /**
     * 移除节点
     *
     * @param el 节点元素
     */
    public void remove(T el) {
        mData.remove(el);
        root = removeNode(root, el);
    }

Activity中测试:

静态显示测试
val treeView = TreeView<Int>(this)
val data = ArrayList<Int>()
data.add(200)
data.add(265)
data.add(855)
data.add(67)
data.add(15)
data.add(48)
data.add(12)
data.add(585)
data.add(45)
treeView.setData(data)
动态添加、删除测试
treeView.setOnEventListener(object : BaseView.OnEventListener {
    override fun down(pos: Pos) {
    }
    override fun up(pos: Pos, speed: BaseView.MoveSpeed, orientation: BaseView.Orientation) {
        when (orientation) {
            BaseView.Orientation.TOP -> {
                val rangeInt = ZRandom.rangeInt(2, 400)
                treeView.add(rangeInt)
                treeView.invalidate()
            }
            BaseView.Orientation.BOTTOM -> {
                val el = treeView.data.get(ZRandom.rangeInt(1, treeView.data.size - 1))
                treeView.remove(el)
                treeView.invalidate()
            }
        }
    }
    override fun move(pos: Pos, s: Double, dy: Float, dx: Float, dir: Double, orientation: BaseView.Orientation) {
    }
})

字符串测试
        val treeView = TreeView<String>(this)
        val data = ArrayList<String>()
        data.add("f")
        data.add("c")
        data.add("a")
        data.add("g")
        data.add("z")
        data.add("d")
        data.add("o")
        data.add("w")
        data.add("g")
        data.add("q")
        treeView.setData(data)
        val treeView = TreeView<String>(this)
        val data = ArrayList<String>()
        data.add("赵")
        data.add("钱")
        data.add("孙")
        data.add("李")
        data.add("周")
        data.add("吴")
        data.add("郑")
        data.add("王")
        data.add("冯")
        data.add("陈")
        data.add("楚")
        data.add("卫")
        treeView.setData(data)

二分搜索字符串.png

就酱紫 本项目源码在此,点击查看

后记、

1.声明:

[1]本文由张风捷特烈原创,转载请注明 [2]欢迎广大编程爱好者共同交流 [3]个人能力有限,如有不正之处欢迎大家批评指证,必定虚心改正 [4]你的喜欢与支持将是我最大的动力

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 02--图解数据结构之单链表实现集合

    张风捷特烈
  • 2-3树与红黑树

    张风捷特烈
  • 看得见的数据结构Android版之二分搜索树篇

    张风捷特烈
  • FPGA开篇

    接下来很长一段时间都将进行FPGA的表述,中间也不时的发一些设计硬件电路和嵌入式开发的讲解,如果对FPGA也还不知道是什么东西的朋友可以自己上网了解,反正一个字...

    狂人V
  • 谁能告诉我如何通过Jenkins完成分布式环境搭建并执行自动化脚本

    今天我们接着昨天的内容,看一看如何完成Jenkins分布式环境的搭建和使用,因为我之前也是自己一个人摸索的,如果有不对的地方,请各位看官私信指出。

    菜鸟小白的学习分享
  • (2)MongoDB副本集自动故障转移原理(含客户端)

    前文我们搭建MongoDB三成员副本集,了解集群基本特性,今天我们围绕下图聊一聊背后的细节。

    小码甲
  • 开发者自述:我如何用云函数快速搞定「模板消息推送功能」

    知晓君
  • Elastic:Elasticsearch 的分片管理策略

    在本教程中,我们介绍了一些与 Elasticsearch 中的分片管理相关的常见问题,其解决方案以及一些最佳实践。 在某些用例中,我们结合了特殊的技巧来完成任务...

    腾讯云ES团队
  • 高可用 - 简述

    高可用性 描述了一个周期内的功能连续可用的绝对程度,可表示为正常运行时间和停机时间之间的关系,如下公式:

    zhangyunfeiVir
  • 一起学爬虫——使用Beautiful S

    要想学好爬虫,必须把基础打扎实,之前发布了两篇文章,分别是使用XPATH和requests爬取网页,今天的文章是学习Beautiful Soup并通过一个例子来...

    py3study

扫码关注云+社区

领取腾讯云代金券