- 一、二叉搜索树
- 二、BST 接口设计
- 三、实现（add）
- 添加节点步骤（☆☆☆☆☆）
- 添加进 BST 里面的元素必须具有可比较性
- (1) BST 限制泛型必须具有可比较性
- (2) 传比较器给 BST
- (3) 结合 (1) 和 (2)
- 四、二叉树网址和打印器的使用
- 任意一个节点的值都大于其左子树所有节点的值
- 任意一个节点的值都小于其右子树所有节点的值
- BST 存储的元素必须具备可比较性（如 int、double 等）
- BST 存储自定义类型，需要指定比较方式
- BST 存储的元素不能为 null
左边的都比我小，右边的都比我大。
二、BST 接口设计public class BinarySearchTree{ public int size() { return 0; } public boolean isEmpty() { return true; } public void clear() { } public void add(E element) { } public void remove(E element) { } public boolean contains(E element) { return true; } }
- BST 的元素没有索引的概念
- 二叉搜索树（BinarySearchTree）中会维护一个节点类
- BST 内部会维护根节点
public class BinarySearchTree{ private static class Node { // 节点上存储的元素 E element; // 左子节点 Node left; // 右子节点 Node right; // 父节点 Node parent; public Node(E element, Node parent) { this.element = element; this.parent = parent; } } }
- 元素非空检测
private void elementNotNullCheck(E element) {
if (element == null)
throw new IllegalArgumentException("Element must not be null!");
}
添加节点步骤（☆☆☆☆☆）
- 找到父节点（parent）
- 创建新节点（node）
- parent.left = node 或 parent.right = node
- 遇到值相等？新值覆盖旧值
BinarySearchTree 限制，能够放进 BinarySearchTree 泛型的元素必须实现 Comparable 接口。Comparable 接口中要求实现它的类必须实现 compareTo 方法，进而提供比较逻辑。
public class BinarySearchTree> { // 记录二叉搜索树的元素个数 private int size; private Node root; // 根节点 public int size() { return size; } public boolean isEmpty() { return size == 0; } public void clear() { } public void add(E element) { elementNotNullCheck(element); // BST 中存储的第一个节点（根节点） if (size == 0 && root == null) { root = new Node<>(element, null); size++; return; } // 假设 node 是父节点 Node node = root; Node parent = root; int cmp = 0; while (node != null) { cmp = compare(element, node.element); parent = node; if (cmp > 0) { node = node.right; } else if (cmp < 0) { node = node.left; } else { return; } } // 创建新节点 Node newNode = new Node<>(element, parent); if (cmp > 0) { parent.right = newNode; } else if (cmp < 0) { parent.left = newNode; } size++; } public void remove(E element) { } public boolean contains(E element) { return true; } private int compare(E e1, E e2) { return e1.compareTo(e2); } private void elementNotNullCheck(E element) { if (element == null) throw new IllegalArgumentException("Element must not be null."); } private static class Node { E element; Node left; Node right; Node parent; public Node(E element, Node parent) { this.element = element; this.parent = parent; } } }
public interface Comparable{ int compareTo(E e); }
public class Student implements Comparable{ private int score; public int getScore() { return score; } public Student(int score) { this.score = score; } @Override public int compareTo(Student student) { return score - student.getScore(); } }
public class Main {
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree<>();
bst.add(new Student(100));
bst.add(new Student(66));
bst.add(new Student(78));
}
}
Student 类的比较逻辑写死了
(2) 传比较器给 BSTpublic class BinarySearchTree{ // 记录二叉搜索树的元素个数 private int size; private Node root; // 根节点 private Comparator comparator; public BinarySearchTree(Comparator comparator) { this.comparator = comparator; } public int size() { return size; } public boolean isEmpty() { return size == 0; } public void clear() { } public void add(E element) { elementNotNullCheck(element); // BST 中存储的第一个节点（根节点） if (size == 0 && root == null) { root = new Node<>(element, null); size++; return; } // 假设 node 是父节点 Node node = root; Node parent = root; int cmp = 0; while (node != null) { cmp = compare(element, node.element); parent = node; if (cmp > 0) { node = node.right; } else if (cmp < 0) { node = node.left; } else { return; } } // 创建新节点 Node newNode = new Node<>(element, parent); if (cmp > 0) { parent.right = newNode; } else if (cmp < 0) { parent.left = newNode; } size++; } public void remove(E element) { } public boolean contains(E element) { return true; } private int compare(E e1, E e2) { return comparator.compare(e1, e2); } private void elementNotNullCheck(E element) { if (element == null) throw new IllegalArgumentException("Element must not be null."); } private static class Node { E element; Node left; Node right; Node parent; public Node(E element, Node parent) { this.element = element; this.parent = parent; } } }
public interface Comparator{ int compare(E e1, E e2); }
public class Student {
private int score;
public int getScore() {
return score;
}
public Student(int score) {
this.score = score;
}
}
public class Main2 {
private static class StudentComparator1 implements Comparator {
@Override
public int compare(Student e1, Student e2) {
return e1.getScore() - e2.getScore();
}
}
private static class StudentComparator2 implements Comparator {
@Override
public int compare(Student e1, Student e2) {
return e2.getScore() - e1.getScore();
}
}
public static void main(String[] args) {
BinarySearchTree bst1 = new BinarySearchTree<>(new StudentComparator1());
BinarySearchTree bst2 = new BinarySearchTree<>(new StudentComparator2());
}
}
强制限制 BST 必须提供比较器了
(3) 结合 (1) 和 (2)public class BinarySearchTree3{ // 记录二叉搜索树的元素个数 private int size; private Node root; // 根节点 private Comparator comparator; public BinarySearchTree3(Comparator comparator) { this.comparator = comparator; } public BinarySearchTree3() { this.comparator = null; } public int size() { return size; } public boolean isEmpty() { return size == 0; } public void clear() { } public void add(E element) { elementNotNullCheck(element); // BST 中存储的第一个节点（根节点） if (size == 0 && root == null) { root = new Node<>(element, null); size++; return; } // 假设 node 是父节点 Node node = root; Node parent = root; int cmp = 0; while (node != null) { cmp = compare(element, node.element); parent = node; if (cmp > 0) { node = node.right; } else if (cmp < 0) { node = node.left; } else { return; } } // 创建新节点 Node newNode = new Node<>(element, parent); if (cmp > 0) { parent.right = newNode; } else if (cmp < 0) { parent.left = newNode; } size++; } public void remove(E element) { } public boolean contains(E element) { return true; } private int compare(E e1, E e2) { if (comparator != null) return comparator.compare(e1, e2); return ((Comparable )e1).compareTo(e2); } private void elementNotNullCheck(E element) { if (element == null) throw new IllegalArgumentException("Element must not be null."); } private static class Node { E element; Node left; Node right; Node parent; public Node(E element, Node parent) { this.element = element; this.parent = parent; } } }
public interface Comparable{ int compareTo(E e); }
public interface Comparator{ int compare(E e1, E e2); }
public class Student {
private int score;
public int getScore() {
return score;
}
public Student(int score) {
this.score = score;
}
}
public class Main3 {
private static class StudentComparator1 implements Comparator {
@Override
public int compare(Student e1, Student e2) {
return e1.getScore() - e2.getScore();
}
}
private static class StudentComparator2 implements Comparator {
@Override
public int compare(Student e1, Student e2) {
return e2.getScore() - e1.getScore();
}
}
public static void main(String[] args) {
BinarySearchTree3 bst1 = new BinarySearchTree3<>(new StudentComparator1());
BinarySearchTree3 bst2 = new BinarySearchTree3<>(new StudentComparator2());
BinarySearchTree3 bst3 = new BinarySearchTree3<>();
}
}
Comparable 和 Comparator 在 jdk 的 util 包中都有的
匿名内部类和 Lambda 表达式：
public class Main4 {
private static class StudentComparator1 implements Comparator {
@Override
public int compare(Student e1, Student e2) {
return e1.getScore() - e2.getScore();
}
}
private static class StudentComparator2 implements Comparator {
@Override
public int compare(Student e1, Student e2) {
return e2.getScore() - e1.getScore();
}
}
public static void main(String[] args) {
BinarySearchTree4 bst1 = new BinarySearchTree4<>(new StudentComparator1());
BinarySearchTree4 bst2 = new BinarySearchTree4<>(new StudentComparator2());
BinarySearchTree4 bst3 = new BinarySearchTree4<>();
// 匿名内部类
BinarySearchTree4 bst4 = new BinarySearchTree4<>(new Comparator() {
@Override
public int compare(Student o1, Student o2) {
return o1.getScore() - o2.getScore();
}
});
// Lambda 表达式
BinarySearchTree4 bst5 = new BinarySearchTree4<>((o1, o2) -> o2.getScore() - o1.getScore());
}
}
四、二叉树网址和打印器的使用
https://520it.com/binarytrees/
① BinarySearchTree 实现 BinaryTreeInfo 接口
② 实现四个方法
@Override
public Object root() {
return root;
}
@Override
public Object left(Object node) {
return ((Node) node).left;
}
@Override
public Object right(Object node) {
return ((Node) node).right;
}
@Override
public Object string(Object node) {
return ((Node) node).element;
}
③ BinaryTrees.pringln(bst) 打印
