# tree

Before we talk about binary trees, let s first understand what a tree is

Definition of tree

1. The tree is a very important data structure in our computer. At the same time, using the data structure of the tree can describe many things in real life, such as family tree, organizational structure of the unit, and so on.

2. A tree is a set of hierarchical relationships composed of n (n>=1) finite nodes. It is called a "tree" because it looks like an upside-down tree, which means that it has its roots facing up and its leaves facing down.

Diagram of the tree

Characteristics of the tree

1. Each node has zero or more child nodes;
2. The node without the parent node is the root node;
3. Each non-root node has only one parent node ;
4. Each node and its descendants can be regarded as a tree as a whole, called a subtree of the parent node of the current node ;

Related terms for trees

Degree of node:

The number of subtrees contained in a node is called the degree of the node;

Leaf node:

A node with a degree of 0 is called a leaf node, or it can be called a terminal node

Branch node:

Nodes with a degree other than 0 are called branch nodes, and can also be called non-terminal nodes

Node level:

Starting from the root node, the level of the root node is 1, the immediate successor level of the root is 2, and so on

The sequence number of the node:

Arrange the nodes in the tree into a linear sequence from the upper layer to the lower layer, and from left to right in the same layer, and weave them into continuous natural numbers.

Degree of tree:

Maximum degree of all nodes in the tree

Tree height (depth):

Maximum level of nodes in the tree

forest:

m (m>=0) a collection of disjoint trees, delete the root node of a non-empty tree, the tree becomes a forest; add a unified root node to the forest, and the forest becomes a tree

Child node:

The immediate successor node of a node is called the child node of the node, such as (H is the child node of D)

Parent node (parent node):

The immediate predecessor of a node is called the parent node of the node, such as (D is the parent node of H)

Brother node:

The child nodes of the same parent node are called sibling nodes, such as (I and J are sibling nodes)

After understanding this, I believe you have a preliminary definition of the tree. Next, let's take a look at a special type of tree: binary tree

## Binary tree

definition

A binary tree is a tree whose degree does not exceed 2 (that is, each node has at most two child nodes)

Icon

### Two special binary trees

Full binary tree

A binary tree, if the number of nodes in each layer reaches the maximum, then the binary tree is a full binary tree.

The number of nodes in each layer is 1, 2, 4, 8, 16, starting from the root node.... The rule is

2^(n-1)

Complete binary tree

A binary tree where leaf nodes can only appear in the lowermost and sub-lower layers, and the nodes of the lowermost layer are concentrated in the leftmost positions of the layer

Need to pay attention to the definition and judgment of full binary tree and complete binary tree

### The creation of ordinary binary tree

1. We use the form of linked list to create
2. We need a node class to record the left subtree, right subtree, key, value of the current node
```private  class  Node  {
public Key key; //key
public Value value; //value
public Node left; //left child node
public Node right; //right child node

public  Node (Key key, Value value, Node left, Node right)  {
this .key = key;
this .value = value;
this .left = left;
this .right = right;
}
}
Copy code```
1. Two variables are needed to record the root node and the number of elements in the tree respectively
```private Node root; //root node
Private  int N; number of elements in the tree//
copy the code```
1. Define some methods to achieve, the creation of a binary tree

Insert data into the binary tree

• public void put(Key key, Value value): Insert a key-value pair into the tree (
Call the put method overloaded below
)
• public Node put(Node x,Key key, Value value): Add a key-value pair to the specified tree x, and return the new tree after adding

Ideas:

```1. The tree is empty, the new node is used as the root node, and the number of elements is increased by one
2. The tree is not empty. Starting from the root node, determine the key of the new node and the key of the current node.
2.1 If the key of the new node is greater than the key of the current node, continue to find the right child node of the current node
2.2 If the key of the new node is smaller than the key of the current node, continue to find the left child node of the current node
2.3 If the key of the new node is equal to the key of the current node, replace the value of the current node
Copy code```

Code:

```public Node put (Node x, Key key, Value value)  {
if (x == null ) {//The tree is empty
N++;
return  new Node(key, value, null , null );
}
//The tree is not empty
int cmp = key.compareTo(x.key);
if (cmp> 0 ) { //If the key of the new node is greater than the key of the current node, continue to find the right child node of the current node
x.right = put(x.right, key, value);
} else  if (cmp < 0 ) { //If the key of the new node is smaller than the key of the current node, continue to find the left child node of the current node
x.left = put(x.left, key, value);
} else { //If the key of the new node is equal to the key of the current node, replace the value of the current node
x.value = value;
}
return x;
}
Copy code```

Find the value corresponding to the key from the tree

• public Value get(Key key): Find the value corresponding to the key from the tree (
Call the following overloaded get method
)
• public Value get(Node x, Key key): Find the value corresponding to the key in the specified tree x

Ideas:

```1. If the tree is empty, the key you are looking for cannot be found
2. If the tree is not empty, traverse from the root node to determine the key of the node to be found and the size of the key of the current node
2.1 If the key of the node to be searched is greater than the key of the current node, continue to find the right child node of the current node
2.2 If the key of the node to be searched is smaller than the key of the current node, continue to find the left child node of the current node
2.3 If the key of the node to be searched is equal to the key of the current node, the value of the current node is returned
Copy code```

Code:

```    public Value get (Node x, Key key)  {
//When the tree is empty
if (x == null ) {
return  null ;
}
//The tree is not empty
int cmp = key.compareTo(x.key);
if (cmp> 0 ) { //If the key to be searched is larger than the key of the current node, continue to find the right child node of the current node
return get(x.right, key);
} else  if (cmp < 0 ) { //If the key to be searched is smaller than the key of the current node, continue to find the left child node of the current node
return get(x.left, key);
} else { //If the key to be found is equal to the key of the current node, replace the value of the current node
return x.value;
}

}
Copy code```

Delete the value corresponding to key from the tree

• public void delete(Key key): Delete the value corresponding to key from the tree (
Call the delete method overloaded below
)
• public Node delete(Node x, Key key): In the specified tree x, delete the value corresponding to the key

Ideas:

```1. Find the deleted node (the same idea as the get method), and reduce the number of elements by one
2. Find the smallest node minNode in the right subtree of the deleted node
2.1 Consider the possible location of the node to be deleted
2.1.1 The node to be deleted does not have a left child node
2.1.2 The node to be deleted has no right child node
2.1.3 The node to be deleted has a left child node and a right child node
3. Delete the smallest node in the right subtree
4. Let the left subtree of the deleted node become the left subtree of the smallest node minNode, and let the right subtree of the deleted node become the right subtree of the smallest node minNode
5. Let the parent node of the deleted node point to the smallest node minNode
Copy code```

Code:

``` public Node delete (Node x, Key key)  {
//The tree is empty
if (x == null ) {
return  null ;
}
//The tree is not empty
int cmp = key.compareTo(x.key);
if (cmp> 0 ) { //If the key to be searched is larger than the key of the current node, continue to find the right child node of the current node
x.right = delete(x.right, key);
} else  if (cmp < 0 ) { //If the key to be searched is smaller than the key of the current node, continue to find the left child node of the current node
x.left = delete(x.left, key);
} else { //If the key to be searched is equal to the key of the current node, the node to be deleted is found
/*
The delete operation to be performed after finding the node to be deleted
0. The number of elements minus one
1. Find the smallest node minNode in the right subtree of the deleted node
1.1 Consider the possible location of the node to be deleted
1.1.1 The node to be deleted does not have a left child node
1.1.2 The node to be deleted has no right child node
1.1.3 The node to be deleted has a left child node and a right child node
2. Delete the smallest node in the right subtree
3. Let the left subtree of the deleted node become the left subtree of the smallest node minNode,
4. Let the right subtree of the deleted node be the right subtree of the smallest node minNode
5. Let the parent node of the deleted node point to the smallest node minNode
*/
//The number of elements minus one
N--;
//The node to be deleted has no left child node
if (x.left == null ) {
return x.right;
}
//The node to be deleted has no right child node
if (x.right == null ) {
return x.left;
}
//Find the smallest node in the right subtree of the node to be deleted
Node minNode = x.right;
//At the end of the loop, the smallest node of the right subtree of the node to be deleted is found minNode
while (minNode.left != null ) {
minNode = minNode.left;
}
//Delete the smallest
node in the right subtree//Start traversing from the right subtree of the node to be deleted, and keep looking for the left subtree
Node temp = x.right;
while (temp.left != null ) {
if (temp.left.left == null ) {
temp.left = null ; //Deletion is implemented here
} else {
temp = temp.left;
}
}
//Let the left subtree of the deleted node become the left subtree of the smallest node minNode
minNode.left = x.left;
//Let the right subtree of the deleted node become the right subtree of the smallest node minNode
minNode.right = x.right;
//Let the parent node of the deleted node point to the smallest node minNode
x = minNode; //Give all the contents of minNode to x, which is equivalent to replacing minNode with the position of node x

}

return x;
copy code```

Get the number of elements in the tree

• public int size(): Get the number of elements in the tree

Code:

```    //Get the number of elements in the tree
public  int  size ()  {
return N;
}
Copy code```

API for complete binary tree creation

```package com.study.tree;

import com.study.queue.queueAPI;

public  class  BinaryTreeAPI < Key  extends  Comparable < Key >, Value > {
//node class
private  class  Node  {
public Key key; //key
public Value value; //value
public Node left; //left child node
public Node right ; //Right child node

public  Node (Key key, Value value, Node left, Node right)  {
this .key = key;
this .value = value;
this .left = left;
this .right = right;
}
}
private Node root; //Root node
private  int N; //Number of elements in the tree

//Get the number of elements in the tree
public  int  size ()  {
return N;
}

//Add element key-value to the entire tree
//Call the overload method of
put public  void  put (Key key, Value value)  {
root = put(root, key, value);
}

/**
* Add key-value to the specified tree, and return the new tree after adding elements
* 1. The tree is empty, and the new node is used as the root node
* 2. The tree is not empty. Starting from the root node, determine the key of the new node and the key of the current node.
* 2.1 If the key of the new node is greater than the key of the current node, continue to find the right child node of the current node
* 2.2 If the key of the new node is smaller than the key of the current node, continue to find the left child node of the current node
* 2.3 If the key of the new node is equal to the key of the current node, replace the value of the current node
*/
public Node put (Node x, Key key, Value value)  {
if (x == null ) {//The tree is empty
N++;
return  new Node(key, value, null , null );
}
//The tree is not empty
int cmp = key.compareTo(x.key);
if (cmp> 0 ) { //If the key of the new node is greater than the key of the current node, continue to find the right child node of the current node
x.right = put(x.right, key, value);
} else  if (cmp < 0 ) { //If the key of the new node is smaller than the key of the current node, continue to find the left child node of the current node
x.left = put(x.left, key, value);
} else { //If the key of the new node is equal to the key of the current node, replace the value of the current node
x.value = value;
}
return x;
}

//Query the value corresponding to the specified key in the entire tree
public Value get (Key key)  {
return get(root, key);
}

//Find the value corresponding to the key in the specified tree x
public Value get (Node x, Key key)  {
//When the tree is empty
if (x == null ) {
return  null ;
}
//The tree is not empty
int cmp = key.compareTo(x.key);
if (cmp> 0 ) { //If the key to be searched is larger than the key of the current node, continue to find the right child node of the current node
return get(x.right, key);
} else  if (cmp < 0 ) { //If the key to be searched is smaller than the key of the current node, continue to find the left child node of the current node
return get(x.left, key);
} else { //If the key to be found is equal to the key of the current node, replace the value of the current node
return x.value;
}

}

//Delete the value corresponding to the key in the tree
public  void  delete (Key key)  {
delete(root, key);
}

/**
* Delete the value corresponding to the key in the specified tree, and return the deleted new tree
* 1. Find the deleted node;
* 2. Find the smallest node minNode in the right subtree of the deleted node
* 3. Delete the smallest node in the right subtree
* 4. Let the left subtree of the deleted node become the left subtree of the smallest node minNode,
* Let the right subtree of the deleted node become the right subtree of the smallest node minNode
* 5. Let the parent node of the deleted node point to the smallest node minNode
*/
public Node delete (Node x, Key key)  {
//The tree is empty
if (x == null ) {
return  null ;
}
//The tree is not empty
int cmp = key.compareTo(x.key);
if (cmp> 0 ) { //If the key to be searched is larger than the key of the current node, continue to find the right child node of the current node
x.right = delete(x.right, key);
} else  if (cmp < 0 ) { //If the key to be searched is smaller than the key of the current node, continue to find the left child node of the current node
x.left = delete(x.left, key);
} else { //If the key to be searched is equal to the key of the current node, the node to be deleted is found
/*
The delete operation to be performed after finding the node to be deleted
0. The number of elements minus one
1. Find the smallest node minNode in the right subtree of the deleted node
1.1 Consider the possible location of the node to be deleted
1.1.1 The node to be deleted does not have a left child node
1.1.2 The node to be deleted has no right child node
1.1.3 The node to be deleted has a left child node and a right child node
2. Delete the smallest node in the right subtree
3. Let the left subtree of the deleted node become the left subtree of the smallest node minNode,
4. Let the right subtree of the deleted node be the right subtree of the smallest node minNode
5. Let the parent node of the deleted node point to the smallest node minNode
*/
//The number of elements minus one
N--;
//The node to be deleted has no left child node
if (x.left == null ) {
return x.right;
}
//The node to be deleted has no right child node
if (x.right == null ) {
return x.left;
}
//Find the smallest node in the right subtree of the node to be deleted
Node minNode = x.right;
//At the end of the loop, the smallest node of the right subtree of the node to be deleted is found minNode
while (minNode.left != null ) {
minNode = minNode.left;
}
//Delete the smallest
node in the right subtree//Start traversing from the right subtree of the node to be deleted, and keep looking for the left subtree
Node temp = x.right;
while (temp.left != null ) {
if (temp.left.left == null ) {
temp.left = null ; //Deletion is implemented here
} else {
temp = temp.left;
}
}
//Let the left subtree of the deleted node become the left subtree of the smallest node minNode
minNode.left = x.left;
//Let the right subtree of the deleted node become the right subtree of the smallest node minNode
minNode.right = x.right;
//Let the parent node of the deleted node point to the smallest node minNode
x = minNode; //Give all the contents of minNode to x, which is equivalent to replacing minNode with the position of node x

}

return x;
}

}

Copy code```

### The largest key and smallest key in a binary tree

Ideas

Because we created it based on the fact that the left subtree of the root node is smaller than the root node, and the right subtree of the root node is larger than the root node , so we look for the right subtree when we find the largest key. The least key is to find the left subtree

Method implementation (I also put these in the API created by the binary tree)

```    //Find the largest key in the tree
public Key max ()  {
Node minNode = root; //Use a new node to prevent root from being modified by us
//The tree is empty
if (minNode == null ) {
return  null ;
}
//The tree is not empty
while (minNode.right != null ) {
if (minNode.right.right == null ) {
return minNode.right.key;
} else {
minNode = minNode.right;
}
}
return minNode.key;
}

//Find the smallest key in the tree
public Key min ()  {
Node maxNode = root;
//The tree is empty
if (maxNode == null ) {
return  null ;
}
//The tree is not empty
while (maxNode.left != null ) {
if (maxNode.left.left == null ) {
return maxNode.left.key;
} else {
maxNode = maxNode.left;
}
}
return maxNode.key;
}
Copy code```

### Traversal of binary tree

The following binary tree traversal will illustrate three common traversal methods and an advanced traversal method

#### Preorder traversal

Traversal order: root node -> left subtree -> right subtree

Ideas:

1. Put the key of the current node into the queue
2. Find the left subtree of the current node, if not empty, traverse the left subtree recursively
3. Find the right subtree of the current node, if not empty, traverse the right subtree recursively
```    //Pre-order traversal: first visit the root node, then the left subtree, then the right subtree
//Get all the keys of the entire tree
public queueAPI<Key> preErgodic ()  {
queueAPI<Key> queue = new queueAPI<>();
preErgodic(root, queue);
return queue;
}

//Get all the keys of the specified tree and put them in the queue
public  void  preErgodic (Node x, queueAPI<Key> queue)  {
if (x == null ) {
return ;
}
//Put the key of the x node in the queue
queue.enqueue(x.key);

//Recursively traverse the left subtree of x
if (x.left != null ) {
preErgodic(x.left, queue);
}
//Recursively traverse the right subtree of x
if (x.right != null ) {
preErgodic(x.right, queue);
}
}
Copy code```

#### In-order traversal

Traversal order: left subtree -> root node -> right subtree

Ideas:

1. Find the left subtree of the current node, if not empty, traverse the left subtree recursively
2. Put the key of the current node into the queue;
3. Find the right subtree of the current node, if not empty, traverse the right subtree recursively
```     //Mid-order traversal: first visit the left subtree, then the root node, then the right subtree
public queueAPI<Key> midErgodic ()  {
queueAPI<Key> queue = new queueAPI<>();
midErgodic(root, queue);
return queue;
}

public  void  midErgodic (Node x, queueAPI<Key> queue)  {
if (x == null ) {
return ;
}
//Recursively traverse the left subtree and always find the leftmost element
if (x.left != null ) {
midErgodic(x.left, queue);
}
//When x.left is equal to null, the current node x is the leftmost element, directly added to the queue
queue.enqueue(x.key);
//Recursively traverse the right subtree
if (x.right != null ) {
midErgodic(x.right, queue);
}
}
Copy code```

#### Post-order traversal

Traversal order: left subtree -> right subtree -> root node

Ideas:

1. Find the left subtree of the current node, if not empty, traverse the left subtree recursively
2. Find the right subtree of the current node, if not empty, traverse the right subtree recursively
3. Put the key of the current node into the queue;
```    //Post-order traversal: first visit the left subtree, then the right subtree, and then the root node
public queueAPI<Key> afterErgodic ()  {
queueAPI<Key> queue = new queueAPI<>();
afterErgodic(root, queue);
return queue;
}

public  void  afterErgodic (Node x, queueAPI<Key> queue)  {
if (x == null ) {
return ;
}
//Recursively traverse the left subtree
if (x.left != null ) {
afterErgodic(x.left, queue);
}
//Recursively traverse the right subtree
if (x.right != null ) {
afterErgodic(x.right, queue);
}
//When x.left is equal to null, yes, the current node x is the leftmost element, directly added to the queue
queue.enqueue(x.key);

}
Copy code```

#### Sequence traversal

Traversal sequence: Start from the root node (first layer), and then go down to get the values of all nodes in each layer.

Ideas:

1. Create a queue to store nodes, first put the head node into
2. Every time a node in the queue is popped up, get the key of the node
3. See if the pop-up node has a left child node, put it in
4. See if the pop-up node has a right child node, put it in

Diagram

```public queueAPI<Key> layerErgodic ()  {
queueAPI<Key> queue = new queueAPI<>(); //Store sorted elements
queueAPI<Node> nodes = new queueAPI<>(); //Store nodes
//First put the head node in the node queue
nodes.enqueue(root);
//Traverse the nodes queue
while (!nodes.isEmpty()){
//Every time the first node of the node queue pops up
Node node = nodes.dequeue();
//Put the key of the popped node into the sorted queue
queue.enqueue(node.key);
//See if the pop-up node has a left child node, put it in the node queue
if there is one if (node.left!= null ){
nodes.enqueue(node.left);
}
//
Check whether the pop-up node has a right child node, and put it in the node queue if (node.right!= null ){
nodes.enqueue(node.right);
}
}
return queue;
}
Copy code```

### Depth of binary tree

Depth : the number of nodes on the longest path from the root node of the tree to the farthest leaf node

Ideas:

1. If the root node is empty, the maximum depth is 0;
2. Calculate the maximum depth of the left subtree;
3. Calculate the maximum depth of the right subtree;
4. The maximum depth of the current tree = the greater of the maximum depth of the left subtree and the maximum depth of the right subtree+1

Code:

``` public  int  maxDepth () {
return maxDepth(root);
}
//Find the maximum depth of the tree where the node is located
public  int  maxDepth (Node x) {
if (x== null ){
return  0 ;
}
int left = 0 ; //the maximum depth of the left subtree
int right = 0 ; //the maximum depth of the right subtree
int max = 0 ; //the larger of the left and right subtrees
if (x.left!= null ) { //Calculate the maximum depth of the left subtree;
left=maxDepth(x.left);
}
if (x.right!= null ){ //Calculate the maximum depth of the right subtree;
right = maxDepth(x.right);
}
max = left>right?left+ 1 :right+ 1 ;
return max;

}
Copy code```

## Binary tree summary

The implementation of the above method is summarized in a binary tree implementation API, the total code is:

```package com.study.tree;

import com.study.queue.queueAPI;

public  class  BinaryTreeAPI < Key  extends  Comparable < Key >, Value > {
private Node root; //root node
private  int N; //number of elements in the tree

//Get the number of elements in the tree
public  int  size ()  {
return N;
}

//Add element key-value to the entire tree
//Call the overload method of
put public  void  put (Key key, Value value)  {
root = put(root, key, value);
}

/**
* Add key-value to the specified tree, and return the new tree after adding elements
* 1. The tree is empty, and the new node is used as the root node
* 2. The tree is not empty. Starting from the root node, determine the key of the new node and the key of the current node.
* 2.1 If the key of the new node is greater than the key of the current node, continue to find the right child node of the current node
* 2.2 If the key of the new node is smaller than the key of the current node, continue to find the left child node of the current node
* 2.3 If the key of the new node is equal to the key of the current node, replace the value of the current node
*/
public Node put (Node x, Key key, Value value)  {
if (x == null ) {//The tree is empty
N++;
return  new Node(key, value, null , null );
}
//The tree is not empty
int cmp = key.compareTo(x.key);
if (cmp> 0 ) { //If the key of the new node is greater than the key of the current node, continue to find the right child node of the current node
x.right = put(x.right, key, value);
} else  if (cmp < 0 ) { //If the key of the new node is smaller than the key of the current node, continue to find the left child node of the current node
x.left = put(x.left, key, value);
} else { //If the key of the new node is equal to the key of the current node, replace the value of the current node
x.value = value;
}
return x;
}

//Query the value corresponding to the specified key in the entire tree
public Value get (Key key)  {
return get(root, key);
}

//Find the value corresponding to the key in the specified tree x
public Value get (Node x, Key key)  {
//When the tree is empty
if (x == null ) {
return  null ;
}
//The tree is not empty
int cmp = key.compareTo(x.key);
if (cmp> 0 ) { //If the key to be searched is larger than the key of the current node, continue to find the right child node of the current node
return get(x.right, key);
} else  if (cmp < 0 ) { //If the key to be searched is smaller than the key of the current node, continue to find the left child node of the current node
return get(x.left, key);
} else { //If the key to be found is equal to the key of the current node, replace the value of the current node
return x.value;
}

}

//Delete the value corresponding to the key in the tree
public  void  delete (Key key)  {
delete(root, key);
}

/**
* Delete the value corresponding to the key in the specified tree, and return the deleted new tree
* 1. Find the deleted node;
* 2. Find the smallest node minNode in the right subtree of the deleted node
* 3. Delete the smallest node in the right subtree
* 4. Let the left subtree of the deleted node become the left subtree of the smallest node minNode,
* Let the right subtree of the deleted node become the right subtree of the smallest node minNode
* 5. Let the parent node of the deleted node point to the smallest node minNode
*/
public Node delete (Node x, Key key)  {
//The tree is empty
if (x == null ) {
return  null ;
}
//The tree is not empty
int cmp = key.compareTo(x.key);
if (cmp> 0 ) { //If the key to be searched is larger than the key of the current node, continue to find the right child node of the current node
x.right = delete(x.right, key);
} else  if (cmp < 0 ) { //If the key to be searched is smaller than the key of the current node, continue to find the left child node of the current node
x.left = delete(x.left, key);
} else { //If the key to be searched is equal to the key of the current node, the node to be deleted is found
/*
The delete operation to be performed after finding the node to be deleted
0. The number of elements minus one
1. Find the smallest node minNode in the right subtree of the deleted node
1.1 Consider the possible location of the node to be deleted
1.1.1 The node to be deleted does not have a left child node
1.1.2 The node to be deleted has no right child node
1.1.3 The node to be deleted has a left child node and a right child node
2. Delete the smallest node in the right subtree
3. Let the left subtree of the deleted node become the left subtree of the smallest node minNode,
4. Let the right subtree of the deleted node be the right subtree of the smallest node minNode
5. Let the parent node of the deleted node point to the smallest node minNode
*/
//The number of elements minus one
N--;
//The node to be deleted has no left child node
if (x.left == null ) {
return x.right;
}
//The node to be deleted has no right child node
if (x.right == null ) {
return x.left;
}
//Find the smallest node in the right subtree of the node to be deleted
Node minNode = x.right;
//At the end of the loop, the smallest node of the right subtree of the node to be deleted is found minNode
while (minNode.left != null ) {
minNode = minNode.left;
}
//Delete the smallest
node in the right subtree//Start traversing from the right subtree of the node to be deleted, and keep looking for the left subtree
Node temp = x.right;
while (temp.left != null ) {
if (temp.left.left == null ) {
temp.left = null ; //Deletion is implemented here
} else {
temp = temp.left;
}
}
//Let the left subtree of the deleted node become the left subtree of the smallest node minNode
minNode.left = x.left;
//Let the right subtree of the deleted node become the right subtree of the smallest node minNode
minNode.right = x.right;
//Let the parent node of the deleted node point to the smallest node minNode
x = minNode; //Give all the contents of minNode to x, which is equivalent to replacing minNode with the position of node x

}

return x;
}

//Find the largest key in the tree
public Key max ()  {
Node minNode = root; //Use a new node to prevent root from being modified by us
//The tree is empty
if (minNode == null ) {
return  null ;
}
//The tree is not empty
while (minNode.right != null ) {
if (minNode.right.right == null ) {
return minNode.right.key;
} else {
minNode = minNode.right;
}
}
return minNode.key;
}

//Find the smallest key in the tree
public Key min ()  {
Node maxNode = root;
//The tree is empty
if (maxNode == null ) {
return  null ;
}
//The tree is not empty
while (maxNode.left != null ) {
if (maxNode.left.left == null ) {
return maxNode.left.key;
} else {
maxNode = maxNode.left;
}
}
return maxNode.key;
}

//Pre-order traversal: first visit the root node, then the left subtree, then the right subtree
//Get all the keys of the entire tree
public queueAPI<Key> preErgodic ()  {
queueAPI<Key> queue = new queueAPI<>();
preErgodic(root, queue);
return queue;
}

//Get all the keys of the specified tree and put them in the queue
public  void  preErgodic (Node x, queueAPI<Key> queue)  {
if (x == null ) {
return ;
}
//Put the key of the x node in the queue
queue.enqueue(x.key);

//Recursively traverse the left subtree of x
if (x.left != null ) {
preErgodic(x.left, queue);
}
//Recursively traverse the right subtree of x
if (x.right != null ) {
preErgodic(x.right, queue);
}
}

//Mid-order traversal: first visit the left subtree, then the root node, then the right subtree
public queueAPI<Key> midErgodic ()  {
queueAPI<Key> queue = new queueAPI<>();
midErgodic(root, queue);
return queue;
}

public  void  midErgodic (Node x, queueAPI<Key> queue)  {
if (x == null ) {
return ;
}
//Recursively traverse the left subtree and always find the leftmost element
if (x.left != null ) {
midErgodic(x.left, queue);
}
//When x.left is equal to null, the current node x is the leftmost element, directly added to the queue
queue.enqueue(x.key);
//Recursively traverse the right subtree
if (x.right != null ) {
midErgodic(x.right, queue);
}
}

//Post-order traversal: first visit the left subtree, then the right subtree, and then the root node
public queueAPI<Key> afterErgodic ()  {
queueAPI<Key> queue = new queueAPI<>();
afterErgodic(root, queue);
return queue;
}

public  void  afterErgodic (Node x, queueAPI<Key> queue)  {
if (x == null ) {
return ;
}
//Recursively traverse the left subtree
if (x.left != null ) {
afterErgodic(x.left, queue);
}
//Recursively traverse the right subtree
if (x.right != null ) {
afterErgodic(x.right, queue);
}
//When x.left is equal to null, yes, the current node x is the leftmost element, directly added to the queue
queue.enqueue(x.key);

}

//Layer sequence traversal
//1. Create a queue to store nodes, first put the head node in
//2. Each time a node in the queue is popped,
//3. See if the popped node has a left Child node, put it in
if there is one//4.
Check if the pop-up node has a right child node, put it in public queueAPI<Key> layerErgodic ()  {
queueAPI<Key> queue = new queueAPI<>(); //Store sorted elements
queueAPI<Node> nodes = new queueAPI<>(); //Store nodes
//First put the head node in the node queue
nodes.enqueue(root);
//Traverse the nodes queue
while (!nodes.isEmpty()){
//Every time the first node of the node queue pops up
Node node = nodes.dequeue();
//Put the key of the popped node into the sorted queue
queue.enqueue(node.key);
//See if the pop-up node has a left child node, put it in the node queue
if there is one if (node.left!= null ){
nodes.enqueue(node.left);
}
//
Check whether the pop-up node has a right child node, and put it in the node queue if (node.right!= null ){
nodes.enqueue(node.right);
}
}
return queue;
}
//Find the maximum depth of the entire tree
//1. Find
the maximum depth of the left subtree //2. Find the maximum depth of the right subtree
//3. Take the maximum value of the left subtree and the right subtree + 1 Depth
public  int  maxDepth () {
return maxDepth(root);
}
//Find the maximum depth of the tree where the node is located
public  int  maxDepth (Node x) {
if (x== null ){
return  0 ;
}
int left = 0 ; //the maximum depth of the left subtree
int right = 0 ; //the maximum depth of the right subtree
int max = 0 ; //the larger of the left and right subtrees
if (x.left!= null ) {
left=maxDepth(x.left);
}
if (x.right!= null ){
right = maxDepth(x.right);
}
max = left>right?left+ 1 :right+ 1 ;
return max;

}
//node class
private  class  Node  {
public Key key; //key
public Value value; //value
public Node left; //left child node
public Node right; //right child node

public  Node (Key key, Value value, Node left, Node right)  {
this .key = key;
this .value = value;
this .left = left;
this .right = right;
}
}

}

Copy code```

Let's take another test code:

```package com.study.tree;

import com.study.queue.queueAPI;

public  class  BinaryTreeTest  {
public  static  void  main (String[] args)  {
BinaryTreeAPI<Integer, String> bt = new BinaryTreeAPI<>();
bt.put( 5 , "Zhang San" );
bt.put( 2 , " " );
bt.put( 7 , "Wang Five" );
bt.put( 1 , "Zhao Liu" );
bt.put( 4 , "Wu Xin" );
bt.put( 6 , "Zhao Si " );
bt.put( 8 , "Wu Lei" );
bt.put( 3 , " " );
System.out.println( "After adding elements, the total number of elements is:" +bt.size());
System.out.println(bt.get( 2 ));
bt.delete( 2 );
System.out.println( "After deleting elements, the total number of elements is:" +bt.size());
System.out.println( "After deleting the element, the value of the element with key 2 is: " +bt.get( 2 ));
bt.put( 2 , " " );
Integer min = bt.min();
System.out.println( "The element with the smallest key is:" +min);
Integer max = bt.max();
System.out.println( "The element with the largest key is:" +max);
System.out.println( "Preorder traversal:" );
queueAPI<Integer> prequeue = bt.preErgodic();
for (Integer i: prequeue) {
System.out.println(i+ "---" +bt.get(i));
}
System.out.println( "In-order traversal:" );
queueAPI<Integer> queue = bt.midErgodic();
for (Integer i: queue) {
System.out.println(i+ "---" +bt.get(i));
}
System.out.println( "Post-order traversal:" );
queueAPI<Integer> afqueue = bt.afterErgodic();
for (Integer i: afqueue) {
System.out.println(i+ "---" +bt.get(i));
}
System.out.println( "Sequence traversal:" );
queueAPI<Integer> layerqueue = bt.layerErgodic();
for (Integer i: layerqueue) {
System.out.println(i+ "---" +bt.get(i));
}
int maxDepth = bt.maxDepth();
System.out.println( "The depth of the tree is:" +maxDepth);
}
}

Copy code```

Add elements to the tree, delete elements in the tree, and get the value of the specific key in the tree

Preorder traversal

In-order traversal

Post-order traversal

Sequence traversal

Tree depth