Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

directory

  • preface
  • The body of the
      1. Min () method
      1. Min (Node x) method
      1. Max () method

      1. Max (Node x) method

preface

Trees can be used to describe many things in daily life, such as the contents of books, the organizational structure of work units and so on. Tree is a very important data structure in computer. Tree storage can improve the efficiency of data storage and reading.

The body of the

For example, binary trees are used to record salary and name data of employees in a company, or ranking and name data of students in a class. How to find the data of the highest and lowest students quickly?

In that case, what to do? In fact, the following four methods can also be sorted out and defined as follows:

1. Min () method

The min () method is similar to the get () and put () methods mentioned above, and can also be implemented using the following overloaded methods:


// Find the smallest key in the tree
 
public key min(a) {
 
    return min(root).key;
 
}
Copy the code

2. Min (Node x) method

The min (Node x) method needs to find the smallest Node in the left subtree according to the location of the Node passed in. If it is empty, it directly returns empty. The specific code is as follows:

// Find the node with the smallest key in the tree
 
public Node min(Node x) {
 
    if (x == null) {
 
        return x;
 
    }
 
    Node minNode = x;
 
    while(minNode.left ! =null) {
 
        minNode = minNode.left;
 
    }
 
    return minNode;
 
}
Copy the code

3. Max () method

The Max () method is similar to the min () method mentioned above, and can also be implemented using the following overloaded methods:

// Find the smallest key in the tree
 
public key max(a) {
 
    return max(root).key;
 
}
Copy the code

4. Max (Node x) method

Max (Node x) = Max (Node x) = Max (Node x) = Max (Node x) = Max (Node x)

// Find the node with the largest key in the tree
 
public Node min(Node x) {
 
    if (x == null) {
 
        return x;
 
    }
 
    Node maxNode = x;
 
    while(maxNode.right ! =null) {
 
        maxNode = maxNode.right;
 
    }
 
    return maxNode;
 
}
Copy the code