看得见的数据结构Android版之二分搜索树篇

零、前言

1.个人感觉这个二叉搜索树实现的还是很不错的,基本操作都涵盖了 2.在Activity中对view设置监听函数,可以动态传入数据,只要可比较,都可以生成二分搜索树 3.二分搜索树的价值:搜索、添加、删除、更新速度快,最佳状态复杂度logn,但极端情况下会退化成单链表 4.本例操作演示源码:希望你可以和我在Github一同见证:DS4Android的诞生与成长,欢迎star

1.留图镇楼:二分搜索树的最终实现的操作效果:

二分搜索树操作合集.gif


2、二叉树简介
二叉树特性
1.一个二叉树一定有且仅有一个根节点
2.一个二叉树除了数据之外,还有[左子]、[右子]的引用,节点本身称为[父]
3.树形:
    |---残树:
        |---左残:[左子]为空,[右子]非空
        |---右残:[右子]为空,[左子]非空
        |---叶:[右子]为空,[左子]为空
    |---满树:[左子]、[右子]非空
4.二叉系:
    |---二叉系是天然存在的无限全空二叉树
    |---节点的二叉系坐标:(x,y)  x:该层的第几个元素 y:该层层数
5.二叉树的分类:
    |---二分搜索树:
    |---平衡二叉树:最大树深-最小树深<=1
        |---完全二叉树:按二叉系坐标排放元素
            |---堆
        |---线段树

二叉树树形.png


3、二分搜索树简介

二分搜索树是一种特殊的二叉树形的数据结构 存储的数据必须具有可比较性

特性:对于每个节点      
1.[父]的值都要大于[左子]的值。
2.[父]的值都要小于[右子]的值。

二分搜索树.png


一、准备工作

1.创建类
/**
 * 作者:张风捷特烈
 * 时间:2018/10/7 0007:7:36
 * 邮箱:1981462002@qq.com
 * 说明:
 */
public class BinarySearchTree<T extends Comparable<T>> {
    private Node root;//根节点
    private int size;//节点个数

    public Node getRoot() {//----!为方便视图绘制:暴露此方法
        return root;
    }

    /**
     * 获取节点个数
     *
     * @return 节点个数
     */
    public int size() {
        return size;
    }

    /**
     * 二分搜索树是否为空
     *
     * @return 是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }
}
2.节点类的设计
/**
 * 节点类----!为方便视图绘制---private 改为 public
 */
public class Node {

    public T el;//储存的数据元素
    public Node left;//左子
    public Node right;//右子

    public int deep;//!为方便视图绘制---增加节点树深


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

    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;
        }
    }
}

二、节点(Node)的添加操作

感觉就像顺藤插瓜,一个瓜,两个叉,比较[待插入瓜]和[当前瓜]的个头大小 大了放右边,小了放左边,直到摸不到瓜了,就把待插入的插上。

1.指定节点,按二分搜索树添加元素
/**
 * 添加节点
 *
 * @param el 节点元素
 */
public void add(T el) {
    root = addNode(root, el);
}

/**
 * 返回插入新节点后的二分搜索树的根
 *
 * @param target 目标节点
 * @param el     插入元素
 * @return 插入新节点后的二分搜索树的根
 */
private Node addNode(Node target, T el) {
    if (target == null) {
        size++;
        return new Node(null, null, el);
    }
    if (el.compareTo(target.el) <= 0) {
        target.left = addNode(target.left, el);
        target.left.deep = target.deep + 1;//!为方便视图绘制---维护deep
    } else if (el.compareTo(target.el) > 0) {
        target.right = addNode(target.right, el);
        target.right.deep = target.deep + 1;//!为方便视图绘制---维护deep
    }
    return target;
}
2.添加测试:6, 2, 8, 1, 4, 3

二分搜索树添加.gif

[ 6, 2, 8, 1, 4, 3 ]

插入的形象演示:其中表示null

    6             6                6              6                   6                  6
 /    \ --->   /    \    --->   /   \   --->   /     \    --->     /     \   --->     /     \
。     。     2       。       2     8         2      8            2      8           2      8
           /    \           /  \  /  \      /  \    /  \        /  \    /  \       /  \    /  \
          。     。        。   。。   。   1    。 。   。      1   4  。   。     1   4   。   。
                                          / \                 / \  / \          / \  / \
                                         。  。              。  。。  。        。 。。  3         
3.用栈来分析插入元素5时的递归:
searchTree.add(5);

二叉树插入递归分析.png

插入5时.png


二、最值操作:

这真是正宗的顺藤摸瓜,想找最小值,一直往左摸,想找最大值,一直往右摸。

1.寻找最小值
/**
 * 获取最小值:暴露的方法
 *
 * @return 树的最大元素
 */
public E getMin() {
    return getMinNode(root).el;
}
 
/**
 * 获取最小值所在的节点 :内部方法
 *
 * @param node 目标节点
 * @return 最小值节点
 */
private Node<E> getMinNode(Node<E> node) {
    //左子不为空就一直拿左子,直到左子为空
    if (node.right == null) {
        return node;
    }
    node = getMinNode(node.left);
    return node;
}

最小值.png

查找最小值递归.png


2.删除最小值:

node.left == null说明一直再往左找,整个递归过程中node.left = removeMinNode(node.left); 从根节点开始,它们都在等待左侧值,直到发现到最左边了,便将最小值节点的右侧节点返回出去 这时前面等待的人接到了最小值的右侧,然后最小值被从树上移除了。

/**
 * 从二分搜索树中删除最大值所在节点
 *
 * @return 删除的元素
 */
public E removeMin() {
    E ret = getMin();
    root = removeMinNode(root);
    return ret;
}

/**
 * 删除掉以node为根的二分搜索树中的最小节点 返回删除节点后新的二分搜索树
 *
 * @param node 目标节点
 * @return 删除节点后新的二分搜索树的根
 */
private Node removeMinNode(Node node) {
    if (node.left == null) {
        Node rightNode = node.right;
        node.right = null;
        return rightNode;
    }
    
    node.left = removeMinNode(node.left);
    return node;
}

删除最小值.gif

移除最小值递归分析.png


3.寻找最大值

原理基本一致,就不画图了。

/**
 * 获取最大值:暴露的方法
 *
 * @return 树的最大元素
 */
public E getMax() {
    return getMaxNode(root).el;
}

/**
 * 获取最大值所在的节点:内部方法
 *
 * @param node 目标节点
 * @return 最小值节点
 */
private Node<E> getMaxNode(Node<E> node) {
    //右子不为空就一直拿右子,直到右子为空
    return node.right == null ? node : getMaxNode(node.right);
}
4.删除最大值

原理基本一致,就不画图了。

最大值操作.gif

/**
 * 从二分搜索树中删除最大值所在节点
 *
 * @return 删除的元素
 */
public E removeMax() {
    E ret = getMax();
    root = removeMaxNode(root);
    return ret;
}

/**
 * 删除掉以node为根的二分搜索树中的最小节点 返回删除节点后新的二分搜索树的根
 *
 * @param node 目标节点
 * @return 删除节点后新的二分搜索树的根
 */
private Node removeMinNode(Node node) {
    if (node.left == null) {
        Node rightNode = node.right;
        node.right = null;
        return rightNode;
    }
    node.left = removeMinNode(node.left);
    return node;
}

三、查找是否包含元素

想一下一群西瓜按二分搜索树排列,怎么看是否包含10kg的西瓜? 和root西瓜比较:小了就往往左走,因为右边的都比root大,一下就排除一半,很爽有没有 让后继续比较,直到最后也没有,那就不包含。

    /**
     * 否存在el元素
     * @param el 元素
     * @return 是否存在
     */
    public boolean contains(E el) {
        return contains(el, root);
    }

    /**
     * 以root为根节点的二叉树是否存在el元素
     *
     * @param el   待测定元素
     * @param node 目标节点
     * @return 是否存在el元素
     */
    private boolean contains(E el, Node<E> node) {
        if (node == null) {
            return false;
        }

        if (el.compareTo(node.el) == 0) {
            return true;
        }

        boolean isSmallThan = el.compareTo(node.el) < 0;
        //如果小于,向左侧查找
        return contains(el, isSmallThan ? node.left : node.right);

    }

包含方法递归分析.png

包含.png


四、二叉树的遍历:

层序遍历、前序遍历、中序遍历、后序遍历,听起来挺吓人其实就是摸瓜的时候什么时候记录一下 这里是用List装一下,方便获取结果,你也可以用打印来看,不过感觉有点low

1.前序遍历、中序遍历、后序遍历

代码基本一致,就是在遍历左右子时,放到篮子里的时机不同,分为了前、中、后 前序遍历:父-->左-->右(如:6父,2左,2为父而左1,1非父,2右4,4为父而左3,以此循之) 中序遍历:左-->父-->右 后序遍历:左-->右-->父

遍历.png

/**
 * 二分搜索树的前序遍历(用户使用)
 */
public void orderPer(List<T> els) {
    orderPerNode(root, els);
}
/**
 * 二分搜索树的中序遍历(用户使用)
 */
public void orderIn(List<T> els) {
    orderNodeIn(root, els);
}
/**
 * 二分搜索树的后序遍历(用户使用)
 */
public void orderPost(List<T> els) {
    orderNodePost(root, els);
}

/**
 * 前序遍历以target为根的二分搜索树
 *
 * @param target 目标树根节点
 */
private void orderPerNode(Node target, List<T> els) {
    if (target == null) {
        return;
    }
    els.add(target.el);
    orderPerNode(target.left, els);
    orderPerNode(target.right, els);
}

/**
 * 中序遍历以target为根的二分搜索树
 *
 * @param target 目标树根节点
 */
private void orderNodeIn(Node target, List<T> els) {
    if (target == null) {
        return;
    }
    orderNodeIn(target.left, els);
    els.add(target.el);
    orderNodeIn(target.right, els);
}
/**
 * 后序遍历以target为根的二分搜索树
 *
 * @param target 目标树根节点
 */
private void orderNodePost(Node target, List<T> els) 
    if (target == null) {
        return;
    }
    orderNodePost(target.left, els);
    orderNodePost(target.right, els);
    els.add(target.el);
}
2.层序遍历(队列模拟):

感觉挺有意思的:还是用个栗子说明吧

6元素先入队,排在最前面,然后走了登个记(放在list里),把左右两个孩子2,8留下了,队列:8-->2    
然后2登个记(放在list里)走了,把它的孩子1,4放在队尾,这时候排队的是:4-->1-->8,集合里6,2  
然后8登个记(放在list里)走了,它没有孩子,这时候排队的是:4-->1,集合里6,2,8  
然后1登个记(放在list里)走了,它没有孩子,这时候排队的是:4,集合里6,2,8,1  
然后4登个记(放在list里)走了,把它的孩子3,5放在队尾,这时候排队的是:5-->3,集合里6,2,8,1,4    
都出队过后:6,2,8,1,4,3,5-------------一层一层的遍历完了,是不是很神奇

层序遍历.png

/**
 * 二分搜索树的层序遍历,使用队列实现
 */
public void orderLevel( List<T> els) {
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        Node cur = queue.remove();
        els.add(cur.el);
        //节点出队时将孩子入队
        if (cur.left != null) {
            queue.add(cur.left);
        }
        if (cur.right != null) {
            queue.add(cur.right);
        }
    }
}

五、二叉树的移除指定元素:
移除节点:首先类似包含操作,找一下与传入元素相同是的节点  
删除的最大难点在于对目标节点孩子的处理,按照树型可分为:
RIGHT_NULL:如果目标只有一个左子,可以按照删除最小值的思路  
LEFT_NULL:只有一个右子,可以按照删除最大值的思路  
LEAF:如果本身就是叶子节点,就不用考虑那么多了,爱怎么删怎么删  
FULL:如果左右都有孩子,你总得找个继承人接班吧,才能走..
1.看一下移除2时:

首先2走了,要找到继承人:这里用后继节点,将它右侧的树中的最小节点当做继承人

移除2.gif

//找后继节点
Node successor = getMinNode(target.right);
successor.right = removeMinNode(target.right);
successor.left = target.left;
target.left = target.right = null;
return successor;
2.移除的代码实现
/**
 * 移除节点
 *
 * @param el 节点元素
 */
public void remove(T el) {
    root = removeNode(root, el);
}
/**
 * 删除掉以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;
                size--;
                return rightNode;
            case RIGHT_NULL:
                Node leftNode = target.left;
                target.left = null;
                size--;
                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;
}

好了,二叉树的基本操作都讲了以遍,下面说说绘图的核心方法:

核心绘制方法:

核心绘制思路

/**
 * 绘制结构
 *
 * @param canvas
 */
private void dataView(Canvas canvas) {
    if (!mTreeBalls.isEmpty()) {
        canvas.save();
        canvas.translate(ROOT_X, ROOT_Y);
        BinarySearchTree<TreeNode<E>>.Node root = mTreeBalls.getRoot();
        canvas.drawCircle(0, 0, NODE_RADIUS, mPaint);
        canvas.drawText(root.el.data.toString(), 0, 10, mTxtPaint);
        drawNode(canvas, root);
        canvas.restore();
    }
}

private void drawNode(Canvas canvas, BinarySearchTree<TreeNode<E>>.Node node) {
    float thta = (float) ((60 - node.deep * 10) * Math.PI / 180);//父节点与子节点竖直方向夹角
    int lineLen = (int) (150 / ((node.deep + .5)));//线长
    float offsetX = (float) (NODE_RADIUS * Math.sin(thta));//将起点偏移圆心X,到圆上
    float offsetY = (float) (NODE_RADIUS * Math.cos(thta));//将起点偏移圆心X,到圆上
    
    //画布移动的X
    float translateOffsetX = (float) ((lineLen + 2 * NODE_RADIUS) * Math.sin(thta));
    //画布移动的Y
    float translateOffsetY = (float) ((lineLen + 2 * NODE_RADIUS) * Math.cos(thta));
    
    float moveX = (float) (lineLen * Math.sin(thta));//线移动的X
    float moveY = (float) (lineLen * Math.cos(thta));//线移动的Y
    if (node.right != null) {
        canvas.save();
        canvas.translate(translateOffsetX, translateOffsetY);//每次将画布移到右子的圆心
        canvas.drawCircle(0, 0, NODE_RADIUS, mPaint);//画圆
        mPath.reset();//画线
        mPath.moveTo(-offsetX, -offsetY);
        mPath.lineTo(-offsetX, -offsetY);
        mPath.rLineTo(-moveX, -moveY);
        canvas.drawPath(mPath, mPathPaint);
        canvas.drawText(node.right.el.data.toString(), 0, 10, mTxtPaint);//画字
        drawNode(canvas, node.right);
        canvas.restore();
    }
    if (node.left != null) {//同理
        canvas.save();
        canvas.translate(-translateOffsetX, translateOffsetY);
        mPath.reset();
        mPath.moveTo(offsetX, -offsetY);
        mPath.rLineTo(moveX, -moveY);
        canvas.drawPath(mPath, mPathPaint);
        canvas.drawCircle(0, 0, NODE_RADIUS, mPaint);
        canvas.drawText(node.left.el.data.toString(), 0, 10, mTxtPaint);
        drawNode(canvas, node.left);
        canvas.restore();
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Bingo的深度学习杂货店

Q112 Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path suc...

35670
来自专栏Vamei实验室

纸上谈兵: 树, 二叉树, 二叉搜索树

树的特征和定义 树(Tree)是元素的集合。我们先以比较直观的方式介绍树。下面的数据结构是一个树: ? 树有多个节点(node),用以储存元素。某些节点之间存在...

23170
来自专栏大史住在大前端

野生前端的数据结构基础练习(7)——二叉树

一棵树最上面的点称为根节点,如果一个节点下面连接多个节点,那么该节点称为父节点,下面的节点称为子节点,二叉树的每一个节点最多有2个子节点,一个节点子节点的个数称...

9220
来自专栏开发与安全

数据结构:线性表之链式存储结构

为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系,对数据ai,除了存储其自身的信息之外,还需存储一个指示其 直接后继的信息(即直接后继的存储位置)...

204100
来自专栏Java3y

二叉树就这么简单

一、二叉树就是这么简单 本文撇开一些非常苦涩、难以理解的概念来讲讲二叉树,仅入门观看(或复习)…. 首先,我们来讲讲什么是树: 树是一种非线性的数据结构,相对于...

54380
来自专栏前端迷

数据结构与前端开发(四)-树

二叉树拥有一个根节点,每个节点至多拥有两个子节点,分别为:左节点和右节点。树的最底部节点称之为叶节点,当一颗树的叶数量数量为满时,该树可以称之为满二叉树。

21030
来自专栏一名叫大蕉的程序员

大数据计数原理1+0=1这你都不会算(四)No.52

这是本坑的第四篇,之前已经说了关于 HashSet 、BitMap 、Bloom Filter 布隆过滤器了,本篇主要讲B-树。要是还不知道前面讲了啥的,可以点...

21570
来自专栏老马说编程

(32) 剖析日期和时间 / 计算机程序的思维逻辑

本节和下节,我们讨论在Java中如何进行日期和时间相关的操作。 日期和时间是一个比较复杂的概念,Java API中对它的支持不是特别好,有一个第三方的类库反而特...

217100
来自专栏WindCoder

链表实现栈的动态顺序存储实现—C语言

19620
来自专栏数据结构与算法

24:打印月历

24:打印月历 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 给定年月,打印当月的月历表。 输入输入为一行两个整数,...

38860

扫码关注云+社区

领取腾讯云代金券