【数据结构】二叉查找树建立以及增删-Java版


维基百科

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

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

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

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

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

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

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

虽然二叉查找树的最坏效率是O(n),但它支持动态查询,且有很多改进版的二叉查找树可以使树高为O(\log 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;
 }
 }
}

声明:TIL|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA[ZH]协议进行授权

转载:转载请注明原文链接 - 【数据结构】二叉查找树建立以及增删-Java版


Life is very interesting. In the end, some of your greatest pains become your greatest strengths.