This is the 23rd day of my participation in the August More Text Challenge.More challenges in August”
The tree
Why do we need in-tree structure?
Array storage:
1, advantages: through the subscript access elements, fast, for ordered array can also use binary search to improve the speed of retrieval.
2. Disadvantages: If you want to retrieve a specific value, or insert value will be sorted and moved, low efficiency
Chain storage analysis:
- Advantages: in a certain program on the array storage mode optimization, such as the insertion of a value, only need to say the insertion point connected to the linked list, delete efficiency is the same good effect.
- Disadvantages: The efficiency of retrieval is still very low. When a value is retrieved, it needs to be retrieved from the list header.
Tree storage analysis:
It can improve the efficiency of data storage and reading. For example, binary trees can be used to ensure the speed of data retrieval and the speed of data insertion, deletion and modification.
Binary tree
1.Binary tree concept
Binary tree is an important type of tree structure. The data structure abstracted from many practical problems is often in the form of binary tree, even the general tree can be simply converted to binary tree, and the storage structure and algorithm of binary tree are relatively simple, so the binary tree is particularly important. The characteristic of binary tree is that each node can have at most two subtrees, and can be divided into left and right
2.ย The tree diagram
Common terms:
1, the node
2. Root
3. Parent
4. Children
5. Leaf nodes (nodes with no children)
6. Weight of node (node value)
7, path (from root to destination)
8 layers.
9, the subtree
10. Tree height (maximum number of layers)
11. Forest (multiple sub-trees constitute a forest)
ย
3.ย Introduction to binary trees
1. There are many kinds of trees in which each node can have at most two children
2. Binary trees are divided into left nodes and right nodes
3. If all the leaf nodes of the binary tree are in the last layer, and the total number of nodes is 2^n-1, and n is the number of layers, we call it a full binary tree
4. 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, we call it a completely complete binary tree.
4.ย Binary tree application case
The following binary tree can be traversed using pre-order, middle-order, and post-order
1. Pre-order traversal: output the parent node first and traverse the left and right subtrees
2. Middle order traversal: first traverses the left subtree, then traverses the parent node, and then traverses the right subtree
3. Back-order traversal: first traverses the left subtree, then the right subtree, and finally the parent node
Conclusion: The output order of the parent node is an order traversal
Node
Public class Node {private int no; /** * author: date:2021/3/22 16:55 * version:1.0 */ public class Node {private int no; private String name; private Node left; private Node right; public Node(int no,String name){ this.no = no; this.name = name; } public int getNo(){ return no; } public void setNo(int no){ this.no = no; } public String getName(){ return name; } public void setName(String name){ this.name = name; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; } @Override public String toString() { return "Node{" + "no=" + no + ", name='" + name + '\'' + ", left=" + left + ", right=" + right + '}'; } 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(); } // Output parent 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(); } // Output parent system.out.println (this); }}Copy the codeBinaryTree
/** * author: SSL * Date :2021/3/22 16:47 * version:1.0 */ public 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 (" Binary tree is empty, cannot be traversed "); } } public void infixOrder(){ if (this.root ! =null){ this.root.infixOrder(); }else {system.out.println (" Binary tree is empty, cannot be traversed "); } } public void postOrder(){ if (this.root ! =null){ this.root.postOrder(); }else {system.out.println (" Binary tree is empty, cannot be traversed "); }}}Copy the codeTest
Public class Test {public static void main(String[] args) {public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); Node root = new Node(1," sun Shang xiang "); Node2 = new Node(2," xiahou "); Node3 = new Node(3," "); Node node4 = new Node(4," lyu "); Node5 = new Node(5," Yu Ji "); Node6 = new Node(6," wangzaojun "); root.setLeft(node2); node2.setLeft(node3); root.setRight(node4); node4.setRight(node5); node2.setLeft(node6); binaryTree.setRoot(root); /** * preOrder */ binarytree.preorder (); System.out.println("-----------------------------------------------"); binaryTree.infixOrder(); System.out.println("-----------------------------------------------"); binaryTree.postOrder(); }}Copy the codeBinary tree query node
According to the order, order, order to search
Node
package com.bjpowernode.binary; Public class Node {private int no; /** * author: date:2021/3/22 16:55 * version:1.0 */ public class Node {private int no; private String name; private Node left; private Node right; public Node(int no,String name){ this.no = no; this.name = name; } public int getNo(){ return no; } public void setNo(int no){ this.no = no; } public String getName(){ return name; } public void setName(String name){ this.name = name; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; } @Override public String toString() { return "Node{" + "no=" + no + ", name='" + name + '\'' + ", left=" + left + ", right=" + right + '}'; } 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(); } // Output parent 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(); } // Output parent system.out.println (this); } public Node preOrderSearch(int no){if (this.no == no){return this; } lNode = null;} lNode = null; lNode = null; if (this.left ! =null){ lNode = this.left.preOrderSearch(no); } if (lNode ! =null){ return lNode; If (this.right! = this.right! = this.right! = this.right! = this.right! = this.right! =null){ lNode = this.right.preOrderSearch(no); } return lNode; } public Node infixOrderSearch(int no){/** * check whether the left child of the current Node is empty, if it is not empty, then check */ Node Node = null; if (this.left ! =null){ node = this.left.infixOrderSearch(no); } if (node ! =null){ return node; } if (this.no == no){ return this; } if (this.right ! =null){ node = this.right.infixOrderSearch(no); } return node; } /** * public Node postOrderSearch(int no){Node Node = null; if (this.left ! =null){ node = this.left.postOrderSearch(no); } if (node ! =null){ return node; } /** * if (this.right! = this.right! = this.right! =null){ node = this.right.postOrderSearch(no); } if (node ! =null){ return node; } /** * if (this.no==no){return this; } return node; }}Copy the codeBinaryTree
public 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 (" Binary tree is empty, cannot be traversed "); } } public void infixOrder(){ if (this.root ! =null){ this.root.infixOrder(); }else {system.out.println (" Binary tree is empty, cannot be traversed "); } } public void postOrder(){ if (this.root ! =null){ this.root.postOrder(); }else {system.out.println (" Binary tree is empty, cannot be traversed "); }} /** * preOrderNode(int no){if (root! =null){ return root.preOrderSearch(no); }else { return null; }} /** * public Node infixOrderNode(int no){if (root! =null){ return root.infixOrderSearch(no); }else { return null; }} /** ** public Node postOrderNode(int no){if (root! =null){ return root.postOrderSearch(no); }else { return null; }}}Copy the codetest
Public class Test {public static void main(String[] args) {author: date:2021/3/23 14:23 * version:1.0 */ BinaryTree binaryTree = new BinaryTree(); Node root = new Node(1," sun Shang xiang "); Node2 = new Node(2," xiahou "); Node3 = new Node(3," "); Node node4 = new Node(4," lyu "); Node5 = new Node(5," Yu Ji "); Node6 = new Node(6," wangzaojun "); root.setLeft(node2); node2.setLeft(node3); root.setRight(node4); node4.setRight(node5); node2.setLeft(node6); binaryTree.setRoot(root); /* /* binarytree.preorder (); System.out.println("-----------------------------------------------"); binaryTree.infixOrder(); System.out.println("-----------------------------------------------"); binaryTree.postOrder(); */ Node Node = binarytree.preOrderNode (5); if (node ! =null){system.out.printf (" info: id=%d name%s", node.getno (),node.getName()); }else {system.out.println (" not found "); } / sequence search after * * * * / Node infix. = binaryTree infixOrderNode (5); if (infix ! Printf (" info: id=%d name%s", infix.getno (),infix.getName()); }else {system.out.println (" not found "); } Node post = binaryTree.postOrderNode(5); if (post ! Printf (" id=%d name%s", post.getno (),post.getName()); }else {system.out.println (" not found "); }}}Copy the codeBinary trees delete nodes
Node deletion can be divided into two cases:
1. The node to be deleted is the leaf node, so the current points can be deleted.
2. The node to be deleted is a non-leaf node, so the subtree needs to be deleted.
Delete requirement:
1. Delete node 5
Add delete methods to the Node class
Public void delNode(int no){/** * * 2. If the left child of the current node is not empty and the left child is the node that needs to be deleted, the left child of the current node needs to be deleted. If this.left = null, return * this.left = null; if this.left = null, return * this.left = null; If (this.left! = this.left! = this.left! = this.left! =null &&this.left.no==no){ this.left = null; return; } /** * if (this.right! =null && this.right.no==no){ this.right = null; return; } /** * if (this.left! =null){ this.left.delNode(no); } /** * if (this.right! =null){ this.right.delNode(no); }}Copy the codeThe BinaryTree class adds a delete method
if (root ! =null){ if (root.getNo()==no){ root = null; }else { root.delNode(no); }}else {system.out.println (" tree is empty, cannot delete "); }}Copy the codetest
