零、前言
1.个人感觉这个二叉搜索树实现的还是很不错的，基本操作都涵盖了
2.在Activity中对view设置监听函数，可以动态传入数据，只要可比较，都可以生成二分搜索树 3.二分搜索树的价值：搜索、添加、删除、更新速度快,最佳状态复杂度logn，但极端情况下会退化成单链表 4.本例操作演示源码：
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> { 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 getMinNode(Node 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 getMaxNode(Node 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 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(Listels) { orderPerNode(root, els);}/** * 二分搜索树的中序遍历（用户使用） */public void orderIn(List els) { orderNodeIn(root, els);}/** * 二分搜索树的后序遍历（用户使用） */public void orderPost(List els) { orderNodePost(root, els);}/** * 前序遍历以target为根的二分搜索树 * * @param target 目标树根节点 */private void orderPerNode(Node target, List 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 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 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( Listels) { Queue 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 >.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 >.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(); }}复制代码 后记：捷文规范
本系列后续更新链接合集：(动态更新)
更多数据结构---以后再说吧
2.本文成长记录及勘误表
| 日期 | 备注 | |
|---|---|---|
| 2018-11-25 |
3.更多关于我
| 笔名 | 微信 | 爱好 | |
|---|---|---|---|
| 张风捷特烈 | 1981462002 | zdl1994328 | 语言 |
4.声明
1----本文由张风捷特烈原创,转载请注明
2----欢迎广大编程爱好者共同交流 3----个人能力有限，如有不正之处欢迎大家批评指证，必定虚心改正 4----看到这里，我在此感谢你的喜欢与支持