1. Analyze the characteristics of elements in binary sort tree
The binary sort tree must ensure that the elements can be compared in size
How to ensure that elements can be compared in size?
Implement comparator interface
- implement the Comparable interface and rewrite the compareTo method -- internal comparator
- implement Comparator interface -- external Comparator
Usage scenario: if you don't want to use the defined comparison rules, use the temporary or new comparison rules. In this case, use the implementation of the interface to define the comparison rules outside the class
Scenario 1: some student objects are required to be stored in the collection
1. Arrange the students in the collection in ascending order according to their student numbers
2. Then arrange them in descending order according to the age of students
3. Based on the above, the list set is arranged in ascending order by name
import java.util.Objects;
//Student class
//Provide parameterless construction, override the get set method, and override toString
//Rewrite equals and hashCode by id (if the result of equals is true for two objects, the hashCode values of the two objects must be equal)
public class Student implements Comparable<Student>{
private Integer id;
private String name;
private Integer age;
public Student() {
}
public Student(Integer id, String name, Integer age) {
this.id = id;
this.name = name;
this.age = age;
}
public Integer getId() {
return id;
}
public void setId(Integer id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getAge() {
return age;
}
public void setAge(Integer age) {
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"id=" + id +
", name='" + name + '\'' +
", age=" + age +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Student student = (Student) o;
return id.equals(student.id);
}
@Override
public int hashCode() {
return Objects.hash(id);
}
/**Override the method of Comparable, which is used to define comparison rules*/
@Override
public int compareTo(Student o) {
//If a positive number is returned, the current object is larger than the current student object
//If a negative number is returned, the current object is smaller than the current student object
//Equality means consistency
return id-o.getId();//The current object is written in the front and another object is written in the back. The default is ascending, and the descending order is the opposite
}
}Using the comparable interface of the internal comparator, rewrite the compareTo method to arrange the student numbers in ascending order
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
/*This class is used to arrange tests in ascending order by student number*/
/*Use internal comparator*/
//Create a StudentTest and store the students in the list array
public class StudentTest {
public static void main(String[] args) {
//1. Create List collection
List<Student> list=new ArrayList<>();
//2. Create student objects and give student numbers in random order
Student student1 = new Student(1001,"Kobe",24);
Student student2 = new Student(1007,"Lisa",22);
Student student3 = new Student(1003,"James",26);
Student student4 = new Student(1002,"Jack",23);
Student student5 = new Student(1005,"Rose",28);
//3. Deposit in the list
list.add(student1);
list.add(student2);
list.add(student3);
list.add(student4);
list.add(student5);
//4. Traverse the list
for (Student student:list){
System.out.println(student);
}
//5. In ascending order of student number
//5.1 using the sort method, the default parameter is list. You must ensure that the elements in the collection implement the Comparable interface before sorting
Collections.sort(list);
//6. Add a delimiter to test
System.out.println("--------------------");
//7. Traverse the list and print here
for (Student student:list){
System.out.println(student);
}
Use the external Comparator to implement the Comparator interface and arrange the students' ages in descending order
// 8. Provide an anonymous inner class in descending order by age
Collections.sort(list, new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
//Because it needs to be in descending order, the back minus the front
return o2.getAge()-o1.getAge();
}
});
//Traverse again
for (Student student:list){
System.out.println(student);
}
Sort according to the names of students. Since they are all of String type, the comparTo method is called for comparison
//Sort by student name -- when comparing rules, compare by elements of reference type
Collections.sort(list, new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
return o1.getName().compareTo(o2.getName());
}
});
for (Student student:list){
System.out.println(student);
}Scenario 2:
There are 35 students in a class. Write a code in java to sort the students according to their age: if they are the same age, they are sorted according to their height (high to low), and if they are the same height, they are sorted according to their weight (light to heavy)
import java.util.Objects;
/**There are 35 students in a class. Write a piece of code in java to sort the students according to their age:
* If the age is the same, it is sorted by height (high to low), if the height is the same, it is sorted by weight (light to heavy)*/
public class Stu implements Comparable<Stu>{
private Integer id;
private String name;
private Integer age;
private Double height;
private Double weight;
public Stu() {
}
public Stu(Integer id, String name, Integer age, Double height, Double weight) {
this.id = id;
this.name = name;
this.age = age;
this.height = height;
this.weight = weight;
}
public Integer getId() {
return id;
}
public void setId(Integer id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getAge() {
return age;
}
public void setAge(Integer age) {
this.age = age;
}
public Double getHeight() {
return height;
}
public void setHeight(Double height) {
this.height = height;
}
public Double getWeight() {
return weight;
}
public void setWeight(Double weight) {
this.weight = weight;
}
@Override
public String toString() {
return "Stu{" +
"id=" + id +
", name='" + name + '\'' +
", age=" + age +
", height=" + height +
", weight=" + weight +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Stu stu = (Stu) o;
return id.equals(stu.id);
}
@Override
public int hashCode() {
return Objects.hash(id);
}
@Override
public int compareTo(Stu o) {
if (!(o.getAge() ==age)){
return o.getAge().compareTo(age); //In descending order of age
}
//If they are of equal age, they are sorted according to their height (from high to low)
if (!(height==o.getHeight())){
return o.getHeight().compareTo(height);
}
//If the height is equal, they are sorted by weight
return weight.compareTo(o.getWeight());
}
}import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class StuTest {
public static void main(String[] args) {
List<Stu> list = new ArrayList<>();
Stu stu1 = new Stu(1001, "tom", 21, 170.5, 55.5);
Stu stu2 = new Stu(1004, "tomy", 22, 170.5, 60.5);
Stu stu3 = new Stu(1006, "amy", 21, 170.5, 80.5);
Stu stu4 = new Stu(1002, "jack", 22, 160.5, 70.5);
Stu stu5 = new Stu(1003, "rose", 23, 150.5, 55.5);
list.add(stu1);
list.add(stu2);
list.add(stu3);
list.add(stu4);
list.add(stu5);
Collections.sort(list);
for (Stu stu:list){
System.out.println(stu);
}
}
}2. Main functions
2.1 adding elements to a binary tree
2.1.1 define binary sort tree, pay attention to element type and ensure sorting
2.1.2 define the internal class Node, which represents the Node object
2.1.3 define the add method to complete the operation of adding elements
/**Binary sort tree
* E Represents the interface type. The element type stored to the binary system can be interface type or class type
* No matter what type, ensure that the E interface is implemented*/
public class BinarySearchTree <E extends Comparable<E>>{
//1. Define the root node (there is only one)
private Node root;
//5. Define length (according to business requirements)
int size;
//6. Add method
/**Add element:
* Two cases:
* 1.root null, make the new element root
* 2.root Not null, add a new element to a node (judging from the root node)*/
public boolean add(E e){
//7. Judge whether the root node is null
if (root==null){ //If the element equals null, it becomes a new node
root=new Node(e);//Encapsulate as root node
size++;
return true;
}
//8. If the root is not null, add a new element to a node (judging from the root node)
return root.append(e);
}
//2. Create Node internal class
private class Node{
//3. Create element attributes
private E data; //Element object
private Node left;//Left subtree
private Node right;//Right subtree
//4. Create structure with parameters
Node(E e){
data=e;
}
//9. Auto generate append method
public boolean append(E e) {
//10. Judge whether e is equal to root. If it is equal, return false. If not, judge whether it is greater than or less than,
// Here is the compareTo method. If it is equal to 0, it will prove that it is equal
if(e.compareTo(data)==0){//The nodes of all elements are saved in data, so data is used for comparison
return false;//Add failed
}else if (e.compareTo(data)<0){ //It indicates that the new element is smaller than the current element and is placed in the left subtree
if (left==null){//If the current left is empty, the new node will become the left subtree
left=new Node(e);//e stands for a new element
size++;
return true;//Added successfully
}
//If left is not null
return left.append(e);//Because the append method returns boolean, it returns directly
}else{//Add element to right subtree
if (right==null){
right = new Node(e);
size++;
return true;
}
return right.append(e);
}
}
}
}public class BinarySearchTreeTest {
public static void main(String[] args) {
//Create a binary sort tree object
BinarySearchTree<Integer> tree=new BinarySearchTree<>();
tree.add(77);
tree.add(67);
tree.add(90);
tree.add(69);
tree.add(10);
System.out.println(tree);
System.out.println(tree.size);
}
}
2.2 realize the output reference, and output the elements in the binary sort tree in ascending order -- using medium order traversal
2.2.1 rewrite the toString method to realize all elements in the output tree
If no element returns [],
If there are elements, use middle order traversal to the tree, save the elements to [], and finally return them in the form of [1,2,3,4]
- the method of middle order traversal will be called: traversal order: left root right. For each element traversed, add [] -- use StringBuilder to complete the addition of elements, and the final result is [1,2,3,4,5,6,]
/**Binary sort tree
* E Represents the interface type. The element type stored to the binary system can be interface type or class type
* No matter what type, ensure that the E interface is implemented*/
public class BinarySearchTree <E extends Comparable<E>>{
//1. Define the root node (there is only one)
private Node root;
//5. Define length (according to business requirements)
int size;
//6. Add method
/**Add element:
* Two cases:
* 1.root null, make the new element root
* 2.root Not null, add a new element to a node (judging from the root node)*/
public boolean add(E e){
//7. Judge whether the root node is null
if (root==null){ //If the element equals null, it becomes a new node
root=new Node(e);//Encapsulate as root node
size++;
return true;
}
//8. If the root is not null, add a new element to a node (judging from the root node)
return root.append(e);
}
//12. Override toString method
@Override
public String toString() {
//12.1 judge whether the root is null. If it is null, directly return []
if(root==null)
return "[]";
//12.2 if there are elements in the tree, you need to traverse the tree at this time`
StringBuilder builder=new StringBuilder("[");
//12.3 call sequence traversal
root.midOrder(builder); //The method name can be customized. Because it is a Node, the internal class of Node is defined
//12.4 process the elements in the builder, remove and add]
return builder.deleteCharAt(builder.lastIndexOf(",")).append("]").toString();
}
//2. Create Node internal class
private class Node{
//3. Create element attributes
private E data; //Element object
private Node left;//Left subtree
private Node right;//Right subtree
//4. Create structure with parameters
Node(E e){
data=e;
}
//9. Auto generate append method
public boolean append(E e) {
//10. Judge whether e is equal to root. If it is equal, return false. If not, judge whether it is greater than or less than,
// Here is the compareTo method. If it is equal to 0, it will prove that it is equal
if(e.compareTo(data)==0){//The nodes of all elements are saved in data, so data is used for comparison
return false;//Add failed
}else if (e.compareTo(data)<0){ //It indicates that the new element is smaller than the current element and is placed in the left subtree
if (left==null){//If the current left is empty, the new node will become the left subtree
left=new Node(e);//e stands for a new element
size++;
return true;//Added successfully
}
//If left is not null
return left.append(e);//Because the append method returns boolean, it returns directly
}else{//Add element to right subtree
if (right==null){
right = new Node(e);
size++;
return true;
}
return right.append(e);
}
}
//13
/**
* Traverse each element in the middle order, and add the traversal element to the builder*/
public void midOrder(StringBuilder builder) {
//Left, judge whether left is null
if (left!=null)
left.midOrder(builder);
//root
builder.append(data).append(",");
//right
if (right!=null)
right.midOrder(builder);
}
}
}
public class BinarySearchTreeTest {
public static void main(String[] args) {
//Create a binary sort tree object
BinarySearchTree<Integer> tree=new BinarySearchTree<>();
tree.add(77);
tree.add(67);
tree.add(90);
tree.add(69);
tree.add(10);
System.out.println(tree);
System.out.println(tree.size);
}
}2.2.2 preorder traversal and postorder traversal
Note: in Section 12.3 of toString of traversal code in the middle order, change the code call to test
//Traverse the root first
public void beforeOrder(StringBuilder builder){
builder.append(data).append(",");
//Judge whether the left subtree is not empty
if (left!=null)
left.beforeOrder(builder);
if (right!=null)
right.beforeOrder(builder);
} //Postorder traversal of left and right roots
public void afterOrder(StringBuilder builder){
if (left!=null)
left.afterOrder(builder);
if (right!=null)
right.afterOrder(builder);
builder.append(data).append(",");
}2.3 query elements from binary tree species
Find elements based on element values
As shown in the figure: we need to find the number 69. Then we will take 69 and compare it from the root node. If it is equal to 77, the search is completed. If it is smaller than 77, it will be shifted to 67, if it is larger than 77, it will be shifted to 90, and so on until it is equal
2.3.1 define node get (E) in binary sort tree
2.3.2 implementation method:
Starting from the root node, first judge whether the element is equal to the root node. If it is equal, it will directly return to the current node. If the element is not equal to the current node, judge whether it is greater than or less than. If it is greater than, go to the right subtree of the current node to find it If less than, search the left subtree of the current node, and so on
be careful:
1. If the root is null, the tree is empty. If you find any element, you should return null
2. If the searched element does not exist in the tree, null should also be returned
Test code:
1. Define get() in the external class to obtain nodes through elements
//14. Find by element
//14.1 get the node object of the element
public Node get(E e){
//Judge whether the root is null. If it is null, return null directly
if (root==null)
return null;
return root.get(e);
}2. Define the get method again in the inner class and override toString
//14.2 generate get method in inner class
public Node get(E e) {
//14.3 judge whether e is equal to the element of the current node
if (e.compareTo(data)==0){
return this;
}else if (e.compareTo(data)<0){
//First judge whether left is null. If the left subtree is null, it proves that the left subtree does not exist at all
if (left==null)
return null;
return left.get(e); //If the left is not null, use recursion to continue the search
}else{
//Judge whether the right subtree is null. If it is null, it returns null
if (right==null)
return null;
return right.get(e);
}
}
//14.4 toString rewriting for Node
@Override
public String toString() {
return "Node{" +
"data=" + data +
", left=" + left +
", right=" + right +
'}';
}3. Test code and query output results
public class BinarySearchTreeTest {
public static void main(String[] args) {
//14.5 find a non-existent element
System.out.println(tree.get(100)); //null
System.out.println(tree.get(90));//Node{data=90, left=null, right=null}
System.out.println(tree.get(67));//Node{data=67, left=Node{data=10, left=null, right=null}, right=Node{data=69, left=null, right=null}}
}
}2.4 deleting elements
Delete test URL:
There are three situations:
1. Delete the leaf node (there are no child nodes below), set the left or right of its parent node to null, and set the data of the current leaf node to null, then the current node object and element object will become garbage and wait for recycling
2. The deleted node has only one subtree. Let the reference of its parent node point to the child node of the deleted node
3. The deleted node has two subtrees,