怎样做好网站建设设计,怎么建立一个网站搜关键词会跳出,天津信息港,自己做网站可以揽业务吗文章目录 一、搜索树二、使用代码实现一棵二叉搜索树1.查找2.插入3.删除#xff08;重点#xff09; 总结 一、搜索树
二叉搜索树又称二叉排序树#xff0c;它或者是一棵空树#xff0c;或者是具有以下性质的二叉树: 若它的左子树不为空#xff0c;则左子树上所有节点的值… 文章目录 一、搜索树二、使用代码实现一棵二叉搜索树1.查找2.插入3.删除重点 总结 一、搜索树
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树: 若它的左子树不为空则左子树上所有节点的值都小于根节点的值 若它的右子树不为空则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 仔细观察上图可以发现二叉搜索树的一个特性 中序遍历二叉搜索树是有序的所以二叉搜索树也被称为二叉排序树
二、使用代码实现一棵二叉搜索树
1.查找
遍历这棵树先从树的根节点开始查找如果树的根节点是我们要查找的元素就返回根节点如果要查找的元素比我们的根节点小就去树的左边寻找如果比我们的根节点大就去树的右边寻找直到遍历完整棵树为止
代码如下 public boolean search(int val) {TreeNode cur root;while (cur ! null) {//左树中去找if(cur.val val) {cur cur.left;//右树中去找}else if(cur.val val) {cur cur.right;}else {return true;}}return false;}2.插入
往二叉搜索树插入一个元素的时候我们要注意两点首先如果二叉搜索树为空则直接令 root 为当前插入的节点即可如果不为空则新的元素会依次与节点比较如果比根节点大则去根的右边比根节点小则去根的左边 首先定义一个 cur 引用当 cur 等于 null 了则表示是我要插入的位置找到了要插入的位置我们还得知道这个位置的父亲节点是谁通过父亲节点将元素插入到该二叉树中
代码如下 public void insert(int val) {if(root null) {root new TreeNode(val);return;}TreeNode cur root;//记录cur的上一个节点TreeNode parent null;while (cur ! null) {if(cur.val val) {parent cur;cur cur.right;}else if(cur.val val) {parent cur;cur cur.left;}else {return;}}//cur为空 将val插入到parent的左树或者右树TreeNode node new TreeNode(val);if(parent.val val) {parent.left node;}else {parent.right node;}}3.删除重点
二叉搜索树中删除一个元素是很麻烦的我们要把每一种情况都列举出来而且在删除完一个元素后还要满足二叉搜素树的性质 设 cur 为要删除的元素parent为待删除结点的双亲结点为首先我们要判断这个二叉搜索树中是否存在要删除的节点这个方法在上面已经写过了找到要删除的节点后再对每一种情况进行删除
1.cur没有左子树 cur 是 root则 root cur.right cur 不是 rootcur 是 parent.left则 parent.left cur.right cur 不是 rootcur 是 parent.right则 parent.right cur.right 图解如下 2.cur没有右子树 cur 是 root则 root cur.left cur 不是 rootcur 是 parent.left则 parent.left cur.left cur 不是 rootcur 是 parent.right则 parent.right cur.left 图解如下 3.cur既有左子树又有右子树 使用替换法进行删除即在 cur 的右子树中一直往左寻找最小的元素将这个最小值赋值给要删除节点的 val 值中接着把这个最小元素的节点删除即可 图解如下 代码如下 public void remove(int val) {TreeNode cur root;TreeNode parent null;while (cur ! null) {if(cur.val val) {parent cur;cur cur.right;}else if(cur.val val) {parent cur;cur cur.left;}else {removeNode(parent,cur);return;}}}private void removeNode(TreeNode parent,TreeNode cur) {//左树为空if(cur.left null) {if(cur root) {root cur.right;}else if(cur parent.left) {parent.left cur.right;}else {parent.right cur.right;}//右树为空}else if(cur.right null) {if(cur root) {root cur.left;}else if(cur parent.left) {parent.left cur.left;}else {parent.right cur.left;}//两个都不为空 使用替换法的方式来删除节点}else {TreeNode t cur.right;TreeNode tp cur;while (t.left ! null) {tp t;t t.left;}cur.val t.val;if(tp.left t) {tp.left t.right;}else {tp.right t.right;}}}总结
插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。 对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多 二叉搜索树在最好的情况下为完全二叉树查找的平均比较次数为logn 二叉搜索树在最差的情况下退化成但分支查找的平均比较次数为n/2 注意 二叉搜索树不要求是完全二叉树或满二叉树甚至会出现单分支的二叉搜索树所以针对这种特殊的情况进行了优化也就延申出了 AVL树当发现二叉搜索树左右子树高度差太大会自动旋转以致平衡避免旋转的次数太多又引入了红黑树给节点增加了颜色细节部分后期讲解这里有个概念即可
