Data structure and algorithm--binary tree

Data structure and algorithm--binary tree

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