看得见的数据结构Android版之二分搜索树篇
2018-11-25 本文已影响8人
e4e52c116681
零、前言
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();
}
}
后记：捷文规范
本系列后续更新链接合集：(动态更新)
看得见的数据结构Android版之开篇前言
看得见的数据结构Android版之数组表(数据结构篇)
看得见的数据结构Android版之数组表(视图篇)
看得见的数据结构Android版之单链表篇
看得见的数据结构Android版之双链表篇
看得见的数据结构Android版之栈篇
看得见的数据结构Android版之队列篇
看得见的数据结构Android版之二分搜索树篇
更多数据结构---以后再说吧
2.本文成长记录及勘误表
| 项目源码 | 日期 | 备注 |
|---|---|---|
| V0.1--github | 2018-11-25 | 看得见的数据结构Android版之二分搜索树结构的实现 |
3.更多关于我
| 笔名 | 微信 | 爱好 | |
|---|---|---|---|
| 张风捷特烈 | 1981462002 | zdl1994328 | 语言 |
| 我的github | 我的简书 | 我的掘金 | 个人网站 |
4.声明
1----本文由张风捷特烈原创,转载请注明
2----欢迎广大编程爱好者共同交流
3----个人能力有限，如有不正之处欢迎大家批评指证，必定虚心改正
4----看到这里，我在此感谢你的喜欢与支持
icon_wx_200.png
