java基础二叉搜索树图文详解

java基础二叉搜索树图文详解

目录概念直接实践准备工作：定义一个树节点的类，和二叉搜索树的类。搜索二叉树的查找功能搜索二叉树的插入操作搜索二叉树删除节点的操作-难点性能分析总程序-模拟实现二叉搜索树和java类集的关系总结

概念

直接实践

准备工作：定义一个树节点的类，和二叉搜索树的类。

搜索二叉树的查找功能

假设我们已经构造好了一个这样的二叉树，如下图

我们要思考的第一个问题是如何查找某个值是否在该二叉树中?

根据上述的逻辑，我们来把搜索的方法进行完善。

搜索二叉树的插入操作

根据上述逻辑，我们来写一个插入节点的代码。

搜索二叉树 删除节点的操作 - 难点

再来分析一下：curDummy 和 parentDummy 是怎么找到“替罪羊”的。

总程序 - 模拟实现二叉搜索树

class TreeNode{

public int val;

public TreeNode left;

public TreeNode right;

public TreeNode(int val){

this.val = val;

}

}

public class BinarySearchTree {

TreeNode root;

//在二叉树中 寻找指定 val 值的节点

// 找到了，返回其节点地址；没找到返回 null

public TreeNode search(int key){

TreeNode cur = this.root;

while(cur != null){

if(cur.val == key){

return cur;

}else if(cur.val < key){

cur = cur.right;

}else{

cur = cur.left;

}

}

return null;

}

// 插入操作

puhttp://blic boolean insert(int key){

if(this.root == null){

this.root = new TreeNode(key);

return true;

}

TreeNode cur = this.root;

TreeNode parent = null;

while(cur!=null){

if(key > cur.val){

parent = cur;

cur = cur.right;

}else if(cur.val == key){

return false;

}else{

parent = cur;

cur = cur.left;

}

}

TreeNode node = new TreeNode(key);

if(parent .val > key){

parent.left = node;

}else{

parent.right = node;

}

return true;

}

// 删除操作

public void remove(int key){

TreeNode cur = root;

TreeNode parent = null;

// 寻找 删除节点位置。

while(cur!=null){

if(cur.val == key){

removeNode(cur,parent);// 真正删除节点的代码

break;

}else if(cur.val < key){

parent = cur;

cur = cur.right;

}else{

parent = cur;

cur = cur.left;

}

}

}

// 辅助删除方法：真正删除节点的代码

private void removeNode(TreeNode cur,TreeNode parent){

// 情况一

if(cur.left == null){

if(cur == this.root){

this.root = this.root.right;

}else if( cur == parent.left){

parent.left = cur.right;

}else{

parent.right = cur.right;

}

// 情况二

}else if(cur.right == null){

if(cur == this.root){

this.root = root.left;

}else if(cur == parent.left){

parent.left = cur.left;

}else{

parent.right = cur.left;

}

// 情况三

}else{

// 第二种方法：在删除节点的右子树中寻找最小值，

TreeNode parentDummy = cur;

TreeNode curDummy = cur.right;

while(curDummy.left != null){

parentDummy = curDummy;

curDummy = curDummy.left;

}

// 此时 curDummy 指向的 cur 右子树

cur.val = curDummy.val;

if(parentDummy.left != curDummy){

parentDummy.right = curDummy.right;

}else{

parentDummy.left = curDummy.right;

}

}

}

// 中序遍历

public void inorder(TreeNode root){

if(root == null){

return;

}

inorder(root.left);

System.out.print(root.val+" ");

inorder(root.right);

}

public static void main(String[] args) {

int[] array = {10,8,19,3,9,4,7};

BinarySearchTree binarySearchTree = new BinarySearchTree();

for (int i = 0; i < array.length; i++) {

binarySearchTree.insert(array[i]);

}

binarySearchTree.inorder(binarySearchTree.root);

System.out.println();// 换行

System.out.print("插入重复的数据 9：" + binarySearchTree.insert(9));

System.out.println();// 换行

System.out.print("插入不重复的数据 1：" + binarySearchTree.insert(1));

System.out.println();// 换行

binarySearchTree.inorder(binarySearchTree.root);

System.out.println();// 换行

binarySearchTree.remove(19);

System.out.print("删除元素 19 ：");

binarySearchTree.inorder(binarySearchTree.root);

System.out.println();// 换行

System.out.print("查找不存在的数据50 ：");

System.out.println(binarySearchTree.search(50));

System.out.print("查rqRTch找存在的数据 7：");

System.out.println(binarySearchTree.search(7));

}

}

性能分析

和 java 类集的关系

TreeMap 和 TreeSet 即 java 中利用搜索树实现的 Map 和 Set；实际上用的是红黑树，而红黑树是一棵近似平衡的二叉搜索树，即在二叉搜索树的基础之上 + 颜色以及红黑树性质验证，关于红黑树的内容，等博主学了，会写博客的。

总结

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。