logo设计免费生成器在线,网站搜索优化排名,甜妹妹福利wordpress,.net网站搭建1、什么是二叉搜索树二叉搜索树又称为二叉排序树#xff0c;二叉也就说明它跟二叉树一样最多只能有两个度#xff0c;它可以是棵空树#xff0c;也可以不是棵空树#xff0c;当它不是棵空树的时候需要具备以下的性质#xff1a;若它的左树不为空#xff0c;那么它的左树上…1、什么是二叉搜索树二叉搜索树又称为二叉排序树二叉也就说明它跟二叉树一样最多只能有两个度它可以是棵空树也可以不是棵空树当它不是棵空树的时候需要具备以下的性质若它的左树不为空那么它的左树上的所有结点的值都要小于根节点的值若它的右树不为空那么它的右树上的所有结点的值都要大于根节点的值它的左右子树分别也都为二叉搜索树二叉搜索树其实也是棵二叉树但是它跟二叉树的不同点也就在上述的三个性质上面2、模拟实现二叉搜索树那接下来我们就来模式实现一棵二叉搜索树首先我们先要创建一个二叉搜索树类用来模拟实现二叉搜索树public class BinarySearchTree {}那么接下来我们就可以将所有模拟实现的二叉搜索树的属性以及方法全部放入这个 BinarySearchTree 这个类中二叉搜索树也是树那么树都是由节点构成的。那么我们就需要创建一个内部类用来构建节点2.1 内部类通过内部类来创建节点//节点
public static class Node {private int key;private Node left;private Node right;public Node(int key) {this.key key;}
}key数据域left 左孩子right右孩子2.2 属性private Node root null;用来存储根节点2.3 方法2.3.1 获取根节点public Node getRoot() {return root;
}2.3.2 判空判断这颗树是否为空树//判空
public boolean isEmpty(Node root) {if (root null) {return true;}return false;
}2.3.3 插入//插入
public boolean insert(int key) {if (isEmpty(root)) {root new Node(key);return true;}//查找插入的位置Node cur root;Node parent null;while (cur ! null) {if (key cur.key) {return false;} else if (key cur.key) {parent cur;cur cur.left;} else {parent cur;cur cur.right;}}Node node new Node(key);if (key parent.key) {parent.left node;} else {parent.right node;}return true;
}插入操作就是插入一个节点首先进入方法判断根节点root是否为空如果为空直接插入在根节点的位置然后返回true如果 root 不为空就按照查找的逻辑确定插入的位置进行插入新节点假设当前的二叉搜索树如下现在需要在这颗二叉搜索树上插入 5 这个节点应该如何插入答因为root 不为空所以就要按照查找的逻辑确定插入的位置。按照二叉搜索树的性质进行比较循环比较让插入节点的值跟cur节点的值进行比较如果相等直接返回false如果小于就让parent指向cur目前所指向的节点然后再让cur等于cur.left如果大于就让parent指向cur目前所指向的节点然后再让cur等于cur.right。当cur为null的时候就跳出循环此时这个位置就是新节点该插入的位置此时parent就是新节点的父节点。跳出循环判断新节点插入parent节点的右孩子还是左孩子位置然后插入即可插入完后后返回true注可以根据插入操作构造一棵二叉搜索树2.3.4 查找//查找
public Node search(int key) {Node cur root;while (cur ! null) {if (key cur.key) {return cur;} else if(key cur.key) {cur cur.left;} else {cur cur.right;}}return null;
}若根节点不为空就循环比较key的值是否与cur.key的值相等若相等就找到了直接返回即可若不相等就比较key与cur.key的大小关系如果小于cur就等于cur.left如果大于 cur 就等于 cur.right当cur 为空是就跳出循环说明这棵二叉搜索树中没有这个节点2.3.5 删除节点//删除
public void remove(int key) {Node cur root;Node parent null;while (cur ! null) {if (key cur.key) {removeNode(parent,cur);break;} else if (key cur.key) {parent cur;cur cur.left;} else {parent cur;cur cur.right;}}
}public void removeNode(Node parent,Node 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 {Node target cur.right;Node targetParent cur;while (target.left ! null) {targetParent target;target target.left;}cur.key target.key;if (target targetParent.right) {targetParent.right target.right;} else {targetParent.left target.right;}}
}首先得找到要删除得节点找到之后调用removeNode方法将这个要删除得节点以及它的父节点传过去在 removeNode 方法中会判断三种情况①第一种情况要删除节点的左节点为空这一种情况中有可以分为以下几种情况根节点就是要删除的节点因为删除的节点的左节点为空所以直接让根节点等于它的右节点即可要删除的节点是它父节点的左节点因为删除的节点的左节点为空所以直接让父节点的左节点等于要删除节点的右节点要删除的节点是它父节点的右节点因为删除的节点的左节点为空所以直接让父节点的右节点等于要删除节点的右节点②第二种情况要删除节点的右节点为空这一种情况中有可以分为以下几种情况根节点就是要删除的节点因为删除的节点的右节点为空所以直接让根节点等于它的左节点即可要删除的节点是它父节点的左节点因为删除的节点的右节点为空所以直接让父节点的左节点等于要删除节点的左节点要删除的节点是它父节点的右节点因为删除的节点的右节点为空所以直接让父节点的右节点等于要删除节点的左节点③第三种情况当要删除的节点左右两边的节点都不为空2.3.6 打印二叉搜索树//打印
public void print(Node root) {if (isEmpty(root)) {return;}print(root.left);System.out.println(root.key);print(root.right);
}打印二叉搜索树其实跟中序打印二叉树是一样的打印二叉搜索树打印出来的其实是有序的因为二叉搜索树上述的三个性质
