网站app建设图片素材,网站开发的实施方案,工程建设指挥部网站,太原网络推广公司文章目录 二叉搜索树的性质二叉搜索树的操作遍历查找插入删除 二叉搜索树又称为二叉排序树#xff0c;是一种具有一定性质的特殊的二叉树#xff1b;
二叉搜索树的性质 若它的左子树不为空#xff0c;则左子树上结点的值均小于根节点的值#xff1b; 若它的右子树不为空是一种具有一定性质的特殊的二叉树
二叉搜索树的性质 若它的左子树不为空则左子树上结点的值均小于根节点的值 若它的右子树不为空则右子树上结点的值均大于根节点的值 二叉搜索树的左右子树均为二叉搜索树 二叉搜索树的操作
遍历
关于二叉树的遍历方式有前序、中序、后序三种对于二叉搜索树而言使用中序遍历得到的结点序列是有序的
public class BinarySearchTree {
//首先创建相关的结点结构static class TreeNode {public int key;public TreeNode left;public TreeNode right;TreeNode(int key){this.keykey;}}public TreeNode root;//进行中序遍历public void inorder(TreeNode root){if (rootnull) return;inorder(root.left);System.out.println(root.key );inorder(root.right);}
}查找
基于二叉搜索树的性质当根节点不为空时可以根据根节点的值与待查找的值key之间的关系进行查找即若根节点的值大于key则在其左子树进行查找若根节点的值小于key则到其右子树进行查找直到最终根节点的值为空或没有找到key则结束
public TreeNode search(int key){//定义一个cur从根节点的位置开始查找TreeNode curroot;while (cur!null){//结点的值与key相等找到并返回if (cur.keykey){return cur;}else if(cur.keykey){//结点的值小于key去其右子树进行查找curcur.right;}else {//结点的值大于key去其左子树进行查找curcur.left;}}//没有找到没有该值return null;}插入
插入操作可以分为2种情况当根节点为空时直接插入到根节点即可当根节点不为空时就需要遵守搜索树的性质按照之前查找的逻辑将节点插入合适的位置保证不破坏其二叉搜索树的结构 public boolean insert (int key){//结点为空直接进行插入if (rootnull){rootnew TreeNode(key);return true;}//结点不为空//定义一个cur寻找插入的合适位置TreeNode curroot;//记录cur的位置或走向TreeNode parentnull;//寻找合适的插入位置使用parent记录while (cur!null){if (cur.keykey){parentcur;curcur.right;}else if (cur.keykey){parentcur;curcur.left;}else{//不可以插入相同的数据return false;}}//创建新结点TreeNode nodenew TreeNode(key);if (parent.keykey){parent.rightnode;}else{parent.leftnode;}return true;}删除
删除操作相较于前面的查找插入操作要略显复杂大致可以分为下面几种情况
设待删除的结点为cur待删除节点的双亲结点为parent
cur.leftnull;
cur是root; cur不是root,又可以分为2种情况
cur是其双亲结点parent的左结点 cur是其双亲结点parent的右结点 cur.rightnull;
cur为root cur不是root,又可以分为2种情况
cur是其双亲结点parent的左结点 cur是其双亲结点parent的右结点 cur.left!null cur.right!null;
使用替换法进行删除使用待删除节点的右子树的最小值将待删除节点进行替换再删除最小值的结点即可 下面是具体的代码实现
public boolean remove(int key){TreeNode curroot;TreeNode parentnull;//寻找删除的结点的位置while (cur!null){if (cur.keykey){parentcur;curcur.right;}else if(cur.keykey){//调用removeNode方法进行具体的删除removeNode(parent,cur);return true;}else{parentcur;curcur.left;}}return false;}private void removeNode(TreeNode parent, TreeNode cur) {//第一种情况if (cur.leftnull){if (curroot){rootcur.right;}else if(curparent.left){parent.leftcur.right;}else {parent.rightcur.right;}//第二种情况}else if(cur.rightnull){if (curroot){rootcur.left;}else if(curparent.left){parent.leftcur.left;}else {parent.rightcur.left;}}else{//第三种情况使用替换法TreeNode targetParentcur;TreeNode targetcur.right;//寻找最小值while (target.left!null){targetParenttarget;targettarget.left;}//进行替换cur.keytarget.key;//删除那个最小值if (targettargetParent.left){targetParent.lefttarget.right;}else{targetParent.righttarget.right;}}}对于这样一棵二叉搜索树而言一般情况下结点所处的位置越深需要进行比较的次数就越多。因此根据结点插入的次序不同就可能得到不同结构的二叉树 最好情况下得到一棵完全二叉树的结构平均比较次数达到logN(以2为底) 最坏情况下得到一棵单分支树平均比较次数为N/2; over!
