BST
任意一个节点的值，都大于其左子树所有节点的值。
任意一个节点的值，都小于其右子树所有节点的值。
左右子树也是一颗二叉搜索树。
元素必须是可比较的。
元素不能为null 。
类设计：
属性：
树是由一个一个节点组成，那么可以使用一个基础的集合来保存Node。 实际上比不需要一个集合来保存。 只需要记录一个根节点属性就可以了。 节点里面有子节点的指向，就可以根据节点的左右子节点来找到相应的节点了。 所以，第一个属性是根节点。
Node<E> root;
既然有了节点，肯定需要记录下来当前树的大小，那么就会有一个size属性。
int size;
二叉搜索树也是用来保存数据的，所以，必须要有一个元素(数据)的属性。
还是有些不理解，元素直接放在节点里面不就可以了？ 为什么还需要一个元素属性？一棵树里面有一个元素？？？？
E element;
为了让二叉树可以存储任何类型的元素，所以可以在类定义的时候加一个泛型。
方法：
提供数据结构应该要有的基础的操作方法：
int size() 返回当前大小
boolean isEmpty() 返回当前是否为空
void clear() 清空当前结构
void add(E element) 添加一个元素
void remove(E element) 删除一个元素
boolean contains(E element) 判断一个元素是否存在
看回节点，因为节点只提供给本类使用，所以创建一个内部类(Node)就可以了。
节点应该也可以存储任何类型的元素，所以定义的时候也可以给一个泛型。
二叉树里面，一个节点都会有父节点和左右子节点(除了根节点没有父节点)。
除此之外，节点应该可以保存一个对象，作为节点的数据。
所以， 内部类如下：
private static class Node<E>{
E element;
Node<E> left;
Node<E> right;
Node<E> parent;
//构造函数,因为parent是除了根节点以外其他节点都必须有的，所以构造函数要提供。 left和right每个节点不一定有，所以不需要在构造函数里面提供。
public Node(E element, Node<E> parent) {
this.element = element;
this.parent = parent;
}
}
整合上述，整个二叉搜索树的基础结构如下：
二叉搜索树基础结构
package com.franck.dateStruct.tree;
/**
* 二叉搜索树
*/
public class BinarySearchTree<E> {
private int size;
private E element;
/**
* 返回当前大小
* @return size
*/
public int size() {
return size;
}
/**
* 返回当前是否为空
* @return 是否为空
*/
public boolean isEmpty() {
return size == 0 ;
}
/**
* 清空所有元素
*/
public void clear() {
}
/**
* 添加一个元素
* @param element 元素
*/
public void add(E element) {
}
/**
* 删除一个特定元素
* @param element 需要删除的元素
*/
public void remove(E element) {
}
/**
* 判断元素是否存在
* @param element 需要判断的元素
* @return 判断结果
*/
public boolean contains(E element) {
return false;
}
private static class Node<E>{
E element;
Node<E> left;
Node<E> right;
Node<E> parent;
public Node(E element, Node<E> parent) {
this.element = element;
this.parent = parent;
}
}
}
实现比较方法：
二叉搜索树的元素一定是可比较的。
1 继承compareable接口。
2 使用比较器。
3 使用比较器 + comparable接口。
实现添加方法：
1 非空检测
不能将null添加到数里面，所以首先要进行非空的检测。在这边，写一个非空检测的方法，因为其他的方法也会用到非空检测，所以抽出来做成一个方法。在添加方法的第一步，调用检测方法。
/**
* 添加一个元素
* @param element 元素
*/
public void add(E element) {
elementNotNullCheck(element);
}
private void elementNotNullCheck(E element) {
if (element == null) {
throw new IllegalArgumentException("元素不能为null");
}
}
2 添加根节点
如果根节点为null，则先添加根节点。
public void add(E element) {
elementNotNullCheck(element);
if (this.root == null) {
root = new Node<E>(element,null);
size++;
return ;
}
}
3 添加子节点
如果根节点不是null，则当前一定是添加子节点。
实现思路：
-
找到新增节点的父节点。
从根节点开始对比，如果比根节点大，则去右子树找，如果比根节点小，则去左子树找。一直找到空的位置。如果新增的节点和父节点相等，不处理，或者替换，建议进行替换。因为新元素和旧元素是不一样的。如果没有处理，则丢失了新增的节点了。 -
确定新增节点的位置。
确定父节点后，也就确定了新增节点的位置，是父节点的左节点还是右节点，还是和父节点一样。 然后新增加一个节点，添加进树里面。 然后设置新增的节点为父节点的左子树或者右子树，或者替换掉父节点。
下面是增加添加子节点的逻辑代码(JDK的实现会更复杂一些，会使用到比较器来实现更加灵活的元素的比较，这里只使用comparable来比较)：
/**
* 添加一个元素
* @param element 元素
*/
public void add(E element) {
elementNotNullCheck(element);
if (this.root == null) {
root = new Node<E>(element,null);
size++;
return ;
}
Node<E> parent = root;
Node<E> current = root;
int result = 0;
while (current != null) {
parent = current;
result = element.compareTo(current.element);
if (result < 0) {
//左节点
current = current.left;
} else if (result > 0) {
//右节点
current = current.right;
} else {
//相等
current.element = element;
}
}
//创建节点
Node<E> newNode = new Node<E>(element,parent);
//设置节点的位置
if (result < 1) {
parent.left = newNode;
} else if (result > 1) {
parent.right = newNode;
}
size++;
}
private void elementNotNullCheck(E element) {
if (element == null) {
throw new IllegalArgumentException("元素不能为null");
}
}
网友评论