One, binary sorting tree definition
1. Definition of binary sorting tree <br />Binary Sort Tree (Binary Sort Tree), also known as Binary Search Tree. It is defined as: a binary sorting tree or an empty tree, or a binary tree that meets the following properties:
① If its left subtree is not empty, the values of all nodes on the left subtree are smaller than the value of the root node;
② If its right subtree is not empty, the values of all nodes on the right subtree are greater than the values of the root node;
③The left and right subtrees themselves are each a binary sorting tree.
The above properties are referred to as the binary sorting tree property (BST property), so the binary sorting tree is actually a binary tree that satisfies the BST property.
2. Properties of binary sorting tree <br />Transfer the binary sorting tree in mid-order, and the resulting intermediate-order traversal sequence is an incremental ordered sequence.
3. Insert the binary sorting tree <br />Insert a new node into the binary sorting tree, to ensure that the inserted binary tree still meets the definition of the binary sorting tree.
Insert process:
If the binary sorting tree is empty, the node *S to be inserted into the empty tree as the root node;
When it is not empty, compare the keyword S->key to be inserted with the tree root keyword t->key. If s->key = t->key, there is no need to insert it. If s->key< t->key, it is inserted into the left subtree of the root. If s->key>t->key, it is inserted into the right subtree of the root. The insertion process in the subtree is the same as the insertion process in the tree. This continues until the node *s is inserted into the binary sorting tree as a new leaf, or until the tree is found to have nodes with the same keywords.
4. Search for binary sorting tree <br />Assuming that the root pointer of the binary sorting tree is root and the given keyword value is K, the search algorithm can be described as:
① Set initial value: q = root;
② If K = q -> key, the search is successful and the algorithm ends;
③ Otherwise, if K < q －＞ key and the left subtree of q is not empty, the left subtree of q is sent to q and then the step ②; otherwise, the search fails and the algorithm ends;
④ Otherwise, if K ＞ q －＞ key , and the right subtree of q is not empty, the right subtree of q is sent to q and then the step ②; otherwise, the search fails and the algorithm ends.
5. Deletion of binary sorting tree <br />Suppose that the deleted node is *p and the parents are *f, which is not lost in generality. Assume that *p is the left child of *f, the following is divided into three situations:
⑴ If node *p is a leaf node, you only need to modify the pointer of its parent node *f.
⑵ If the node *p has only the left subtree PL or only the right subtree PR, then just make PL or PR the left subtree of its parent node.
⑶ If the left and right subtrees of node *p are not empty, first find the middle order predecessor (or successor) node *s of *p (note that *s is the lower rightmost node in the left subtree of *p, and its right chain domain is empty), and then there are two ways: ① Let the left subtree of *p directly link to the left chain of the parent node *f of *p, and the right subtree of *p is chained to the right chain of *p's middle order predecessor node *s. ② Replace *p with the middle order predecessor node *s of *p (that is, copy the data of *s into *p), and chain the left subtree of *s to the left (or right) chain of the parent node *q of *s.
6. Traversal of binary trees <br />There are three ways to traverse binary trees, as follows:
(1) Pre-order traversal (DLR), first accessing the root node, then traversing the left subtree, and finally traversing the right subtree. Abbreviated root - left - right.
(2) In-order traversal (LDR), first traversal the left subtree, then access the root node, and finally traversal the right subtree. Abbreviated Note: Left-root-right.
(3) Post-order traversal (LRD), first traversing the left subtree, then traversing the right subtree, and finally accessing the root node. Abbreviated Left-Right-Root.
2. Code writing
1. Definition of tree node class 0
package com.lin; /** * Function summary: */ public class TreeNode { public Integer data; /* Parent node of this node*/ public TreeNode parent; /*Left child node of this node*/ public TreeNode left; /*Right child node of this node*/ public TreeNode right; public TreeNode(Integer data) { this.data = data; } @Override public String toString() { return "TreeNode [data=" + data + "]"; } } 2. Definition of binary sorting tree
package com.lin; /** * Function summary: Sort/balanced binary tree*/ public class SearchTree { public TreeNode root; public long size; /** * Add node to the tree* @param data * @return Boolean Insertion returns true */ public Boolean addTreeNode(Integer data) { if (null == root) { root = new TreeNode(data); System.out.println("Data was successfully inserted into the balanced binary tree"); return true; } TreeNode treeNode = new TreeNode(data);// The data to be inserted TreeNode currentNode = root; TreeNode parentNode; while (true) { parentNode = currentNode;// Save the parent node// The inserted data is smaller than the parent node if (currentNode.data > data) { currentNode = currentNode.left; // The left child node of the current parent node is empty if (null == currentNode) { parentNode.left = treeNode; treeNode.parent = parentNode; System.out.println("Data was successfully inserted into the binary search tree"); size++; return true; } // The inserted data is larger than the parent node} else if (currentNode.data < data) { currentNode = currentNode.right; // The right child node of the current parent node is empty if (null == currentNode) { parentNode.right = treeNode; treeNode.parent = parentNode; System.out.println("Data is successfully inserted into the binary search tree"); size++; return true; } } else { System.out.println("The input data is the same as the node's data"); return false; } } } /** * @param data * @return TreeNode */ public TreeNode findTreeNode(Integer data){ if(null == root){ return null; } TreeNode current = root; while(current != null){ if(current.data > data){ current = current.left; }else if(current.data < data){ current = current.right; }else { return current; } } return null; } } Here is a method of adding and searching
3. Front, middle and back traversal
package com.lin; import java.util.Stack; /** * Function summary: */ public class TreeOrder { /** * Recursive implementation of preorder traversal* @author linbingwen * @since August 29, 2015* @param treeNode */ public static void preOrderMethodOne(TreeNode treeNode) { if (null != treeNode) { System.out.print(treeNode.data + " "); if (null != treeNode.left) { preOrderMethodOne(treeNode.left); } if (null != treeNode.right) { preOrderMethodOne(treeNode.right); } } } /** * Looping to implement preorder traversal* @param treeNode */ public static void preOrderMethodTwo(TreeNode treeNode) { if (null != treeNode) { Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(treeNode); while (!stack.isEmpty()) { TreeNode tempNode = stack.pop(); System.out.print(tempNode.data + " "); // The right child node is not null, put the right child node in if (null != tempNode.right) { stack.push(tempNode.right); } // After putting the right child node, put the left child node, and take if (null != tempNode.left) { stack.push(tempNode.left); } } } } /** * Recursively implement in-order traversal* @param treeNode */ public static void medOrderMethodOne(TreeNode treeNode){ if (null != treeNode) { if (null != treeNode.left) { medOrderMethodOne(treeNode.left); } System.out.print(treeNode.data + " "); if (null != treeNode.right) { medOrderMethodOne(treeNode.right); } } } /** * Loop implementation in-order traversal* @param treeNode */ public static void medOrderMethodTwo(TreeNode treeNode){ Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode current = treeNode; while (current != null || !stack.isEmpty()) { while(current != null) { stack.push(current); current = current.left; } if (!stack.isEmpty()) { current = stack.pop(); System.out.print(current.data+" "); current = current.right; } } } /** * Recursively implement post-order traversal* @param treeNode */ public static void postOrderMethodOne(TreeNode treeNode){ if (null != treeNode) { if (null != treeNode.left) { postOrderMethodOne(treeNode.left); } if (null != treeNode.right) { postOrderMethodOne(treeNode.right); } System.out.print(treeNode.data + " "); } } /** * Looping to implement post-order traversal* @param treeNode */ public static void postOrderMethodTwo(TreeNode treeNode){ if (null != treeNode) { Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode current = treeNode; TreeNode rightNode = null; while(current != null || !stack.isEmpty()) { while(current != null) { stack.push(current); current = current.left; } current = stack.pop(); while (current != null && (current.right == null ||current.right == rightNode)) { System.out.print(current.data + " "); rightNode = current; if (stack.isEmpty()){ System.out.println(); return; } current = stack.pop(); } stack.push(current); current = current.right; } } } } 4. How to use
package com.lin; /** * Function summary: */ public class SearchTreeTest { /** * @param args */ public static void main(String[] args) { SearchTree tree = new SearchTree(); tree.addTreeNode(50); tree.addTreeNode(80); tree.addTreeNode(20); tree.addTreeNode(60); tree.addTreeNode(10); tree.addTreeNode(30); tree.addTreeNode(70); tree.addTreeNode(90); tree.addTreeNode(100); tree.addTreeNode(40); System.out.println("================================================================================================================================================================================================================================================================================================================================================================================================================================================================================= System.out.println("====================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================== TreeOrder.postOrderMethodOne(tree.root); System.out.println(); System.out.println("======================================================================================================================================================================================================================================================================================================================================================================================================================================================================================= System.out.println("====================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================== TreeOrder.medOrderMethodTwo(tree.root); } }Output result:
Similarly, the search process is as follows:
TreeNode node = tree.findTreeNode(100); System.out.println(node);
The result is correct
The above is a detailed introduction to the Java binary sorting tree. I hope it will be helpful to everyone's learning Java programming.