Writing in the front

  • Full text data structure

Binary sort tree

  • For any non-leaf node, the left child is smaller than the current node and the right child has a larger value than the current node
  • Everything on the right is bigger than anything on the left
  • For the binary sort tree, let’s doIn the sequence traversalThat’s the ascending output

Create and Add

  • Binary sort tree
class BinarySortTree { private Node root; Public void add(Node Node) {if (root == null) {root = Node; } else { root.add(node); Public void infixOrder() {if (root! = null) { root.infixOrder(); } else { System.out.println("empty"); }}}Copy the code
  • node
class Node { int value; Node left; Node right; Public void add(Node Node) {if (Node == null) {return; } if (node.value < this.value) {if (this.left == null) {this.left = node; } else {// Recursively add this.left. Add (node); }} else {if (this.right == null) {this.right = node; } else { this.right.add(node); Public void infixOrder() {if (this.left! = null) { this.left.infixOrder(); } System.out.println(this); if (this.right ! = null) { this.right.infixOrder(); } } //toString constructor... }Copy the code

delete

  • Delete leaf nodes
  • Delete a node that has only one subtree
  • Delete a node with two subtrees

Node method

  • Find the node to delete
public Node search(int value) { if (value == this.value) { return this; If (this.left == null) {return null; if (this.left == null) {return null; } return this.left.search(value); } else { if (this.right == null) { return null; } return this.right.search(value); }}Copy the code
  • The default node to delete is not root. Root is handled in the tree
public Node searchParent(int value) { if ((this.left ! = null && this.left.value == value) || (this.right ! = null && this.right.value == value)) { return this; } else {// If the value of the parent node is less than the value of the current node, and the left child node of the current node is not empty // If the value of the parent node is ==value, it must not be the root node. If (value < this.value && this.left!) = = if (value < this.value && this.left! = null) { return this.left.searchParent(value); } else if (value > this.value && this.right ! = null) { return this.right.searchParent(value); } else { return null; }}}Copy the code

Tree approach

  • Find the node to delete
public Node search(int value) { if (root == null) { return null; } else { if (root.value == value) { return root; } return root.search(value); }}Copy the code
  • Find the parent node
public Node searchParent(int value) { if (root == null) { return null; } else { if (root.value == value) { return null; } return root.searchParent(value); }}Copy the code
  • Remove nodes
public void delNode(int value) { if (root == null) { return; } else { Node targetNode = search(value); if (targetNode == null) { return; } // find the parent of targetNode Node Node parent = searchParent(value); If (parent == null) {if (parent == null) {if (parent == null) {if (parent == null) { If (root.left == null && root.right == null) {root = null; return; } else if (root.left ! = null && root.right == null) {// If only left root = root.left; return; } else if (root.left == null && root.right ! = null) { root = root.right; return; } // Both sides, same as the second case} // the first case, If (targetNode.left == null && targetNode.right == null) {// Check whether targetNode is the left or right child of the parent node if (parent.left! = null && parent.left.value == value) { parent.left = null; } else if (parent.right ! = null && parent.right.value == value) { parent.right = null; } } else if (targetNode.left ! = null && targetNode.right ! Int minValue = delRightTreeMin(targetNode.right); targetNode.value = minValue; } else {// In the second case, delete a subtree node // and targetNode must be a child of parent, through 'parent.left! = null 'protects the first judgment // If it is not the left child, then it must be the right child. = null) { if (parent.left ! = null && parent.left. Value == value) {// The node to be removed is the left child of the parent. } else {//targetNode is the right child of parent; parent.right = targetNode. }} else {// Delete node has right child if (parent.left! = null && parent.left.value == value) { parent.left = targetNode.right; } else {//targetNode is the right child of parent; parent.right = targetNode.right; } } } } }Copy the code
  • In the third case, find the smallest node in the right subtree (go all the way to the left of the right subtree) and replace the value of the deleted node
/** * returns the minimum value and deletes the node passed by * @param node, */ public int delRightTreeMin(node node) {node target = node; // loop through the smallest node while (target.left! = null) { target = target.left; } delNode(target.value); return target.value; }Copy the code
  • In the third case, find the largest from the right subtree of the left subtree
public int delLeftTreeMax(Node node) { Node target = node; While (target. Right! = null) { target = target.right; } delNode(target.value); return target.value; }Copy the code