二叉搜索树
二叉搜索树(BST)又称为二叉查找树、二叉排序树。
1.特征
二叉搜索树首先是一棵二叉树;
对任意节点,如果其左子树不为空,则左子树上任意节点的值均不大于它的根节点的值;
如果其右子树不为空,则右子树上任意节点的值均不大于它的根节点的值;
任意节点的左右子树也分别是二叉搜索树。
2.中序遍历
中序遍历二叉搜索树,得到的结果是有序的数据列。
// 中序遍历二叉搜索树,结果是排好序的数据
public void midOrder(TreeNode node){
if(node == null){
return;
}
midOrder(node.getLeft());
System.out.print(node.getKey() + " ");
midOrder(node.getRight());
}
3.添加节点
二叉搜索树添加的新节点总是成为叶子节点。
// 添加节点构造二叉搜索树
public TreeNode addNode(TreeNode node, int key){
// 如果不存在则创建节点,否则直接返回
if(node == null){
node = new TreeNode(key);
}
if(key < node.getKey()){
node.setLeft(addNode(node.getLeft(), key));
}else if(key > node.getKey()){
node.setRight(addNode(node.getRight(), key));
}else{
return node;
}
return node;
}
4.查找节点
需要遍历二叉搜索树,时间复杂度取决于遍历的深度。
// 查找某个节点,时间复杂度为走过的层数,最坏为O(H)
public TreeNode searchNode(TreeNode node, int key){
// 如果找不到返回null,找到则直接返回
if(node == null || node.getKey() == key){
return node;
}else if(key < node.getKey()){
return searchNode(node.getLeft(), key);
}else{
return searchNode(node.getRight(), key);
}
}
5.范围查找
// 范围查找
public ArrayList<Integer> rangeSearch(int minx, int maxx, ArrayList<Integer> list, TreeNode node){
if(node == null){
return list;
}
//遍历左子树,寻找min的下限处的节点
if(minx < node.getKey()){
rangeSearch(minx, maxx, list, node.getLeft());
}
//开始查找
if(node.getKey() >= minx && node.getKey() <= maxx){
list.add(node.getKey());
}
//遍历右子树,有两种情况:min的下限;不能超过max
if(node.getKey() < minx || node.getKey() < maxx){
rangeSearch(minx, maxx, list, node.getRight());
}
return list;
}