二叉查找树建立以及增删-Java版

维基百科

二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树（英语：ordered binary tree），排序二叉树（英语：sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

 1.若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

 2.若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；

 3.任意节点的左、右子树也分别为二叉查找树；

 4.没有键值相等的节点。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、multiset、关联数组等。

二叉查找树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉查找树的存储结构。中序遍历二叉查找树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉查找树变成一个有序序列，构造树的过程即为对无序序列进行查找的过程。每次插入的新的结点都是二叉查找树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索、插入、删除的复杂度等于树高，期望，最坏（数列有序，树退化成线性表）。

虽然二叉查找树的最坏效率是O(n),但它支持动态查询，且有很多改进版的二叉查找树可以使树高为,如SBT,AVL树，红黑树等。

public class SearchBinaryTree {
 private TreeNode root;

 public void deleteTreeNode(int key) throws Exception {
 TreeNode node = searchNode(key);
 if (node != null) {
 //删除节点
 deleteNode(node);
 } else {
 throw new Exception("节点不存在");
 }
 }

 //删除节点的4种情况
 private void deleteNode(TreeNode node) throws Exception {
 if (node == null) {
 throw new Exception("节点不存在");
 }
 TreeNode parent = node.parent;
 //无左孩子无右孩子
 if (node.leftChild == null && node.rightChild == null) {

 if (parent.leftChild == node) {
 parent.leftChild = null;
 } else if (parent.rightChild == node) {
 parent.rightChild = null;
 }
 return;
 }
 //有左孩子无右孩子
 if (node.leftChild != null && node.rightChild == null) {
 if (parent.leftChild == node) {
 parent.leftChild = node.leftChild;
 } else if (parent.rightChild == node) {
 parent.rightChild = node.leftChild;
 }
 //更新向上索引 修复标识的已知bug
 node.leftChild.parent=parent;
 return;
 }
 //无左孩子有右孩子
 if (node.rightChild != null && node.leftChild == null) {
 if (parent.leftChild == node) {
 parent.leftChild = node.rightChild;
 } else if (parent.rightChild == node) {
 parent.rightChild = node.rightChild;
 }
 //更新向上索引 修复标识的已知bug
 node.rightChild.parent=parent;
 return;
 }
 //左右都有时找后继节点
 TreeNode next = getNextNode(node);
 deleteNode(next);
 node.data = next.data;
 }

 /**
 * 找后继节点
 * @param node
 * @return
 */ private TreeNode getNextNode(TreeNode node) {
 if (node == null) {
 return null;
 }
 if (node.rightChild!=null){
 //找最小节点
 return getMinTreeNode(node.rightChild);
 }else {
 //右子树为空(单独判断,防止找后继节点单独使用)
 TreeNode parent=node.parent;
 while (parent!=null&&node==parent.rightChild){
 node=parent;
 parent=parent.parent;
 }
 return parent;
 }
 }

 //当要删除的节点左右不为空时,找最小的节点(右子树的最左节点)
 private TreeNode getMinTreeNode(TreeNode node){
 if (node==null){
 return null;
 }
 while (node.leftChild!=null){
 node=node.leftChild;
 }
 return node;
 }

 /**
 * 从根节点开始查找,直到找到
 * @param key
 * @return
 */ private TreeNode searchNode(int key) {
 TreeNode node = root;
 if (node == null) {
 return null;
 }
 while (node != null & key != node.data) {
 if (key < node.data) {
 node = node.leftChild;
 } else {
 node = node.rightChild;
 }
 }
 return node;
 }

 /**
 * 数据插入操作
 * @param data
 * @return
 */ public TreeNode put(int data) {
 TreeNode parent = null;
 TreeNode node = new TreeNode(0, data);
 if (root == null) {
 root = node;
 }
 //不是根节点就是从根节点开始 直到找到一个合适的节点并且左右节点为空
 node = root;
 while (node != null) {
 parent = node;
 if (node.data > data) {
 node = node.leftChild;
 } else if (node.data < data) {
 node = node.rightChild;
 } else {
 return node;
 }
 }

 //将节点添加到合适的位置 比根节点小放左边 大放右边
 node = new TreeNode(0, data);
 if (parent.data > data) {
 parent.leftChild = node;
 } else {
 parent.rightChild = node;
 }
 node.parent = parent;
 return node;
 }

 //二叉查找树中序遍历打印数据刚好为排序数据
 public void midOder(TreeNode node) {
 if (node == null) {
 return;
 } else {
 midOder(node.leftChild);
 System.out.print(node.data+" ");
 midOder(node.rightChild);
 }
 }

 public static void main(String[] args) {
 SearchBinaryTree searchBinaryTree = new SearchBinaryTree();
 int[] datas = new int[]{30, 21, 23, 11, 43, 65, 22, 90, 78, 88};
 for (int i : datas)
 searchBinaryTree.put(i);
 searchBinaryTree.midOder(searchBinaryTree.root);
 System.out.println();
 try {
 searchBinaryTree.deleteTreeNode(43);
 searchBinaryTree.deleteTreeNode(90);
 //已知bug：已删除2个当删除第三个时无法删除
 searchBinaryTree.deleteTreeNode(65);
 searchBinaryTree.deleteTreeNode(88);
 searchBinaryTree.deleteTreeNode(21);
 } catch (Exception e) {
 e.printStackTrace();
 }
 searchBinaryTree.midOder(searchBinaryTree.root);

 }

 //定义一个节点类
 class TreeNode {
 //暂未使用，可考虑用于xx用途 我也不知道 比如说标识？
 private int key;
 private TreeNode leftChild;
 private TreeNode rightChild;
 private TreeNode parent;
 private int data;

 public TreeNode(int key, int data) {
 this.key = key;
 this.leftChild = null;
 this.rightChild = null;
 this.parent = null;
 this.data = data;
 }
 }
}