Writing in the front

  • Full text data structure

Tree structure

  • Set bottom with array expansion implementation
  • Node, one object, one unit of the tree
  • Leaf node, a node that has no children
  • The weight of the node, the node value
  • Path to find the path of the node from the root node
  • Layer, same level
  • The height of the tree, the number of layers
  • Forest, multiple subtrees
  • A binary tree can have at most two children per node
  • If all the leaves of the binary tree are at the last level, and the total number of nodes is2^n-1, n is the number of layers, then it is full binary tree
  • If all the leaf nodes of the binary tree are in the last or penultimate layer, and the leaf nodes of the last layer are continuous on the left, and the leaf nodes of the penultimate layer are continuous on the right, it is a complete binary tree, and a full binary tree must be a complete binary tree

traverse

  • Preorder traversal, first output the parent node, then traversal the left and right subtrees
  • Middle order traversal, first traverses the left subtree, then outputs the parent node, then traverses the right subtree
  • After traversal, first traverses the left subtree, then traverses the right subtree, and finally outputs the parent node
  • Create a tree
class BinaryTree { private Node root; public void setRoot(Node root) { this.root = root; } public void preOrder() {if (this.root! = null) { this.root.preOrder(); } else { System.out.println("empty"); Public void infixOrder() {if (this.root! = null) { this.root.infixOrder(); } else { System.out.println("empty"); Public void postOrder() {if (this.root! = null) { this.root.postOrder(); } else { System.out.println("empty"); }}}Copy the code
  • Create a node
class Node { private int id; private String name; private Node left; // left Node private Node right; // right node //setter getter toString constructor... Public void preOrder() {system.out.println (this); // If (this.left! = null) { this.left.preOrder(); } // If (this.right! = null) { this.right.preOrder(); }} public void infixOrder() {if (this.left! = null) { this.left.infixOrder(); } System.out.println(this); if (this.right ! = null) { this.right.infixOrder(); }} public void postOrder() {if (this.left! = null) { this.left.postOrder(); } if (this.right ! = null) { this.right.postOrder(); } System.out.println(this); }}Copy the code

To find the

  • The search order is consistent with traversal
  • Before the order lookup
public Node preOrderSearch(int id) { if (this.id == id) { return this; } Node res = null; if (this.left ! = null) { res = this.left.preOrderSearch(id); } if (res ! = null) {return res; } if (this.right ! = null) { res = this.right.preOrderSearch(id); } if (res ! = null) {return res; } return res; }Copy the code
  • In order to find
public Node infixOrderSearch(int id) { Node res = null; if (this.left ! = null) { res = this.left.preOrderSearch(id); } if (res ! = null) {return res; } if (this.id == id) { return this; } if (this.right ! = null) { res = this.right.preOrderSearch(id); } if (res ! = null) {return res; } return res; }Copy the code
  • After the sequence to find
public Node postOrderSearch(int id) { Node res = null; if (this.right ! = null) { res = this.right.preOrderSearch(id); } if (res ! = null) {return res; } if (this.left ! = null) { res = this.left.preOrderSearch(id); } if (res ! = null) {return res; } if (this.id == id) { return this; } return res; }Copy the code
  • The tree called
public Node preOrderSearch(int id) { if (this.root ! = null) { return this.root.preOrderSearch(id); } else { System.out.println("empty"); return null; } } public Node infixOrderSearch(int id) { if (this.root ! = null) { return this.root.infixOrderSearch(id); } else { System.out.println("empty"); return null; } } public Node postOrderSearch(int id) { if (this.root ! = null) { return this.root.postOrderSearch(id); } else { System.out.println("empty"); return null; }}Copy the code

delete

  • If the node to be deleted is a leaf node, delete it. Delete the non-leaf node, delete the subtree
  • Delete the parent of the node to kill the deleted node
  • Determine whether the node is root. Determine the root node in the tree, and then determine the child node
public void delNode(int id) { if (root ! If (root.getid () == id) {root = null; } else { root.delNode(id); } } else { System.out.println("empty"); }}Copy the code
  • Node, first determine whether the left and right child nodes of the current node, if not, continue to enter recursively, determine the left and right child nodes of the child node
public void delNode (int id) { if (this.left ! = null && this.left.id == id) { this.left = null; return; } if (this.right ! = null && this.right.id == id) { this.right = null; return; } if (this.left ! = null) { this.left.delNode(id); } if (this.right ! = null) { this.right.delNode(id); }}Copy the code

Modifying a Deletion Rule

  • If the non-leaf node has only one node, the child node is used instead. If a non-leaf node has two children, the left child is replaced and the right child is the right child of the left child
  • What if both the left and right child nodes have children
public void delNode (int id) { if (this.left ! = null && this.left.id == id) { if (this.left.left == null && this.left.right == null) { this.left = null; } else if (this.left.left ! = null && this.left. Right == null) {this.left = this.left; } else if (this.left.left == null && this.left.right ! = null) {this.left = this.left; } else {this.left. Left. Right = this.left. this.left.right = null; // The left node replaces the deleted node this.left = this.left. Left; } return; } if (this.right ! = null && this.right.id == id) { if (this.right.left == null && this.right.right == null) { this.right = null; } else if (this.right.left ! = null && this.right. Right == null) {this.right = this.right; } else if (this.right.left == null && this.right.right ! = null) {this.right = this.right; } else {this.right.left. Right = this.right. Right; this.right.right = null; // The left node replaces the deleted node this.right = this.right.left; } return; } if (this.left ! = null) { this.left.delNode(id); } if (this.right ! = null) { this.right.delNode(id); }}Copy the code

Sequential storage of binary trees

  • Arrays are converted to trees
  • The left child array of the NTH element has the subscript2*n+1, the subscript in the right child node array is2*n+2, the subscript in the parent node array is(n-1)/2N is the subscript in the array
class ArrBinaryTree { private int[] arr; public ArrBinaryTree(int[] arr) { this.arr = arr; } public void preOrder() { this.preOrder(0); } / / preOrder traversal of the binary sequence storage public void preOrder (int index) {/ / array is empty if (arr = = null | | arr. Length = = 0) { System.out.println("empty"); return; } System.out.println(arr[index]); If ((index * 2 + 1) < arr.length) {preOrder(index * 2 + 1); } if ((index * 2 + 2) < arr.length) {preOrder(index * 2 + 2); }}}Copy the code

Cue binary tree

  • For a binary tree of n nodes, containsn+1Pointer fields,2n-(n-1)A node has two Pointers, n node connections only needn-1A pointer to the
  • The null pointer field of the binary list is used to store the values that point to the node in some traversal orderPrecursor and successor nodes, the preceding and following nodes are traversed in this order
  • Antecedent cuing binary tree
public void threadedNodes(ThreadedNode node) { if (node == null) { return; } if (node.getLeft() == null) {node.setleft (preNode); Node.setlefttype (1); } // Process subsequent nodes if (preNode! = null && prenode.getright () == null) {// Make the right pointer to the current node prenode.setright (node); preNode.setRightType(1); } // After each node is processed, make the current node the precursor of the next node. if (node.getLeftType() == 0) { threadedNodes(node.getLeft()); } if (node.getRightType() == 0) { threadedNodes(node.getRight()); }}Copy the code
  • Middle order cueing binary tree
public void threadedNodes(ThreadedNode node) { if (node == null) { return; } // Cue left parent right threadedNodes(node.getLeft()); If (node.getLeft() == null) {node.setLeft(preNode); // Change type node.setLeftType(1); } // Process the successor node, using the current node to process the successor of the previous node if (preNode! = null && prenode.getright () == null) {// Make the right pointer to the current node prenode.setright (node); preNode.setRightType(1); } // After each node is processed, the current node is the precursor of the next node. threadedNodes(node.getRight()); }Copy the code
  • Subsequent cueing binary tree
public void threadedNodes(ThreadedNode node) { if (node == null) { return; } threadedNodes(node.getLeft()); threadedNodes(node.getRight()); If (node.getLeft() == null) {node.setLeft(preNode); // Change type node.setLeftType(1); } // Process subsequent nodes if (preNode! = null && prenode.getright () == null) {// Make the right pointer to the current node prenode.setright (node); preNode.setRightType(1); } // After each node is processed, make the current node the precursor of the next node. }Copy the code

Traversal cued binary trees

  • Antecedent traversal cued binary tree
public void threadedList() { ThreadedNode node = root; while (node ! While (node.getLeftType() == 0) {system.out.println (node); while (node.getLeftType() == 0) {system.out.println (node); node = node.getLeft(); } System.out.println(node); node = node.getRight(); }}Copy the code
  • Middle order traversal cued binary tree
public void threadedList() { ThreadedNode node = root; while (node ! While (node.getLeftType() == 0) {node = node.getLeft(); } System.out.println(node); While (node.getrightType () == 1) {node = node.getright (); System.out.println(node); } node = node.getRight(); }}Copy the code
  • Because the backward traversal order isAbout the father, the output of the left subtree is finished, and the parent node of the current subtree is returned. This parent node has the left child of the right subtreePrecursor node, but because of the parent nodeBoth nodes have children to the left and right, then the parent node cannot find the next node in the normal way, so there are two processing methodsIn reverse order, starting from the rightandThe parent node is recorded in the node and the previous node is recorded in the traversal. After traversing the left subtree, if the traversal continues and the right child node of the node is the previous node, the parent node of the node is found and traversal the right node, that is, the parent node
  • Backorder traversal cued binary tree (reverse order)
public void threadedList() { ThreadedNode node = root; Stack<ThreadedNode> stack = new Stack<>(); while (node ! While (node.getrightType () == 0) {stack.push(node); while (node.getrightType () == 0) {stack. node = node.getRight(); } stack.push(node); node = node.getLeft(); } while (! stack.isEmpty()) { System.out.println(stack.pop()); }}Copy the code
  • Post-order traversal cued binary tree (positive order)
public void threadedList() { ThreadedNode node = root; ThreadedNode pre = null; while (node ! While (node.getLeftType() == 0) {node = node.getLeft(); } System.out.println(node); While (node.getrightType () == 1) {// Record the last node, for judgment; If the last node is the right child of a parent node // the right half of the parent node has been processed. node = node.getRight(); System.out.println(node); } if (node == root) {node = null; } // The parent node of the node is the right child node of the node, indicating that the tree structure of the node is complete. = null && node.getRight() == pre) { pre = node; node = node.getParent(); } // Process the right subtree and start at the lower level. The left child that completes the previous round is the sibling of the node if (node! = null && node.getRightType() == 0) { node = node.getRight(); }}}Copy the code