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

零、前言

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

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

---

2、二叉树简介

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

---

3、二分搜索树简介

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

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

---

一、准备工作

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

[ 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);

---

二、最值操作：

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

1.寻找最小值

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

---

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

---

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.删除最大值

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

/**
 * 从二分搜索树中删除最大值所在节点
 *
 * @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);

    }

---

四、二叉树的遍历：

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

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

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

/**
 * 二分搜索树的前序遍历（用户使用）
 */
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-------------一层一层的遍历完了，是不是很神奇

/**
 * 二分搜索树的层序遍历，使用队列实现
 */
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走了，要找到继承人：这里用后继节点,将它右侧的树中的最小节点当做继承人

//找后继节点
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();
    }
}

---

后记：捷文规范

本系列后续更新链接合集：(动态更新)

看得见的数据结构Android版之开篇前言
看得见的数据结构Android版之数组表(数据结构篇)
看得见的数据结构Android版之数组表(视图篇)
看得见的数据结构Android版之单链表篇
看得见的数据结构Android版之双链表篇
看得见的数据结构Android版之栈篇
看得见的数据结构Android版之队列篇
看得见的数据结构Android版之二分搜索树篇
更多数据结构---以后再说吧

2.本文成长记录及勘误表

项目源码	日期	备注
V0.1--github	2018-11-25	看得见的数据结构Android版之二分搜索树结构的实现

3.更多关于我

笔名	QQ	微信	爱好
张风捷特烈	1981462002	zdl1994328	语言
我的github	我的简书	我的掘金	个人网站

4.声明

1----本文由张风捷特烈原创,转载请注明
2----欢迎广大编程爱好者共同交流
3----个人能力有限，如有不正之处欢迎大家批评指证，必定虚心改正
4----看到这里，我在此感谢你的喜欢与支持

---