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

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.

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 upsidedown tree, which means that it has its roots facing up and its leaves facing down.
Diagram of the tree
Characteristics of the tree
 Each node has zero or more child nodes;
 The node without the parent node is the root node;
 Each nonroot node has only one parent node ;
 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
The number of subtrees contained in a node is called the degree of the node;
A node with a degree of 0 is called a leaf node, or it can be called a terminal node
Nodes with a degree other than 0 are called branch nodes, and can also be called nonterminal nodes
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
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.
Maximum degree of all nodes in the tree
Maximum level of nodes in the tree
m (m>=0) a collection of disjoint trees, delete the root node of a nonempty tree, the tree becomes a forest; add a unified root node to the forest, and the forest becomes a tree
The immediate successor node of a node is called the child node of the node, such as (H is the child node of D)
The immediate predecessor of a node is called the parent node of the node, such as (D is the parent node of H)
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
Complete binary tree
A binary tree where leaf nodes can only appear in the lowermost and sublower 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
 We use the form of linked list to create
 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
 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
 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 keyvalue pair into the tree (Call the put method overloaded below)
 public Node put(Node x,Key key, Value value): Add a keyvalue 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 keyvalue to the entire tree
//Call the overload method of
put public void put (Key key, Value value) {
root = put(root, key, value);
}
/**
* Add keyvalue 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:
 Put the key of the current node into the queue
 Find the left subtree of the current node, if not empty, traverse the left subtree recursively
 Find the right subtree of the current node, if not empty, traverse the right subtree recursively
//Preorder 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
Inorder traversal
Traversal order: left subtree > root node > right subtree
Ideas:
 Find the left subtree of the current node, if not empty, traverse the left subtree recursively
 Put the key of the current node into the queue;
 Find the right subtree of the current node, if not empty, traverse the right subtree recursively
//Midorder 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
Postorder traversal
Traversal order: left subtree > right subtree > root node
Ideas:
 Find the left subtree of the current node, if not empty, traverse the left subtree recursively
 Find the right subtree of the current node, if not empty, traverse the right subtree recursively
 Put the key of the current node into the queue;
//Postorder 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:
 Create a queue to store nodes, first put the head node into
 Every time a node in the queue is popped up, get the key of the node
 See if the popup node has a left child node, put it in
 See if the popup 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 popup 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 popup 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:
 If the root node is empty, the maximum depth is 0;
 Calculate the maximum depth of the left subtree;
 Calculate the maximum depth of the right subtree;
 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 keyvalue to the entire tree
//Call the overload method of
put public void put (Key key, Value value) {
root = put(root, key, value);
}
/**
* Add keyvalue 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;
}
//Preorder 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);
}
}
//Midorder 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);
}
}
//Postorder 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 popup 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 popup 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 popup 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( "Inorder traversal:" );
queueAPI<Integer> queue = bt.midErgodic();
for (Integer i: queue) {
System.out.println(i+ "" +bt.get(i));
}
System.out.println( "Postorder 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
Inorder traversal
Postorder traversal
Sequence traversal
Tree depth