package com.learn.tree.demo2;
import java.util.LinkedList;
import java.util.Queue;
/**
* 二分查找树BST（也叫二叉查找树、二叉排序树）的提出是为了提供查找效率，
* 之所以称为二分查找树，因为该二叉树对应着二分查找算法，查找平均的时间复杂度为o(logn)，所以该数据结构的提出是为了提高查找效率。 定义
* 二分查找树或者是一棵空树，或者具有下列性质： 1.若它的左子树不为空，则左子树上所有结点的值均小于根结点的值；
* 2.若它的右子树不为空，则右子树上所有结点的值均大于根结点的值； 3.它的左右子树均为二分查找树。
*
*
* 具体实现:二叉树的前序遍历,中序遍历，后序遍历，层次遍历 求二叉树深度(根到节点-叶子节点最长路径) 新增节点(没有该键 则新增 有则添加) 删除节点
*
* 注意:该二叉搜索树的实现是没有重复键值的
*
*/
public class BinaryTree<Key extends Comparable<Key>, Value> {
private Node root;// 二叉树的根节点
private int count;// 二叉树中的节点数
// 二叉树的实例化 的构造器
public BinaryTree() {
root = null;// 初始化根节点
count = 0;
}
// 判断该 二叉树是否有节点
public boolean isEmpty() {
return count == 0;
}
// 该二叉树的节点数
public int size() {
return count;
}
// 新增二叉树的节点
public void insert(Key key, Value value) {
root = insert(root, key, value);
}
/**
* 插入节点的内部实现方法 采用递归的方法实现 二叉树的插入操作 返回 新增节点的二叉树的后根节点(为什么是根节点 注意递归后的的递进，还有回退 )
*
* @param root
* 该二叉树的根
* @param key
* @param value
*/
private Node insert(Node node, Key key, Value value) {
// 如果根节点的为空 ，则将新增的节点为 作为根节点
if (node == null) {
count++;
return new Node(key, value);
}
if (key.compareTo(node.key) > 0) {
node.right = insert(node.right, key, value);
} else if (key.compareTo(node.key) < 0) {
node.left = insert(node.left, key, value);
} else
node.value = value;
return node;
}
/**
* 获得最小节点
*
* @param key
*/
public Node getMininum() {
Node node = mininum(root);
return node;
}
/**
* 获得最小节点内部方法实现(没有左节点)--->迭代法
*
* @param node
* @param key
* @return
*/
private Node mininum(Node node) {
Node parent = null;
while (node != null) {
parent = node;
node = node.left;
}
return parent;
}
/**
* 获得最小节点内部方法实现(没有左节点)-->递归法
*
* @param node
* @return
*/
private Node minimumD(Node node) {
if (node.left== null)
return node;
return minimumD(node.left);
}
/**
* 获得的二叉树的最大节点
*
* @param key
* @return
*/
public Node getMaxinum() {
Node node = maxinum(root);
return node;
}
/**
* 最大节点的内部实现(没有右节点)--->迭代法
*
* @param node
* @param key
* @return
*/
private Node maxinum(Node node) {
Node parent = null;
while (node != null) {
parent = node;
node = node.right;
}
return parent;
}
/**
* 最大节点的内部实现(没有右节点)--->递归法
*
* @param node
* @return
*/
private Node maxinumD(Node node) {
if (node.right== null)
return node;
return maxinum(node.right);
}
/**
* 删除二叉搜索树的最小节点
*
* @return
*/
public Node removeMin() {
if (root != null)
root = removeMin(root);
return root;
}
/**
* 删除二叉搜索树的最小节点(不同的结构体 或者实体类实现方法不同) 这里是单项关联 过时将父节点的左节点 置为null,与左节点断开关联
* 返回删除节点后新的二分搜索树的根 ----------------------->递归法
*
* @param node
* @return
*/
private Node removeMin(Node node) {
if (node.left == null) {
final Node rightNode = node.right;
node.right = null;// let out gc
count--;
return rightNode;// 如果该节点有右节点，将该节点的 右节点 作为该
// 节点的父节点的左节点(于此同时也断开了该节点与父节点的联系)
}
// 递归调用左节点(直至左节点为空 删除该节点)
node.left = removeMin(node.left);
return node;
}
/**
* 删除二叉搜索树的最小节点--->迭代法
*
* @param node
*/
private void removeMinNode(Node node) {
Node parentNode = null;
while (node != null) {
parentNode = node;
node = node.left;
}
final Node rightNode = node.right;
node.right = null;// let out gc
parentNode.left = rightNode;
count--;
}
/**
* 删除二叉搜索树的最大节点
*
* @return
*/
public Node removeMax() {
if (root != null)
root = removeMax(root);
return root;
}
/**
* 删除二叉搜索树的最大节点(不同的结构体 或者实体类实现方法不同) 这里是单项关联 过时将父节点的右节点 置为null,与右节点断开关联
* 返回删除最大节点后的二叉搜索树的节点 ----------------------->递归法
*
* @param node
* @return
*/
private Node removeMax(Node node) {
if (node.right == null) {
final Node nodeLeft = node.left;
node.left = null;// let out gc
count--;
return nodeLeft;
}
node.right = removeMax(node.right);
return node;
}
/**
* 删除二叉搜索树的最大节点
*
* @param node
*/
private void removeMaxNode(Node node) {
Node parentNode = null;
while (node != null) {
parentNode = node;
node = node.right;
}
final Node nodeLeft = node.left;
node.left = null;// let out gc
node.right = nodeLeft;
count--;
}
/**
* 删除二叉树的节点 设p指向待删除的结点，pre指向待删除结点的父亲，则删除操作视如下情况而定：
* （1）若待删除的结点是叶子结点，不妨设pre->right=p(即待删除的结点为其父亲结点的右孩子)，则直接删除p，对应为：pre->right=
* NULL，delete p；
* （2）若待删除的结点只有左子树或右子树，则只需将待删除结点的父亲与左孩子（或右孩子）连接起来，对应为，不妨设pre->right=p,
* 以待删除结点仅有左子树的情况为例（右子树同理），对应为：pre->right=p->left，delete p；
* （3）若待删除结点左右子树都有，则执行如下步骤：
* 总体来说，整个线索是：找到右子树的最小值结点-->连接断开结点-->对最小值结点的上下文做善后工作。
*
* @param key
*/
public void remove(Key key) {
remove(root, key);
}
/**
* 删除二叉树的节点 内部实现 使用递归的方法 返回删除后的二叉树的根节点--迭代法 返回该节点
*
* @param node
* @param key
* @return
*/
private Node remove(Node node, Key key) {
Node parent = root;
while (node != null) {
if (key.compareTo(node.key) > 0) {
parent = node;
node = node.right;
} else if (key.compareTo(node.key) < 0) {
parent = node;
node = node.left;
} else
break;// 当键相等的时候 就查到该节点 此时node就是 要 删除的节点,与parent 断开关联
}
if (node == null)
throw new RuntimeException("没有该键" + key + "对应的节点!");
// 要删除的左节点左节点不存在
if (node.left == null) {
final Node rihtNode = node.right;
if (node.key.compareTo(parent.key) > 0)
parent.right = rihtNode;
else
parent.left = rihtNode;
node.right = null;
count--;
return node;
}
// 要删除的右节点不存在(其中左右都为null不用考虑,处理包含在其中)
if (node.right == null) {
final Node leftNode = node.left;
if (node.key.compareTo(parent.key) > 0)
parent.left = leftNode;
else
parent.right = leftNode;
node.left = null;
count--;
return node;
}
// 要删除的左右节点都存在
if (node.right != null && node.left != null) {
// 找到该替换该节点的节点
Node successor = new Node(mininum(node.right));
successor.right = removeMin(node.right);
if (node.key.compareTo(parent.key) > 0)
parent.right = successor;
else
parent.left = successor;
successor.left = node.left;
node.left = null;// let out gc
node.right = null;// let out gc
return node;
}
return node;
}
/**
* 删除节点------->递归法 返回删除节点后二叉搜索树的根节点
*
* @param node
* @param key
* @return
*/
private Node removeNode(Node node, Key key) {
if (node == null)
return node;
if (key.compareTo(node.key) > 0) {
node.right = removeNode(node.right, key);
return node;
} else if (key.compareTo(node.key) < 0) {
node.left = removeNode(node.left, key);
return node;
} else {
if (node.left == null) {
final Node rNode = node.right;
node.right = null;
count--;
return rNode;
}
if (node.right == null) {
final Node lNode = node.left;
node.left = null;
count--;
return lNode;
}
if (node.right != null && node.left != null) {
Node successor = new Node(mininum(node.right));
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = null;
node.right = null;
return successor;
}
return node;
}
}
/**
* 通过键 key获取节点
*
* @param key
* @return
*/
public Node node(Key key) {
Node node = node(root, key);
return node;
}
/**
* 用迭代法实现-通过键是获取节点
*
* @param node
* @param key
* @return
*/
private Node node(Node node, Key key) {
while (node != null) {
if (key.compareTo(node.key) > 0)
node = node.right;
else if (key.compareTo(node.key) < 0)
node = node.left;
else
return node;
}
return null;
}
/**
* 判断该键是否在 二叉搜索树
*
* @param key
* @return
*/
public boolean contain(Key key) {
return contain(root, key);
}
/**
* 递归法
*
* @param node
* @param key
* @return
*/
private boolean contain(Node node, Key key) {
if (node == null)
return false;
if (key.compareTo(node.key) == 0)
return false;
else if (key.compareTo(node.key) > 0)
return contain(node.right, key);
else
return contain(node.left, key);
}
/**
* 前序遍历(深度遍历的一种) Traversal
*/
public void preOrder() {
if (root != null)
preOrder(root);
}
/**
* 满足 根-->左--->右 (递归法)
*
* @param node
*/
private void preOrder(Node node) {
if (node != null)
return;
System.out.println("节点键的为:" + node.key + " 节点的值为:" + node.value);
preOrder(node.left);
preOrder(node.right);
}
/**
* 中序遍历(深度遍历的一种)Traversal 中序遍历二叉搜索树 满足从小到大顺序 (排序)
*/
public void inOrder() {
if (root != null)
inOrder(root);
}
/**
* 中序遍历 --->递归法
*
* @param node
*/
private void inOrder(Node node) {
if (node == null)
return;
inOrder(node.left);
System.out.println("节点键的为:" + node.key + " 节点的值为:" + node.value);
inOrder(node.right);
}
/**
* 后序遍历(深度遍历的一种)Traversal
*/
public void postOrder() {
if (root != null)
postOrder(root);
}
/**
* 中序遍历 --->递归法
*
* @param node
*/
private void postOrder(Node node) {
if (node == null)
return;
postOrder(node.left);
postOrder(node.right);
System.out.println("节点键的为:" + node.key + " 节点的值为:" + node.value);
}
/**
* 层序遍历(广度优先遍历)
*
* @param node
*/
public void levelOrder() {
if (root != null)
levelOrder(root);
}
/**
* 利用队列 (Queue)先进先出
*
* @param node
*/
private void levelOrder(Node node) {
Queue<Node> queue = new LinkedList<Node>();
queue.offer(node);
while (!queue.isEmpty()) {
Node element = queue.poll();
System.out.println("节点键的为:" + element.key + " 节点的值为:" + element.value);
if (element.left != null)
queue.offer(element.left);
if (element.right != null)
queue.offer(element.right);
}
}
/**
* 二叉树的节点用一个内部类来实现
*
* @author caibixiang
*
*/
private class Node {
private Key key;// 键 (满足根节点的键小于右节点中所有节点，大于左节点的中所有节点)
private Value value;// 值
private Node left;// 左节点
private Node right;// 又节点
private Node(Key key, Value value) {
this.key = key;
this.value = value;
this.left = null;
this.right = null;
}
private Node(Node node) {
this.key = node.key;
this.value = node.value;
this.left = node.left;
this.right = node.right;
}
}
public static void main(String[] args) {
int N = 100;
// 创建一个数组,包含[0....N]的所有的元素
Integer[] arr = new Integer[N];
for (int i = 0; i < N; i++)
arr[i] = new Integer(i);
// 打乱数组顺序
for (int i = 0; i < N; i++) {
int pos = (int) (Math.random() * (i + 1));
Integer t = arr[pos];
arr[pos] = arr[i];
arr[i] = t;
}
// 由于我们实现的二分搜索树不是平衡二叉树
// 所以如果按照顺序插入一组数据，我们的二分搜索树会退化成为一个链表
// 平横二叉树的实现下一节来实现(avl树)
BinaryTree<Integer, String> bst = new BinaryTree<Integer, String>();
for (int i = 0; i < N; i++)
bst.insert(new Integer(arr[i]), Integer.toString(arr[i]));
bst.inOrder();// 升序排列
bst.remove(5);
bst.remove(7);
bst.remove(71);
bst.remove(23);
bst.remove(34);
bst.remove(56);
System.out.println(bst.size());
bst.inOrder();// 升序排列
}
}