package com.cb.java.algorithms.datastructure.yanweimindatastructure.tree;
/**
* 二叉查找树
*
* @author 36184
*
*/
public class BinarySearchTree<T extends Comparable<T>> {
private TreeNode<T> root; // 根节点
public TreeNode<T> getRoot() {
return root;
}
/**
* 查找
*
* @param key
* @return
* @throws Exception
*/
public TreeNode<T> find(T key) throws Exception {
if (root == null) {
return null;
} else {
TreeNode<T> current = root;
while (current.data.compareTo(key) != 0) {
if (current.data.compareTo(key) < 0) {
current = current.rightChild;
} else {
current = current.leftChild;
}
if (current == null) {
throw new Exception("找不到该节点");
}
}
return current;
}
}
/**
* 插入节点
*
* @param data
*/
public void insert(T data) {
TreeNode<T> node = new TreeNode<T>(data); // 根据插入的数据新建一个节点
if (root == null) {
root = node;
} else {
TreeNode<T> current = root;
TreeNode<T> parent; // 保存要插入节点的父节点
while (true) {
parent = current;
if (current.data.compareTo(node.data) < 0) {
current = current.rightChild; // 如果值大于父节点，则在右子树查找
if (current == null) {
parent.rightChild = node;
return;
}
} else {
current = current.leftChild;
if (current == null) {
parent.leftChild = node;
return;
}
}
}
}
}
/**
* 中序遍历节点：左根右
*
* @param node
*/
public void inOrder(TreeNode<T> node) {
if (node != null) {
inOrder(node.leftChild); // 访问左子树
System.out.println(node.data); // 输出根节点
inOrder(node.rightChild);// 访问右子树
}
}
/**
* 先序遍历
*
* @param node
*/
public void preOrder(TreeNode<T> node) {
if (node != null) {
System.out.println(node.data);
preOrder(node.leftChild);
preOrder(node.rightChild);
}
}
/**
* 后续遍历
*
* @param node
*/
public void postOrder(TreeNode<T> node) {
if (node != null) {
postOrder(node.leftChild);
postOrder(node.rightChild);
System.out.println(node.data);
}
}
/**
* 查找树中最小值
*
* @return
* @throws Exception
*/
public T findMin() throws Exception {
if (root == null) {
throw new Exception("该树为空，没有最小值！");
} else {
TreeNode<T> current = root;
TreeNode<T> parent = null;
while (current != null) {
parent = current;
current = current.leftChild;
}
return parent.data;
}
}
/**
* 查找树中最大值
*
* @return
* @throws Exception
*/
public T findMax() throws Exception {
if (root == null) {
throw new Exception("该树为空，没有最小值！");
} else {
TreeNode<T> current = root;
TreeNode<T> parent = null;
while (current != null) {
parent = current;
current = current.rightChild;
}
return parent.data;
}
}
/**
* 删除指定节点
*
* @param data
* @return
* @throws Exception
*/
public boolean delete(T data) throws Exception {
TreeNode<T> current = root;
TreeNode<T> parent = root;
boolean isLeftChild = true;
while (current.data.compareTo(data) != 0) {
parent = current;
if (data.compareTo(current.data) < 0) {
isLeftChild = true;
current = current.leftChild;
} else {
isLeftChild = false;
current = current.rightChild;
}
if (current == null) {
return false;
}
}
// 删除的是叶子节点
if (current.leftChild == null && current.rightChild == null) {
if (current == root) {
root = null;
} else if (isLeftChild) {
parent.leftChild = null;
} else {
parent.rightChild = null;
}
}
// 删除的节点有一个左子节点
else if (current.rightChild == null) {
if (current == root) {
root = current.leftChild;
}
// 删除的节点本身是左子节点
else if (isLeftChild) {
parent.leftChild = current.leftChild;
}
// 删除的节点本身是右子节点
else {
parent.rightChild = current.leftChild;
}
}
// 删除的节点有一个右子节点
else if (current.leftChild == null) {
if (root == null) {
root = current.rightChild;
}
// 删除的节点本身是左子节点
else if (isLeftChild) {
parent.leftChild = current.rightChild;
}
// 删除的节点本身是右子节点
else {
parent.rightChild = current.rightChild;
}
}
// 删除的节点有左右两个字节点
else {
TreeNode<T> successor = getSuccessor(current); // 要删除节点的直接后继节点
if (current == root) {
root = successor;
}
// 删除的节点本身是左子节点
else if (isLeftChild) {
parent.leftChild = successor;
}
// 删除的节点本身是右子节点
else
parent.rightChild = successor;
successor.leftChild = successor.leftChild;
}
return true;
}
private TreeNode<T> getSuccessor(TreeNode<T> delNode) {
TreeNode<T> successorParent = delNode;// 后继节点的父节点
TreeNode<T> successor = delNode; // 后继节点
TreeNode<T> current = delNode.rightChild; // 要删除节点的右子节点
while (current != null) {
successorParent = successor;
successor = current;
current = current.leftChild;
}
if (successor != delNode.rightChild) {
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
public static void main(String[] args) throws Exception {
BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
binarySearchTree.insert(10);
binarySearchTree.insert(20);
binarySearchTree.insert(5);
binarySearchTree.insert(13);
binarySearchTree.insert(100);
// TreeNode<Integer> node = binarySearchTree.find(100);
// System.out.println(node.data);
// binarySearchTree.inOrder(binarySearchTree.getRoot());
System.out.println("该二叉树最小值为：" + binarySearchTree.findMin());
System.out.println("该二叉树最大值为：" + binarySearchTree.findMax());
boolean delete = binarySearchTree.delete(100);
System.out.println(delete);
binarySearchTree.inOrder(binarySearchTree.getRoot());
System.out.println("该二叉树最大值为：" + binarySearchTree.findMax());
}
}
class TreeNode<T extends Comparable<T>> {
T data; // 节点保存的数据项
TreeNode<T> leftChild; // 节点左子节点
TreeNode<T> rightChild; // 节点右字节点
public TreeNode(T data) {
this.data = data;
leftChild = null;
rightChild = null;
}
}