Zero, preface,

1. Personally feel this binary search tree is very good, the basic operation is covered

2. Set the monitoring function on the Activity view, can dynamically pass data, as long as the comparison, can generate binary search tree 3. The value of binary search tree: search, add, delete, update fast, the best state complexity logn, but in extreme cases will degenerate into a single linked list 4. I hope you can and I at Github together to witness: the birth and growth of DS4Android, welcome to star

1. The operation effect of binary search tree:

2. Introduction to binary trees
2. In addition to data, a binary tree also has references to [left child] and [right child], and the node itself is called [parent] 3. Tree: | - remnants tree: | - left the residual: [left] son is empty, son [right] is not empty | - right residual: [right] son is empty, son [left] is not empty | - leaf: [right] son is empty, son [left] is empty | - full tree: [left], son [right] is not empty. Binary system: | - binary system is the natural existence of infinite binary tree empty | - node of the binary system coordinates (x, y) x: which one element of this layer of the y: the number 5. Binary tree classification: | - binary search trees: | - balanced binary tree, the tree deep - minimum tree deep < = 1 | - complete binary tree: according to the binary system of coordinates discharge element | - pile | - segment treeCopy the code

3. Introduction to binary search tree

Binary search tree is a special binary tree data structure

The stored data must be comparable

Property: For each node 1. The value of [parent] is greater than the value of [left child]. 2. The value of [parent] must be smaller than that of [right child].Copy the code

First, preparation

1. Create the class
/** * Author: Zhang Feng Jiete Lie * Time: 2018/10/70007:7:36 * Email: [email protected] * Description:  */ public class BinarySearchTree<T extends Comparable<T>> { private Node root; // Private int size; Public Node getRoot() {//----! For easy view drawing: expose this method return root; } public int size() {return size;} public int size() {return size; Public Boolean isEmpty() {return size == 0;} public Boolean isEmpty() {return size == 0; }}Copy the code
2. Design of node class
/** * Node class ----! Public */ public class Node {public T el; Public Node left; // Left child public Node right; Public int deep; / /! @param left @param right @param el @param left @param left @param left @param left @param left @param left @param left @param left @param left @param right @param el 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; }}}Copy the code

2. Add a Node

It feels like a straight vine with one melon and two forks, comparing the size of [to be inserted] and [current]

If it’s big, put it on the right, if it’s small, put it on the left, until you can’t touch the melon anymore.

1. Add elements to the binary search tree
/** * add node ** @param el node element */ public void add(T el) {root = addNode(root, el); } /** * return root of binary search tree after insertion ** @param target @param el insert element * @return root of binary search tree after insertion */ 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; / /! Else if (el.compareTo(target.el) > 0) {target.right = addNode(target.right, el); target.right.deep = target.deep + 1; / /! To facilitate view drawing -- maintain deep} return target; }Copy the code
2. Add tests:Six, two, eight, one, four, three

[6, 2, 8, 1, 4, 3]Copy the code

Insert image demo: where. According to null

6 6 6 6 / \ - > / \ - > / \ - > / \ - > / \ - > / \. . 2. 8, 8 2 2 2 2 8 / \ / \ \ / \ \ / \ \ / \ \. . . . . 1. . . 1. 4. . 1. 4. . / \ / \ / \ / \ / \. . . . . . . 3Copy the code
3. Analyze the inserted elements using the stack5Recursion of:
searchTree.add(5);
Copy the code

Two, the most value operation:

This is really authentic follow the trail, to find the minimum, always to the left, to find the maximum, always to the right.

1. Find the minimum
/** * getMinNode(root).el; /** * getMinNode(root).el; } /** * obtain the node where the minimum value is located: Internal method * * @param node target node * @return minimum node */ private node <E> getMinNode(node <E> node) (node.left == null) { return node; } node = getMinNode(node.left); return node; }Copy the code

2. Delete minimum value:

Left = removeMinNode(node.left) left = removeMinNode(node.left);

Starting at the root, they’re all waiting for the left, until they get to the left, and then they return the right side of the minimum node and then the person in front of them gets the right side of the minimum, and then the minimum is removed from the tree.

Public E removeMin() {E ret = getMin(); root = removeMinNode(root); return ret; } /** * Return the root of the new binary search tree ** @param node target node */ 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; }Copy the code

3. Look for the maximum

It’s basically the same principle, so I won’t draw it.

Public E getMax() {return getMaxNode(root).el; } /** * getMaxNode(node <E> node) {private node <E> getMaxNode(node <E> node) { Return node.right == null? Return node.right == null? node : getMaxNode(node.right); }Copy the code
4. Delete the maximum value

It’s basically the same principle, so I won’t draw it.

Public E removeMax() {E ret = getMax(); root = removeMaxNode(root); return ret; } /** * Return root of new binary search tree ** @param node target node */ return root of new binary search tree */ 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; }Copy the code

Third, to find whether to include elements

Consider a group of watermelons arranged by a binary search tree. How do you see if they contain 10kg of watermelons?

Compared with root watermelon: the small watermelon tends to go left, because the right side is bigger than root, once excluded half, very cool, then continue to compare, until the last no, that does not include.

Public Boolean contains(E el) {return contains(el, root); /** * contains(el, root); } /** * @param el () @param node () @param node () @return () @param node () */ 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); }Copy the code

Four, binary tree traversal:

Sequenced traversal, pre-sequenced traversal, in-sequenced traversal, post-sequenced traversal, it sounds scary but when do YOU record when you touch a melon

I’m using a List to get the results, or you can print it out, but it’s a little low

1. Pre-order traversal, in-order traversal, and post-order traversal

The code is basically the same, that is, when traversing the left and right children, the time to put into the basket is different, divided into front, middle, and back

Preorder traversal: father — > left – > right (such as: 6 father, 2 left, 2 for father and father left, 1, 1 a, 2, 4, 4 right left 3, for the father to follow) in sequence traversal: — — — — > > father left right after the sequence traversal: left – > right – > the father

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); } /** ** @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); } /** * @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); } /** * @param target */ private void orderNodePost(nodetarget, nodetarget, nodetarget) List<T> els) if (target == null) { return; } orderNodePost(target.left, els); orderNodePost(target.right, els); els.add(target.el); }Copy the code
2. Sequential traversal (queue simulation) :

Feel quite interesting: or use a chestnut to explain

6 elements first enter the queue, in the front, and then walk the log (put in the list), left the left and right two children 2,8, queue: 8-->2, then 2 enter the log (put in the list) go, put its children 1,4 on the end of the queue, this time the queue is: 4 -- -- > 1 > 8, 6, and 8 in the collection of an away (in the list), it had no children, this line is: 4 - > 1, in the collection of 6,2,8 then 1 an down (on) in the list in the left, it had no children, waiting in line at this time is: 4, set 6,2,8,1 and then 4 entries (put in the list) go, put its children 3,5 on the end of the line, this time the queue is: 5- >3, set 6,2,8,1,4, 4 out of the line: 6,2,8,1,4, 5------------- a layer of traversal finished, is not very magicCopy the code

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); }}}Copy the code
Remove element from binary tree
Remove node: First of all, similar to the include operation, find the node that is the same as the passed element, the biggest difficulty is to remove the target node child processing, according to the tree type can be divided into: RIGHT_NULL: if the target is only one left, according to you can delete the minimum LEFT_NULL: there is only one right child, according to you can delete the maximum LEAF: if itself is a LEAF node, need not consider so much, love how how to delete delete FULL: if left and right sides, all have children, You must find an heir before you leave..Copy the code
1. Look at removal2When:

First 2 goes, to find the heir: here we use the successor node, the smallest node in the tree to its right as the heir

Succeeded = getMinNode(target.right); successor.right = removeMinNode(target.right); successor.left = target.left; target.left = target.right = null; return successor;Copy the code
2. Code implementation for removal
Public void remove(T el) {root = removeNode(root, el); /** * remove node ** @param el element */ public void remove(T el) {root = removeNode(root, el); }Copy the code
/** * delete e from binary search tree; * * @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:// left remnant -- 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: // Find the successor Node succeeded = getMinNode(target.right); successor.right = removeMinNode(target.right); successor.left = target.left; target.left = target.right = null; return successor; } } return target; }Copy the code

Ok, the basic operations of binary trees have been covered, let’s talk about the core method of drawing:

Core drawing method:

/** * @param canvas */ private void dataView(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))); // Line length float offsetX = (float) (NODE_RADIUS * math.sin (thta)); // Float offsetY = (float) (NODE_RADIUS * math.cos (thta)); Float translateOffsetX = (float) ((lineLen + 2 * NODE_RADIUS) * math.sin (thta)); // 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); / / draw circles 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) {// Similarly 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(); }}Copy the code

Postscript: Jie wen standard

Further updates in this series link collection :(dynamic updates)

The first part of the Android edition is the data structure of the array table. The first part of the Android edition is the data structure of the array table. The first part is the data structure of the array table Visible data structures Android Stack Visible data structures Android Queue Visible data structures Android Binary search tree More data structures – more on that later

2. Growth records and errata of this paper
Program source code The date of note
V0.1 – making 2018-11-25 Visible data structure Android version of binary search tree structure implementation
3. More about me
Pen name QQ WeChat hobby
Zhang Feng Jie te Li 1981462002 zdl1994328 language
My lot My Jane books I’m the nuggets Personal website
4. A statement

1—- This article is originally written by Zhang Fengjie, please note if reproduced

2—- welcome the majority of programming enthusiasts to communicate with each other 3—- personal ability is limited, if there is something wrong welcome to criticize and testify, must be humble to correct 4—- see here, I thank you here for your love and support