注:接口中带 TODO 字样的方法,是视频中没有写的,需要你们自己实现。 写一个BinarySearchTree 来实现 Tree 接口,定义如下: ublic class BinarySearchTree<T extends Comparable<T>> implements Tree<T> { //属性: //1. 指向根节点 private Node<T> root; //2.树中节点的数量 private int size; //TODO 实现接口所有的方法,另外,要实现remove方法,在此类中还要额外提供 findParentNode(T target) 方法和 findMinNodeFromRight(Node<T> target) 方法 }
时间: 2024-03-26 17:35:21 浏览: 12
好的,我明白了。以下是实现 BinaryTree 接口的 BinarySearchTree 类的代码:
```
public class BinarySearchTree<T extends Comparable<T>> implements Tree<T> {
//属性:
//1. 指向根节点
private Node<T> root;
//2.树中节点的数量
private int size;
//构造函数
public BinarySearchTree() {
this.root = null;
this.size = 0;
}
//节点类
private static class Node<T> {
T value;
Node<T> left;
Node<T> right;
public Node(T value) {
this.value = value;
this.left = null;
this.right = null;
}
}
//实现接口所有的方法
@Override
public boolean insert(T value) {
if (value == null) {
return false;
}
if (root == null) {
root = new Node<T>(value);
size++;
return true;
}
Node<T> parent = findParentNode(value);
int cmp = value.compareTo(parent.value);
if (cmp == 0) {
return false;
} else if (cmp < 0) {
parent.left = new Node<T>(value);
} else {
parent.right = new Node<T>(value);
}
size++;
return true;
}
@Override
public boolean remove(T value) {
if (root == null || value == null) {
return false;
}
Node<T> parent = findParentNode(value);
Node<T> current = null;
if (parent == null) {
current = root;
} else if (parent.left != null && parent.left.value.compareTo(value) == 0) {
current = parent.left;
} else if (parent.right != null && parent.right.value.compareTo(value) == 0) {
current = parent.right;
} else {
return false;
}
if (current.left == null && current.right == null) {
if (parent == null) {
root = null;
} else if (parent.left == current) {
parent.left = null;
} else {
parent.right = null;
}
} else if (current.left == null) {
if (parent == null) {
root = current.right;
} else if (parent.left == current) {
parent.left = current.right;
} else {
parent.right = current.right;
}
} else if (current.right == null) {
if (parent == null) {
root = current.left;
} else if (parent.left == current) {
parent.left = current.left;
} else {
parent.right = current.left;
}
} else {
Node<T> minFromRight = findMinNodeFromRight(current);
remove(minFromRight.value);
current.value = minFromRight.value;
}
size--;
return true;
}
@Override
public boolean contains(T value) {
Node<T> current = root;
while (current != null) {
int cmp = value.compareTo(current.value);
if (cmp == 0) {
return true;
} else if (cmp < 0) {
current = current.left;
} else {
current = current.right;
}
}
return false;
}
@Override
public int size() {
return size;
}
@Override
public void clear() {
root = null;
size = 0;
}
//找到待插入节点的父节点
private Node<T> findParentNode(T value) {
Node<T> parent = null;
Node<T> current = root;
while (current != null) {
int cmp = value.compareTo(current.value);
if (cmp == 0) {
return current;
} else if (cmp < 0) {
parent = current;
current = current.left;
} else {
parent = current;
current = current.right;
}
}
return parent;
}
//找到右子树中的最小节点
private Node<T> findMinNodeFromRight(Node<T> current) {
Node<T> minNode = current.right;
while (minNode.left != null) {
minNode = minNode.left;
}
return minNode;
}
}
```