java二叉树查找,数据结构二叉查找树
00-1010前言属性实现节点结构初始化插入节点查找节点最后删除节点
今天00-1010，leetcode每日第450题是关于删除二叉查找树的节点。该问题要求删除具有指定值的节点，并保持二叉查找树的属性不变。写完后，我觉得这个问题很好地突出了二叉查找树的特点。首先，您需要找到指定的节点，然后删除节点并保持二叉查找树的属性不变。我想用这个问题来谈谈二叉查找树。
二叉查找树作为一种经典的数据结构，具有快速插入和删除链表的特点，以及优秀的查询效率，因此被广泛应用。例如，这种数据结构通常用在文件系统和数据库系统中，用于高效的排序和检索操作。同时因为实现也比较简单，所以作为一些公司算法题的入门题目是很常见的事情，需要掌握~
所有的源代码都放在我的github里了，包括之前的算法和日常提问。可以查一下数据结构和算法~
00-1010二叉查找树要么是一棵空树，要么是一棵二叉树，具有以下属性。如果当前节点有左子树，则左子树上的每个节点值都小于或等于当前节点值。如果当前节点有一个右子树，则右子树上的每个节点值都大于或等于当前节点值。根据这个性质，当我们第一次遍历二叉查找树时，得到的序列应该是一个从小到大的非递减序列。同时，在搜索指定值时，只需要与当前节点进行比较，根据相对大小在左子树或右子树上进行搜索。
00-1010根据二叉查找树的性质，我们需要实现插入节点、查询节点和删除节点的功能。
目录
公共类TreeNode { public int val公共TreeNode left公共TreeNode权限；public TreeNode(){ } public TreeNode(int val){ this . val=val；} public TreeNode(int val，TreeNode left，TreeNode right){ this . val=val；this.left=leftthis.right=right}}
00-1010这里我们假设所有节点值都大于0，并初始化一个头节点。Ps:对于树、链表等数据结构，为了使首节点的操作与其他节点一致，便于操作，常用的方法是增加一个额外的头节点指向首节点。
TreeNode头；private init(){//添加一个头节点head=new TreeNode(-1)；}
00-1010我们从开始节点遍历二叉查找树。如果当前节点值小于或等于插入节点值，则插入节点在当前节点的右子树上；否则，如果当前节点的左子树是空的，它将被插入。
/* * *插入新节点，假设所有新节点都大于0 * @param val插入节点值* @ return inserted node */public treenode Insert(intval){ treenode temp=head；while(true){ if(temp . valval){/val应该在右边的子树if (null！{ temp=temp.right继续；} else { temp . right=new TreeNode(val)；返回temp.right} }//应该在左子树if (null！=temp . left){ temp=temp . left；继续；} temp . left=new TreeNode(val)；
return temp.left; } }
查找节点
查找节点的步骤其实在插入节点的时候已经有体现，其实就是将查找值与当前节点比较，大于当前节点走右子树，小于当前节点走左子树，直到值匹配返回节点，或者没有找到返回null。ps：这里为了后面方便实现删除，同时返回了当前节点以及当前节点的父节点，这里使用了commons-lang3包下的Pair工具。
/** * 搜索节点值 * @param val * @return */ public Pair<TreeNode, TreeNode> find(int val) { TreeNode temp = head.right; TreeNode parent = head; while (null != temp) { if (temp.val == val) { return Pair.of(temp, parent); } parent = temp; if (temp.val < val) { //在右子树上 temp = temp.right; continue; } temp = temp.left; } return null; }
删除节点
删除节点时候我们需要先找到删除节点的位置，然后做对应操作。有三种情况：
1.如果删除的是叶子节点直接删除
2.如果删除的节点只有左子树或者右子树，则直接将左子树或者右子树节点放在删除节点位置
3.如果删除节点同时有左子树和右子树，则将右子树节点放在原来节点位置，将左子树放在右子树最左边节点左子树上（反之将左子树放在原来节点位置，右子树放在左子树最右边节点右子树上也可）
/** * 1.如果删除的是叶子节点直接删除， * 2.如果删除的节点只有左子树或者右子树，则直接将左子树或者右子树节点放在删除节点位置 * 3.如果删除节点同时右左子树和右子树，则将右子树节点放在原来节点位置，将左子树放在右子树最左边节点左子树上 * @param val */ public void delete(int val) { //找到删除节点，删除节点父节点 Pair<TreeNode, TreeNode> curAndParent = this.find(val); TreeNode cur = curAndParent.getLeft(); TreeNode parent = curAndParent.getRight(); //记录删除当前节点后，当前节点位置放置哪个节点 TreeNode changed; if (null == cur.left && null == cur.right) { changed = null; } else if (null != cur.left && null != cur.right) { TreeNode tempRight = cur.right; while (null != tempRight.left) { //找到最左侧节点 tempRight = tempRight.left; } tempRight.left = cur.left; changed = cur.right; } else if (null != cur.left) { changed = cur.left; } else { changed = cur.right; } if (parent.left == cur) { parent.left = changed; return; } parent.right = changed; }
最后
二叉搜索树易于实现，思想简单，被广泛应用，平均查找，插入，删除时间均为O(logn)，但是在删除或者插入节点的过程中，可能因为数据的特点，使得二叉搜索树极端情况下退化为一棵仅有左子树或者右子树的，这时候就跟普通顺序查找无异，时间复杂度变为O(n),因此后面出现了平衡二叉搜索树，左右子树高度相差不超过1，通过旋转将二叉树高度降低，使得查找、插入、删除在平均和最坏情况下都是O(logn)。比如常见的AVL自平衡二叉搜索树，红黑树等等。
到此这篇关于Java数据结构之二叉搜索树详解的文章就介绍到这了,更多相关Java二叉搜索树内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。