一、定义与概念
1、二叉查找树又称为二叉排序树,它是一种特殊二叉树。
二叉查找树的定义为一颗空树,或满足如下性质的树:
①左子树非空,则左子树所有结点的值均小于根结点的值。
②右子树非空,则右子树所有结点的值均大于(或大于等于)根结点的值。
③左右子树也递归的定义为二叉查找树
二、二叉查找树的操作
1、结点的存储结构
public class TreeNode { int data; TreeNode lchild; TreeNode rchild; TreeNode(int s) { data = s; } public String toString() { return String.valueOf(data); } }
2、二叉查找树的创建
step1:在BST树中插入一个节点
[算法思想]
①如果BST树是空树,则待插入的key值成为BST树的根。
②若BST树非空,则key与二叉树的根进行比较。(这里的根是广义的,即可表示BST子树的根)
a. key < bst.data,则将key插入左子树
b. key >= bat.data,则将key插入右子树
从算法的描述中就可以看出,这里是递归实现的。
private static int[] tree = {24,53,90,12,28,45}; TreeNode insertBST(TreeNode bst, int key) { if(bst == null) { bst = new TreeNode(key); return bst; }else { if(key < bst.data) { bst.lchild = insertBST(bst.lchild,key); }else { bst.rchild = insertBST(bst.rchild,key); } return bst; } }
step2:创建一颗BST树
TreeNode CreateBST() { TreeNode bst = null; for(int key : tree) { bst = insertBST(bst,key); } return bst; }
3、二叉查找树的查找
[算法思想]:首先将待查找的key值与根结点关键字值比较
①key = bst.data,则找到退出
②key < bst.data,则查找左子树
③key > bst.data,则查找右子树
递归实现:
boolean searchBST(TreeNode bst, int key) { if(bst == null) { return false; }else { if(bst.data == key) { return true; }else if(bst.data > key) { return searchBST(bst.lchild,key); }else { return searchBST(bst.rchild,key); } } }
非递归实现:查找的思想就是遍历嘛,这里使用循环来实现。
TreeNode searchBST1(TreeNode bst, int key) { if(bst == null) { return null; }else { TreeNode p = bst; while(p != null) { if(p.data == key) { return p; }else if(p.data > key) { p = p.lchild; }else { p = p.rchild; } } return null; } }
4、二叉查找树的删除
删除操作要保证,删除结点之后还是一颗BST树,这里细节和情况还是挺多的,有点难哟。
[算法思想]:在这里我们假设,如果BST树不空,则BST树的右子树存在。其实BST右子树空不空对算法的实现是没有影响的。
(1)首先,设置p指针遍历树,查找到要删除的节点,设置f指针,f指向p的双亲节点
TreeNode p = bst; TreeNode f = null; while(p != null) { if(key == p.data) { break; }else if(key < p.data) { f = p; p = p.lchild; }else { f = p; p = p.rchild; } }
(2)p.lchild == null 左子树空
情况①f == null 要删除的是根结点
情况②f.lchild == p p是f的左孩子,则将p的右子树改为f的右子树
情况③f.rchild == p p是f的右孩子 ,则将p的右子树改为f的左子树
if(p.lchild == null) { if(f == null) { return bst = p.rchild; }else if(f.lchild == p){ f.lchild = p.rchild; }else if(f.rchild == p) { f.rchild = p.rchild; } }
就算p的右子树为空也不影响什么。
(3)p的左子树不为空
设置指针s、q,q指向s的前驱节点
步骤①将s指针移到,p左子树的最右端(即中序遍历p的直接前驱节点)
步骤②交换s与p节点的值(s是p左子树中的最大值了)
步骤③
情况a if(s结点就是 p的左孩子结点) ,则q.lchild = s.lchild
情况b else 则q.rchild = s.lchild
else { TreeNode s = null; TreeNode q = p; s = p.lchild; while(s.rchild!=null) { q = s; s = s.rchild; } if(q == p) { q.lchild = s.lchild;} else { q.rchild = s.lchild;} p.data = s.data; }
完整代码:
TreeNode deleteBST(TreeNode bst, int key) { if(bst == null) { System.out.println("bst null"); } TreeNode p = bst; TreeNode f = null; while(p != null) { if(key == p.data) { break; }else if(key < p.data) { f = p; p = p.lchild; }else { f = p; p = p.rchild; } } if(p.lchild == null) { if(f == null) { return bst = p.rchild; }else if(f.lchild == p){ f.lchild = p.rchild; }else if(f.rchild == p) { f.rchild = p.rchild; } }else { TreeNode s = null; TreeNode q = p; s = p.lchild; while(s.rchild!=null) { q = s; s = s.rchild; } if(q == p) { q.lchild = s.lchild;} else { q.rchild = s.lchild;} p.data = s.data; } return bst; }