import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.ArrayBlockingQueue;
/**
* 二分搜索树的实现
*
* @author hcc
*
* @param <E>
*/
public class BST<E extends Comparable<E>> {
private Node root;
private int size;
public BST() {
this(null);
}
private BST(Node root) {
this.root = root;
this.size = 0;
}
/**
* 添加元素
* @param e
*/
public void add(E e) {
if (root == null) {
root = new Node(e);
size++;
} else {
add(this.root, e);
}
}
/**
* 添加元素的具体操作
* @param root 树结构的根节点
* @param e 将要添加的数据
*/
private void add(Node root, E e) {
// 也可以使用该表达式判断 e是否存在于树结构中
// if(e.compareTo(root.data) == 0) {
// return;
// }
if (e.equals(root.data)) {
return;
} else if (e.compareTo(root.data) < 0 && root.left == null) {
Node node = new Node(e);
root.left = node;
size++;
} else if (e.compareTo(root.data) > 0 && root.right == null) {
Node node = new Node(e);
root.right = node;
size++;
}
if (e.compareTo(root.data) < 0) {
add(root.left, e);
}
if (e.compareTo(root.data) > 0) {
add(root.right, e);
}
}
/**
* 优化后的添加方法（优化了递归结束条件）
*/
@SuppressWarnings("unused")
private Node addForOptimize(Node root, E e) {
if (root == null) {
Node node = new Node(e);
size++;
return node;
} else if (e.compareTo(root.data) < 0) {
root.left = addForOptimize(root.left, e);
} else if (e.compareTo(root.data) > 0) {
root.right = addForOptimize(root.right, e);
}
return root;
}
/**
* 删除操作，删除树中最小的元素、删除树中最大的元素、随意删除
*/
/**
* 删除“树”上最小的元素（在左下角，二分搜索树的性质决定的）
*
* @return 返回该节点的值
*/
public E removeMin() {
Node node = removeMin(root);
return node.data;
}
/**
* 当找到左下角节点时，需判断该节点是否有“右孩子”
* @param node
* @return
*/
private Node removeMin(Node node) {
if (node == null) {
// 或者通过size判断是否为空也可以
throw new IllegalArgumentException("BST is Empty!");
}
Node sNode = null;
while (node.left != null) {
sNode = node;
node = node.left;
}
Node nod = node;
node = null;
if (nod.right != null) {
sNode.left = nod.right;
} else {
sNode.left = null;
}
size--;
return nod;
}
/**
* 删除“树”上最大的元素（在右下角，二分搜索树的性质决定的）
*
* @return 返回该节点的值
*/
public E removeMax() {
Node node = removeMax(root);
return node.data;
}
/**
* 当找到右下角节点时，需判断该节点是否有“左孩子”
* @param node
* @return
*/
private Node removeMax(Node node) {
if (node == null) {
throw new IllegalArgumentException("BST is Empty!");
}
Node sNode = null;
while (node.right != null) {
sNode = node;
node = node.right;
}
Node nod = node;
node = null;
if (nod.left != null) {
sNode.right = nod.left;
} else {
sNode.right = null;
}
size--;
return nod;
}
/**
* 删除任意位置的值
*
* @param e
*/
public void remove(E e) {
root = remove(root, e);
}
/**
* 删除的具体操作
*
* @param node
* 树结构
* @param e
* 将要删除的数据
* @return 删除指定数据后的树结构
*/
private Node remove(Node node, E e) {
if (e == null || node == null) {
return null;
}
if (e.equals(node.data)) {
if (node.left != null && node.right != null) {
Node nod = node;
node = removeMin(node.right);
size++;
node.left = nod.left;
node.right = nod.right;
nod.left = nod.right = null;
} else {
if (node.left == null && node.right != null) {
size--;
return node.right;
} else if (node.right == null && node.left != null) {
size--;
return node.left;
} else {
size--;
return null;
}
}
size--;
return node;
} else if (e.compareTo(node.data) < 0) {
node.left = remove(node.left, e);
} else if (e.compareTo(node.data) > 0) {
node.right = remove(node.right, e);
}
return node;
}
/**
* 查，前序遍历（递归、非递归）中序遍历（递归、非递归）后序遍历（递归、非递归）层序遍历
*/
/**
* 前序遍历
*/
public void preOrder() {
preOrder(root);
}
/**
* 前序遍历（递归操作）
*
* @param root
*/
private void preOrder(Node node) {
if (node == null) {
return;
}
System.out.print(node.data + " ");
preOrder(node.left);
preOrder(node.right);
}
/**
* 前序遍历（非递归操作）
*
* @param root
*/
@SuppressWarnings("unused")
private void preOrderOne(Node node) {
Stack<Node> stack = new Stack<Node>();
stack.push(node);
while (!stack.isEmpty()) {
Node sNode = stack.pop();
System.out.print(sNode.data + " ");
if (sNode.right != null) {
stack.push(sNode.right);
}
if (sNode.left != null) {
stack.push(sNode.left);
}
}
}
/**
* 中序遍历
*/
public void inOrder() {
inOrderOne(root);
}
/**
* 中序遍历（递归操作）
*
* @param root
*/
@SuppressWarnings("unused")
private void inOrder(Node node) {
if (node == null) {
return;
}
inOrder(node.left);
System.out.print(node.data + " ");
inOrder(node.right);
}
/**
* 中序遍历（非递归操作）
*
* @param root
*/
private void inOrderOne(Node node) {
Stack<Node> stack = new Stack<Node>();
Node nod = node;
while (!stack.isEmpty() || nod != null) {
while (nod != null) {
stack.push(nod);
nod = nod.left;
}
Node sNode = stack.pop();
System.out.print(sNode.data + " ");
nod = sNode.right;
}
}
/**
* 后序遍历
*/
public void postOrder() {
postOrderOne(root);
}
/**
* 后序遍历（递归操作）
*
* @param node
*/
@SuppressWarnings("unused")
private void postOrder(Node node) {
if (node == null) {
return;
}
postOrder(node.left);
postOrder(node.right);
System.out.print(node.data + " ");
}
/**
* 后序遍历（非递归操作）
*
* @param node
*/
private void postOrderOne(Node node) {
Stack<Node> stack = new Stack<Node>();
Node nod = node;
Node pre = null;
while (!stack.isEmpty() || nod != null) {
while (nod != null) {
stack.push(nod);
nod = nod.left;
}
Node sNode = stack.peek();
if (sNode.right == null || pre == sNode.right) {
stack.pop();
pre = sNode;
System.out.print(sNode.data + " ");
} else {
nod = sNode.right;
}
}
}
/**
* 层序遍历
*/
public void levelTraversal() {
levelTraversal(root);
}
/**
* 层序遍历（非递归操作）
*
* @param node
*/
private void levelTraversal(Node node) {
Queue<Node> queue = new ArrayBlockingQueue<Node>(size);
if (node != null) {
queue.offer(node);
}
while (!queue.isEmpty()) {
// System.out.println("取出前："+queue.size());
node = queue.poll();
// System.out.println("取出后："+queue.size());
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
System.out.print(node.data + " ");
}
}
/**
* 获取二分搜索树中数据的个数
*
* @return
*/
public int getSize() {
return this.size;
}
/**
* 判空操作
*
* @return true表示为空，false表示不为空
*/
public boolean isEmpty() {
return this.size == 0;
}
/**
* 判断数据是否在树中存在
*
* @param e
* @return true表示存在，false表示不存在
*/
public boolean contains(E e) {
return contains(root, e);
}
private boolean contains(Node root, E e) {
if (root != null) {
if (e.compareTo(root.data) == 0) {
return true;
} else if (e.compareTo(root.data) < 0) {
return contains(root.left, e);
} else if (e.compareTo(root.data) > 0) {
return contains(root.right, e);
}
}
return false;
}
class Node {
E data;
Node left;
Node right;
public Node() {
this(null, null, null);
}
public Node(E e) {
this(e, null, null);
}
private Node(E e, Node left, Node right) {
this.data = e;
this.left = left;
this.right = right;
}
}
}
网友评论