An overview,
When you look at the JDK source code, you see maps, and when you look at HashMap, part of the source code has to do with red-black trees. Simply learn the data structure of the tree from scratch, write it down, and leave a reference and learning material for yourself and others.
It involves sorting using binary trees, finding node values, pre-order traversal, mid-order traversal, subsequent traversal (their recursive and non-recursive implementations), deleting nodes, finding the largest node, finding the smallest node.
Second, the first
The code snippet is shown below, with the full code at the end of the document
1. Define binary tree nodes (I used static inner classes)
/** * static class Node {int value; Node leftChild; Node rightChild; public Node(int value) { this.value = value; } public Node(int value, Node leftChild, Node rightChild) { this.value = value; this.leftChild = leftChild; this.rightChild = rightChild; } @Override public String toString() { return String.valueOf(value); } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() ! = o.getClass()) return false; Node node = (Node) o; return value == node.value; }}Copy the code2. The overall structure of the class and defining operations
/** * public class BinaryTree {private Node root; private int treeDepth; private int treeWidth; public BinaryTree(int value) { this.root = new Node(value); } public Boolean insert(int t) // Insert node public int getTreeDepth() public int getTreeWidth() // The maximum logical width of the tree public Void preOrderTtaverse() public void preOrderByStack() public void inOrderTraverse() // middle traversal public void preOrderByStack( Void inOrderByStack() public void postOrderTraverse() public void postOrderByStack() public void postOrderByStack( Public void printBinaryTreeByRow() // Print binary tree public void printBinaryTreeByColumn() // Print binary tree public Node findKey(int Public Boolean removeNode(int value) // Remove the specified node public int getMinValue() // Get the minimum value public int GetMaxValue () // Get maximum value}Copy the code3. Insert data
@return specifies whether the return operation succeeds. @throws Exception. / public Boolean Insert (int t) throws Exception { Node newNode = new Node(t); Int count = 0; If (root == null) {// if the root node is empty, assign the newNode to the root node root = newNode; count++; } else { Node current = root; // Node pointer Node parent; // The parent of the node pointer for (; ;) {// loop over count++; If (t < current. Value) {parent = current; current = current.leftChild; Parent. leftChild = newNode; if (current == null) {parent.leftChild = newNode; break; }} else if (t > current. Value) {parent = current; current = current.rightChild; Parent.rightchild = newNode; parent.rightChild = newNode; parent.rightChild = newNode; break; Else {throw new Exception("comparsion Exception for compare value big or small(insert() method!) "); }}} if (treeDepth < count) {// calculate the treeDepth and the logical width treeDepth = count; treeWidth = (int)Math.pow(2, treeDepth); } return true; }Copy the code4. Obtain the maximum depth and logical width of the binary sorting tree
Public int getTreeDepth() {return treeDepth; Public int getTreeWidth() {return treeWidth; }Copy the code5. Front-order traversal
Recursive implementation:
/** * public void preOrderTtaverse() {system.out.print ("); preOrderTtaverse(root); System.out.println(); } /** * if the binary tree is empty, the null operation returns; * If the binary tree is not empty, perform the following operations: * (1) Access the root node. Private void preOrderTtaverse(Node Node) {if (Node == null) return; System.out.print(node.value + " "); preOrderTtaverse(node.leftChild); preOrderTtaverse(node.rightChild); }Copy the codeNon-recursive implementation:
* 1) For any node current, if the node is not empty, access the node and then push the node, and set the left subtree node to current, repeat the operation until current is empty. * 2) If the left subtree is empty, the top node of the stack is removed from the stack, and the right subtree of the node is set to current * 3) Repeat steps 1 and 2 until current is empty and the nodes in the stack are empty. */ public void preOrderByStack() {system.out.print (" preOrderByStack "); Stack<Node> stack = new Stack<>(); // stack, used to save the Node Node current = root; // Node pointer while (current! = null || ! Stack.isempty ()) {// loop while (current! = null) { stack.push(current); System.out.print(current.value + " "); current = current.leftChild; } if (! stack.isEmpty()) { current = stack.pop(); current = current.rightChild; } } System.out.println(); }Copy the code6. Middle order traversal
Recursive implementation:
/** * if the binary tree is empty, the null operation returns; If no, perform the following operations: * 1. Traversal the left subtree of the root node * 2. Public void inOrderTraverse() {system.out.print (" binary traverse: "); public void inOrderTraverse() {system.out.print (" binary traverse: "); inOrderTraverse(root); System.out.println(); } private void inOrderTraverse(Node Node) {if (Node == null) return; inOrderTraverse(node.leftChild); System.out.print(node.value + " "); inOrderTraverse(node.rightChild); }Copy the codeNon-recursive implementation:
* 1) For any node current, if the node is not empty, the node is pushed, and the left subtree node is set to current, and the operation is repeated until current is empty. * 2) If the left subtree is empty, the top node is removed from the stack, and the right subtree of the node is set to current * 3) Repeat steps 1 and 2 until current is empty and the nodes in the stack are empty. */ public void inOrderByStack() {system.out.print (" "); Stack<Node> stack = new Stack<>(); Node current = root; while (current ! = null || ! stack.isEmpty()) { while (current ! = null) { stack.push(current); current = current.leftChild; } if (! stack.isEmpty()) { current = stack.pop(); System.out.print(current.value + " "); current = current.rightChild; } } System.out.println(); }Copy the code7. Subsequent traversal
Recursive implementation:
/** * if the binary tree is empty, the null operation returns; Otherwise, perform the following operations: * 1. Subsequently, traverse the left subtree * 2 of the root node. Public void postOrderTraverse() {system.out.print (" binary tree: "); public void postOrderTraverse() {system.out.print (" binary tree: "); postOrderTraverse(root); System.out.println(); } private void postOrderTraverse(Node Node) {if (Node == null) return; postOrderTraverse(node.leftChild); postOrderTraverse(node.rightChild); System.out.print(node.value + " "); }Copy the codeNon-recursive implementation:
/** * Back-order non-recursive traversal: * 1) For any node current, if the node is not empty, access the node and then push the node, and set the left subtree node to current, repeat the operation until current is empty. * 2) If the left subtree is empty, take the right subtree of the top node of the stack. If the right subtree is empty or the right subtree has just been visited, access the node and set preNode to the node * 3) Repeat steps 1 and 2 until current is empty and the node in the stack is empty. */ public void postOrderByStack() {system.out.print (); / / Public void postOrderByStack() {system.out.print (); Stack<Node> stack = new Stack<>(); Node current = root; Node preNode = null; while (current ! = null || ! stack.isEmpty()) { while (current ! = null) { stack.push(current); current = current.leftChild; } if (! stack.isEmpty()) { current = stack.peek().rightChild; if (current == null || current == preNode) { current = stack.pop(); System.out.print(current.value + " "); preNode = current; current = null; } } } System.out.println(); }Copy the code8. Delete the node(Relatively complicated stuff here)
- Delete a node as a leaf node
// Delete node by node: / / 1. If need to delete the node to a leaf node (waitRemoveNode. LeftChild = = null && waitRemoveNode. RightChild = = null) {/ / if the root node (only do a node in the tree node) if (waitRemoveNode == root) { root = null; } else {if (isLeftChild) // if the leaf node is the leftChild of the parent node, set the leftChild of the parent node to null parent. Else // if the leaf node is the rightChild of the parent, set the rightChild of the parent to null parent.rightChild = null; }}Copy the code2) The deleted node has only one node: only one left child node and only one right child node
/ / 2.1 there is a need to delete the node, and the node's left child node else if (waitRemoveNode. RightChild = = null) {/ / if the node is the root node, If (waitRemoveNode == root) {root = waitRemovenode.leftChild; } else {// if the node is the leftChild of the parent node, change the leftChild of the node to be deleted to the leftChild of the parent node. Else // if the node is the rightChild of the parent node, change the leftChild of the node to be deleted to the rightChild of the parent node. Else if (waitRemovenode.leftChild == null) {// If waitRemovenode.leftChild == null) { The root node right child node to the root node of the if (waitRemoveNode = = root) {root = waitRemoveNode. RightChild; } else {/ / if the node is the parent node's left child node, the node's right child node to the parent node is to be deleted the left child node of the if (isLeftChild) parent. LeftChild = waitRemoveNode. RightChild; Else / / if the node is the parent node's right child node, to the right child node to the parent node to node is to be deleted right child nodes of the parent, rightChild = waitRemoveNode. RightChild; }}Copy the code3) The node to be deleted has two child nodes: in this case, a node needs to be found to replace the node to be deleted; In a binary sorting tree, the best node to replace the node to be deleted is the node that is less than (next in size to it) its node or less than (smallest of all the elements larger than it) its node. Here, we choose the node that is less than it, and the technical term for a node that is less than it is called a successor node.
Successor node: The node whose critical value is next higher than the node to be deleted is its successor node. To put it more simply, a successor node is the smallest value in the set of nodes that is greater than the key value of the node to be deleted.
The subsequent node code is as follows:
Private Node getSuccessorNode(Node waitRemoveNode) {Node successorParent = null; // The parent of the Node succeeded = waitRemoveNode; . / / the subsequent Node Node current = waitRemoveNode rightChild; // Find the successor node and its parent while (current! = null) { successorParent = successor; successor = current; current = current.leftChild; } // If the successor is not the right subtree of the node to be deleted if (succeeded! = waitRemoveNode. RightChild) {/ / will be pointing to the subsequent subsequent node's right child node parent node's left child node successorParent. LeftChild = successor, rightChild; / / will be the right child node to node is to be deleted to subsequent successor. The node's right child node rightChild = waitRemoveNode. RightChild; } // In any case it is necessary to point the left children of the node to be deleted to the left children of the succeeding nodes. LeftChild = waitremovenode. leftChild; return successor; }Copy the codeA) If the successor node is the right child of the node to be deleted (this right child has no left child, and if it does, it cannot be the successor node)
// if the deleted node is the leftChild of the parent node: parent. LeftChild = succeeded; successor.leftChild = delNode.leftChild; // if the deleted node is the rightChild of the parent node: parent.rightChild = antecedent; successor.leftChild = delNode.leftChildCopy the codeB) If the successor node is the left descendant of the right child node of the node to be deleted:
/ / delete node to the parent node's left child node: successorParent. LeftChild = successor. RightChild; successor.rightChild = delNode.rightChild; parent.leftChild = successor; successor.leftChild = delNode.leftChild; / / delete node to the parent node's right child nodes: successorParent. LeftChild = successor. RightChild; successor.rightChild = delNode.rightChild; parent.rightChild = successor; successor.leftChild = delNode.leftChild;Copy the codeTo sum up, the complete deletion code is as follows:
Public Boolean removeNode(int value) {Node waitRemoveNode = root; // Node parent = null; Boolean isLeftChild = true; While (true) {if (current, parent, isLeftChild) {if (current, parent, isLeftChild) {if (current, parent, isLeftChild) {if (current, parent, isLeftChild) {if (current, parent, isLeftChild) {if (current, parent, isLeftChild, isLeftChild) (value == waitRemoveNode.value) { break; } else if (value < waitRemoveNode.value) { isLeftChild = true; parent = waitRemoveNode; waitRemoveNode = waitRemoveNode.leftChild; } else { isLeftChild = false; parent = waitRemoveNode; waitRemoveNode = waitRemoveNode.rightChild; If (waitRemoveNode == null) return false; if (waitRemoveNode == null) return false; } // Delete nodes by case: / / 1. If need to delete the node to a leaf node (waitRemoveNode. LeftChild = = null && waitRemoveNode. RightChild = = null) {/ / if the root node (only do a node in the tree node) if (waitRemoveNode == root) { root = null; } else {if (isLeftChild) // if the leaf node is the leftChild of the parent node, set the leftChild of the parent node to null parent. Else // if the leaf node is the rightChild of the parent, set the rightChild of the parent to null parent.rightChild = null; }} / / 2.1 there is a need to delete the node, and the node's left child node else if (waitRemoveNode. RightChild = = null) {/ / if the node is the root node, If (waitRemoveNode == root) {root = waitRemovenode.leftChild; } else {// if the node is the leftChild of the parent node, change the leftChild of the node to be deleted to the leftChild of the parent node. Else // if the node is the rightChild of the parent node, change the leftChild of the node to be deleted to the rightChild of the parent node. Else if (waitRemovenode.leftChild == null) {// If waitRemovenode.leftChild == null) { The root node right child node to the root node of the if (waitRemoveNode = = root) {root = waitRemoveNode. RightChild; } else {/ / if the node is the parent node's left child node, the node's right child node to the parent node is to be deleted the left child node of the if (isLeftChild) parent. LeftChild = waitRemoveNode. RightChild; Else / / if the node is the parent node's right child node, to the right child node to the parent node to node is to be deleted right child nodes of the parent, rightChild = waitRemoveNode. RightChild; If the Node to be deleted has two nodes, the successor of the Node needs to be found as the replacement else {Node successorNode (waitRemoveNode); If (waitRemoveNode == root) {root = succeeded; // If the node to be deleted is the root node, change the successor node to the root and the left child of the root node to the left child of the successor. } else {// if the node to be deleted is the leftChild of the parent, turn the successor of the node into the leftChild of the parent if (isLeftChild) parent. LeftChild = succeeded; Else // if the junction to be deleted is the rightChild of the parent, turn the successor of that node into the rightChild of the node. } } waitRemoveNode = null; return true; }Copy the codeThe deletion in the above implementation is complicated. There is a simple alternative operation called lazy deletion. In lazy deletion, we do not actually remove the node from the binary search tree, but mark the node as “deleted.” This way, we just need to find the element and tag it, and we’re done deleting the element. If the same element is re-inserted, we can find the node and untag the deletion.
The lazy delete implementation is relatively simple, you can try it. The memory occupied by the tree does not decrease with the deletion of the node. Lazy nodes actually trade memory space for ease of operation.
9. Search for the specified node
Public Node findKey(int value) {Node current = root; while (true) { if (value == current.value) return current; else if (value < current.value) current = current.leftChild; else if (value > current.value) current = current.rightChild; if (current == null) return null; }}Copy the code- Get the maximum and minimum values
Public int getMinValue() {Node current = root; while (true) { if (current.leftChild == null) return current.value; current = current.leftChild; Public int getMaxValue() {Node current = root; while (true) { if (current.rightChild == null) return current.value; current = current.rightChild; }}Copy the code- Prints the binary sort tree
public void printBinaryTreeByRow() { printBinaryTreeByRow(root); } public void printBinaryTreeByColumn() { printBinaryTreeByColumn(0, root); } private void printBinaryTreeByColumn(int space, Node node) { System.out.println(); for (int i = 0; i < space; i++) { System.out.print("\t"); } system.out. print(" [" + node.value + "] "); if (node.leftChild ! = null) { for (int i = 0; i < space + 2; i++) { System.out.print("\t"); } printBinaryTreeByColumn(space + 3, node.leftChild); } if (node.rightChild ! = null) { for (int i = 0; i < space + 2; i++) { System.out.print("\t"); } printBinaryTreeByColumn(space + 3, node.rightChild); }} private void printBinaryTreeByRow(Node Node) {Queue<Node> Queue = new LinkedList<>(); // the rightmost Node of the current line (the rightmost element) Node lastNode = Node; // Next line rightmost Node (rightmost element) Node nextLastNode = null; Queue.add (node); // Queue. While (queue.size() > 0) {nowNode = queue.poll(); If ((nextLastNode = nowNode.leftChild)! = null) { queue.add(nextLastNode); } // If ((nextLastNode = nowNode.rightChild)! = null) { queue.add(nextLastNode); } System.out.print(nowNode.value + " "); if (nowNode.equals(lastNode)) { System.out.println(); lastNode = nextLastNode; }}}Copy the codeThat’s all!
Test code
/** * BinaryTree test */ public class BinaryTreeDemo {public static void main(String[] args) throws Exception {BinaryTree bt = new BinaryTree(50); bt.insert(30); bt.insert(80); bt.insert(10); bt.insert(40); bt.insert(35); bt.insert(60); bt.insert(90); bt.insert(70); bt.insert(83); bt.insert(95); bt.insert(75); bt.insert(88); bt.preOrderTtaverse(); bt.preOrderByStack(); bt.inOrderTraverse(); bt.inOrderByStack(); bt.postOrderTraverse(); bt.postOrderByStack(); System.out.println(" query 777: "+ bt.findKey(777)); System.out.println(" min: "+ bt.getMinValue()); System.out.println(" Max: "+ bt.getMaxValue()); System.out.println(); System.out.println(" line print: "); bt.printBinaryTreeByRow(); System.out.println(); System.out.println(" column print: "); bt.printBinaryTreeByColumn(); System.out.println(); bt.removeNode(32); Bt.removenode (50); Bt.removenode (248); // Delete bt.removenode (248); Bt.removenode (248); // Delete bt.removenode (248); Bt.removenode (580); // Delete bt.removenode (580); Bt.removenode (888); // Delete a node with two children and the successor is the left descendant of the right child of the deleted node. Bt.removenode (52); // Delete bt.removenode (52); // Delete bt.removenode (52); System.out.println(" line print: "); // Delete a node with two children and the root node. bt.printBinaryTreeByRow(); System.out.println(); System.out.println(" column print: "); bt.printBinaryTreeByColumn(); }}Copy the codeRunning results:
Binary tree its foreorder traversal: 50 30 10 40 35 80 60 70 75 90 83 88 95 Foreorder traversal non-recursive implementation: 50 30 10 40 35 80 60 70 75 90 83 88 95 Binary tree its middle order traversal: 10 30 35 40 50 60 70 75 80 83 88 90 95 non-recursive implementation of order traversal: 10 30 35 40 50 60 70 75 80 83 88 90 95 Binary tree its post-order traversal: 10 35 40 30 75 70 60 88 83 95 90 80 50 The non-recursive implementation is as follows: 10 35 40 30 75 70 60 88 83 95 90 80 50 777: null Minimum value: 10 Maximum value: 95
Line printing: 50 30 80 10 40 60 90 35 70 83 95 75 88 column printing:
[50] [30] [10] [40] [35] [80] [60] [70] [75] [90] [83] [88] [95] Line print: 60 30 80 10 40 70 90 35 75 83 95 88 line print:
【60】
【30】
【10】
【40】
【35】
【80】
【70】
【75】
【90】
【83】
【88】
【95】