One , preface

Array search is more convenient , You can use subscripts directly , But deleting and inserting are troublesome ;

Linked lists are the opposite , Delete and insert elements quickly , But the search is slow ;

here , Binary tree came into being , Binary tree has the advantages of linked list , There are also advantages of arrays , It is easy to use when dealing with large quantities of dynamic data , It's a compromise .

File system and database system generally use tree ( especially B tree ) Data structure data of , Mainly for sorting and retrieval efficiency .

Binary tree is the most basic and typical sort tree , Features of trees for teaching and research , It is rarely used in practice , Because the shortcomings are too obvious , It's like bubble sorting , Because efficiency is not practical , But we have to .

Two , Disadvantages of binary tree

1, Sequential storage may waste space ( In incomplete binary tree ), But the efficiency of reading a specified node is relatively high O(0);

2, Chained storage relative to binary tree , Less space wasted , But the efficiency of reading a node is low O(nlogn).

Three , Traversal and node deletion

Binary tree is a very important data structure , Many data structures are based on the evolution of binary tree . For binary tree, there are depth traversal and breadth traversal , Depth traversal has preorder , Three traversal methods of middle order and post order , Breadth traversal is what we usually call level traversal . Because the definition of tree itself is recursive , Therefore, the recursive method is used to achieve three kinds of tree traversal .

For a piece of code , Readability is sometimes more important than the efficiency of the code itself .

1, Four basic ergodic thoughts

* Preorder traversal : Root node --> Zuozishu --> Right subtree ;
* Middle order traversal : Zuozishu --> Root node --> Right subtree ;
* Subsequent traversal : Zuozishu --> Right subtree --> Root node ;
* level traversal : You just need to traverse by degrees ;
2, Custom binary tree

3, code implementation
package dataStructure.tree; public class BinaryTreeTest { public static void
main(String[] args) { // Create a binary tree BinaryTree binaryTree = new BinaryTree();
// Create node HeroNode root = new HeroNode(1, " Song Jiang "); HeroNode node2 = new HeroNode(2,
" Lu Junyi "); HeroNode node3 = new HeroNode(3, " Wu Yong "); HeroNode node4 = new
HeroNode(4, " Gongsun Sheng "); HeroNode node5 = new HeroNode(5, " Guan Sheng ");
root.setLeft(node2); root.setRight(node3); node3.setLeft(node4);
node3.setRight(node5); binaryTree.setRoot(root); System.out.println(" Preorder traversal ");
binaryTree.preOrder(); System.out.println(" Middle order traversal "); binaryTree.midOrder();
System.out.println(" Postorder traversal "); binaryTree.postOrder(); binaryTree.delNode(3);
System.out.println(" Delete Vertex 3, Preorder traversal "); binaryTree.preOrder(); } } // definition BinaryTree Binary tree
class BinaryTree { private HeroNode root; public HeroNode getRoot() { return
root; } public void setRoot(HeroNode root) { this.root = root; } // Preorder traversal public
void preOrder() { if(this.root != null) { this.root.preOrder(); }else {
System.out.println(" The binary tree is empty , Cannot traverse "); } } // Middle order traversal public void midOrder() {
if(this.root != null) { this.root.midOrder(); }else {
System.out.println(" The binary tree is empty , Unable to traverse "); } } // Postorder traversal public void postOrder() {
if(this.root != null) { this.root.postOrder(); }else {
System.out.println(" The binary tree is empty , Unable to traverse "); } } // Delete Vertex public void delNode(int no) {
if(root != null) { // If there's only one root node , It's time to judge here root Is it to delete the node if(root.getNo() == no)
{ root = null; } else { // Recursive deletion root.delNode(no); } }else{
System.out.println(" Empty tree , Cannot delete ~"); } } } // Create first HeroNode node class HeroNode { private
int no; private String name; private HeroNode left; // default null private HeroNode
right; // default null public HeroNode(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 HeroNode getLeft() { return left; } public
void setLeft(HeroNode left) { this.left = left; } public HeroNode getRight() {
return right; } public void setRight(HeroNode right) { this.right = right; }
@Override public String toString() { return "HeroNode [no=" + no + ", name=" +
name + "]"; } // Preorder traversal public void preOrder() { System.out.println(this);// Output parent node first
// Recursive forward traversal to left subtree if(this.left != null) { this.left.preOrder(); } // Recursive preorder traversal of right subtree
if(this.right != null) { this.right.preOrder(); } } // Middle order traversal public void
midOrder() { // Recursive traversal to left subtree if(this.left != null) { this.left.midOrder(); }
System.out.println(this);// Output parent node // Recursive preorder traversal of right subtree if(this.right != null) {
this.right.midOrder(); } } // Postorder traversal public void postOrder() { // Recursive backward traversal to left subtree
if(this.left != null) { this.left.postOrder(); } // Recursive preorder traversal of right subtree if(this.right !=
null) { this.right.postOrder(); } System.out.println(this);// Output parent node } // Delete node recursively
//1. If the deleted node is a leaf node , Then delete the node //2. If the deleted node is a non leaf node , Then delete the subtree public void delNode(int no) {
// thinking /* * 1. Because our binary tree is unidirectional , So we judge whether the child node of the current node needs to be deleted , You can't judge whether the current node needs to be deleted . 2.
If the left child of the current node is not empty , And left child node Is to delete the node , It will this.left = null; And I'll go back ( End recursive delete ) 3.
If the right child of the current node is not empty , And the right child node Is to delete the node , It will this.right= null ; And I'll go back ( End recursive delete ) 4.
If the 2 And No 3 Step did not delete the node , Then we need to delete the left subtree recursively 5. If the 4 Step 2 does not delete the node , Then the right subtree should be deleted recursively . */ //2.
If the left child of the current node is not empty , And left child node Is to delete the node , It will this.left = null; And I'll go back ( End recursive delete ) if(this.left !=
null && this.left.no == no) { this.left = null; return; }
//3. If the right child of the current node is not empty , And the right child node Is to delete the node , It will this.right= null ; And I'll go back ( End recursive delete )
if(this.right != null && this.right.no == no) { this.right = null; return; }
//4. We need to delete the left subtree recursively if(this.left != null) { this.left.delNode(no); }
//5. Then the right subtree should be deleted recursively if(this.right != null) { this.right.delNode(no); } } }
4, console output

Technology
©2019-2020 Toolsou All rights reserved,
C Language programming to find a student's grade java Realize the function of grabbing red packets Random forest R Language implementation QCustomPlot series (5)- Real time dynamic curve Software testing BUG describe use C++ I want to talk to you “ Prototype mode ” ( copy / copy constructor )JS How to operate China's longest high speed rail officially opened ! The fastest way to finish the race 30.5 hour Zimi apologizes :33W Gan charger delayed due to force majeure 2021 year 2 Chinese programming language ranking