一.二分搜索树：
1.代码：
public class BST<E extends Comparable<E>> {
private class Node{
public E e;
public Node left;
public Node right;
public Node(E e){
this.e = e;
left = null;
right = null;
}
}
private Node root;
private int size;
public BST(){
root = null;
size = 0;
}
public int getSize(){
return size;
}
public boolean isEmpty(){
return size ==0;
}
//向以node为根的二分搜索树中插入元素e,递归算法
private void add(Node node,E e){
if (e.equals(node.e)){
return;
}else if(e.compareTo(node.e) < 0 && node.left == null){
node.left = new Node(e);
size++;
return;
}else if(e.compareTo(node.e) > 0 && node.right == null){
node.right = new Node(e);
size++;
return;
}
if (e.compareTo(node.e) < 0 )
add(node.left,e);
else
add(node.right,e);
}
/**
* 向二分搜索树中添加新元素e
* @param e
*/
public void add(E e){
if(root == null){
root = new Node(e);
size++;
}else {
add(root,e);
}
}
// /**
// * //向以node为根的二分搜索树中插入元素e,递归算法。上面add(Node node,E e)方法的优化
// * @param node
// * @param e
// * @return
// */
// private Node addPlus(Node node ,E e){
// if (node == null){
// size++;
// return new Node(e);
// }
// if (e.compareTo(node.e) < 0){
// node.left = addPlus(node.left,e);
// }else if(e.compareTo(node.e) > 0){
// node.right = addPlus(node.right,e);
// }
// return node;
// }
//
// public void addPlus(E e){
// root = addPlus(root,e);
// }
public boolean contains(E e){
return contains(root,e);
}
/**
* 以node为根的二分搜索树中是否包含元素e,递归算法
* @param node
* @param e
* @return
*/
private boolean contains(Node node,E e){
if(node == null){
return false;
}
if (e.compareTo(node.e) == 0){
return true;
}else if(e.compareTo(node.e) < 0){
return contains(node.left,e);
}else {
return contains(node.right,e);
}
}
/**
* 前序遍历以node为根的二分搜索树，递归算法
* @param node
*/
private void preOrder(Node node){
if (node == null)
return;
System.out.println(node.e);
preOrder(node.left);
preOrder(node.right);
}
/**
* 二分搜索树前序遍历 ： 又叫：深度优先搜索
*/
public void preOrder(){
preOrder(root);
}
/**
* 二分搜索树层序遍历 ： 广度优先遍历
*/
public void levelOrder(){
java.util.Queue<Node> q = new java.util.LinkedList<>();
q.add(root);
while (!q.isEmpty()){
Node cur = q.remove();
System.out.println(cur.e);
if (cur.left!=null){
q.add(cur.left);
}
if (cur.right != null){
q.add(cur.right);
}
}
}
/**
* 寻找二分搜索树的最小元素
* @return
*/
public E minimum(){
if (size == 0)
throw new IllegalArgumentException();
return minimum(root).e;
}
/**
* 一直向左搜索
* @param node
* @return
*/
private Node minimum(Node node){
if (node.left == null)
return node;
return minimum(node.left);//向左搜索
}
/**
* 删除二分搜索树中最小值
* @return
*/
public E removeMin(){
//找到最小值
E ret = minimum();
root = removeMin(root);
return ret;
}
/**
* 一直向左遍历
* @param node
* @return
*/
private Node removeMin(Node node){
if (node.left == null){
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
generateBSTString(root,0,res);
return res.toString();
}
private void generateBSTString(Node node, int deepth, StringBuilder res) {
if (node == null){
res.append(generateDepthString(deepth)+"null\n");
return;
}
res.append(generateDepthString(deepth)+node.e+"\n");
generateBSTString(node.left,deepth+1,res);
generateBSTString(node.right,deepth+1,res);
}
private String generateDepthString(int deepth) {
StringBuilder res = new StringBuilder();
for (int i = 0; i < deepth;i++){
res.append("--");
}
return res.toString();
}
}