二叉搜索树的定义: 若左子树不为空,则左子树上所有节点的值都小于根节点的值; 若右子树不为空,则右子树上所有节点的值都大于根节点的值。 树中不会有重复的元素。
二叉搜索树最左侧结点一定是最小的,最右侧一定是最大的; 对二叉搜索树进行中序遍历,一定能够得到一个有序序列。
目录
以查找数据23为例。
从根节点往下遍历,遇到比23大的数据,往其左子树遍历,如果比23小的数据,往其右子树遍历,直到当前结点是我们需要查找的结点或为空结点为止。
代码:
public TreeNode search(int key) {
TreeNode tmp = root;
while(tmp != null){
if(tmp.key > key){
tmp = tmp.left;
}else if(tmp.key < key){
tmp = tmp.right;
}else{
return tmp;
}
}
return null;
}
不能插入树中已有的元素!!!
以插入数据18为例。
从根节点往下遍历,遇到比18大的数据,往其左子树遍历,如果比18小的数据,往其右子树遍历,直到当前结点为空,插入数据18。
代码:
public boolean insert(int key) {
if(root == null){
root = new TreeNode(key);
return true;
}
TreeNode p = root;
TreeNode c = root;
while(c != null){
p = c;
if(c.key < key){
c = c.right;
}else if(c.key > key){
c = c.left;
}else{
return false;
}
}
if(p.key < key){
p.right = new TreeNode(key);
}else{
p.left = new TreeNode(key);
}
return true;
}
设待删除的结点为tmp,其父母亲结点为parent
(一)tmp为左子树结点,有如下情况:
(二)tmp为右子树结点,有如下情况:
(三)tmp为根结点,有如下情况:
代码:
public boolean remove(int key) {
TreeNode tmp = root;
TreeNode parent = root;//标记父母亲结点
while(tmp != null){
if(tmp.key > key){
parent = tmp;
tmp = tmp.left;
}else if(tmp.key < key){
parent = tmp;
tmp = tmp.right;
}else{
break;
}
}
if(tmp == null)
return false;
//删除操作
//为左孩子
if(tmp == parent.left){
if(tmp.left == null){
parent.left = tmp.right;
}else if(tmp.right == null){
parent.left = tmp.left;
}else{
//tmp左右孩子都不为空情况
func(tmp);
}
} else if(tmp == parent.right){
//右孩子
if(tmp.left == null){
parent.right = tmp.right;
}else if(tmp.right == null){
parent.right = tmp.left;
}else {
//tmp左右孩子都不为空情况
func(tmp);
}
}else {
//根节点
if(root.left == null){
root = root.right;
}else if(root.right == null){
root = root.left;
}else{
//tmp左右孩子都不为空情况
func(root);
}
}
return true;
}
public void func(TreeNode tmp){
if(tmp == null) return;
TreeNode ret = find(tmp);
int key = ret.key;
remove(ret.key);
tmp.key = key;
}
//找到tmp结点右孩子的最左边
public TreeNode find(TreeNode tmp){
TreeNode tmp1 = tmp;
tmp = tmp.right;
while(tmp != null){
tmp1 = tmp;
tmp = tmp.left;
}
return tmp1;
}
最优情况下:二叉搜索树为完全二叉树,其平均比较次数为:log2 (n)
最坏情况下:二叉搜索树退化为单支树,其平均比较次数为:n/2
public class BinarySearchTree {
static class TreeNode {
public int key;
public TreeNode left;
public TreeNode right;
TreeNode(int key) {
this.key = key;
}
}
public TreeNode root;
/**
* 插入一个元素
* 不能插入二叉搜索树当中已有的数据,
* 否则返回false
* @param key
*/
public boolean insert(int key) {
if(root == null){
root = new TreeNode(key);
return true;
}
TreeNode p = root;
TreeNode c = root;
while(c != null){
p = c;
if(c.key < key){
c = c.right;
}else if(c.key > key){
c = c.left;
}else{
return false;
}
}
if(p.key < key){
p.right = new TreeNode(key);
}else{
p.left = new TreeNode(key);
}
return true;
}
//查找key是否存在
public TreeNode search(int key) {
TreeNode tmp = root;
while(tmp != null){
if(tmp.key > key){
tmp = tmp.left;
}else if(tmp.key < key){
tmp = tmp.right;
}else{
return tmp;
}
}
return null;
}
//删除key的值
public boolean remove(int key) {
TreeNode tmp = root;
TreeNode parent = root;//标记父母亲结点
while(tmp != null){
if(tmp.key > key){
parent = tmp;
tmp = tmp.left;
}else if(tmp.key < key){
parent = tmp;
tmp = tmp.right;
}else{
break;
}
}
if(tmp == null)
return false;
//删除操作
//为左孩子
if(tmp == parent.left){
if(tmp.left == null){
parent.left = tmp.right;
}else if(tmp.right == null){
parent.left = tmp.left;
}else{
//tmp左右孩子都不为空情况
func(tmp);
}
} else if(tmp == parent.right){
//右孩子
if(tmp.left == null){
parent.right = tmp.right;
}else if(tmp.right == null){
parent.right = tmp.left;
}else {
//tmp左右孩子都不为空情况
func(tmp);
}
}else {
//根节点
if(root.left == null){
root = root.right;
}else if(root.right == null){
root = root.left;
}else{
//tmp左右孩子都不为空情况
func(root);
}
}
return true;
}
public void func(TreeNode tmp){
if(tmp == null) return;
TreeNode ret = find(tmp);
int key = ret.key;
remove(ret.key);
tmp.key = key;
}
//找到tmp结点右孩子的最左边
public TreeNode find(TreeNode tmp){
TreeNode tmp1 = tmp;
tmp = tmp.right;
while(tmp != null){
tmp1 = tmp;
tmp = tmp.left;
}
return tmp1;
}
}
代码链接在这里哦~
二叉搜索树 · Yjun6/DataStructrue@4f9a2c1 (github.com)
这篇博客如果对你有帮助,给博主一个免费的点赞以示鼓励,欢迎各位🔎点赞👍评论收藏⭐,谢谢!!!