二叉树系列之BST
2018-12-24 本文已影响0人
夜里清风徐来
什么是BST？
1. 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 它的左右子树也分别为二叉排序树。
二叉排序树的数据排序方式为 [左孩子节点 < 根节点 < 右孩子节点]，左子树和父节点值最接近的节点为最靠右的节点，右子树和父节点值最接近的点为最靠左的点。
如下图所示：
BST
BST的java代码实现：包含基础的 插入 删除 查找
public class BinarySearchTree{
private Node root;
private int size;
public BinarySearchTree(Node root){
this.root=root;
size++;
}
public int getSize(){
return this.size;
}
public boolean contains(Name name){
return contains(name,this.root);
//return false;
}
private boolean contains(Name n,Node root){
if(root==null){
return false;
}
int compare=n.compareTo(root.element);
if(compare>0){
if(root.right!=null){
return contains(n,root.right);
}else{
return false;
}
}else if(compare<0){
if(root.left!=null){
return contains(n,root.left);
}else{
return false;
}
}else{
return true;
}
}
public boolean insert(Name n){
boolean flag = insert(n,this.root);
if(flag) size++;
return flag;
}
private boolean insert(Name n,Node root){
if(root==null){
this.root=new Node(n);
return true;
}else if(root.element.compareTo(n)>0){
if(root.left!=null){
return insert(n,root.left);
}else{
root.left=new Node(n);
return true;
}
}else if(root.element.compareTo(n)<0){
if(root.right!=null){
return insert(n,root.right);
}else{
root.right=new Node(n);
return true;
}
}else{
root.frequency++;
return true;
}
}
public boolean remove(Name name){
root = remove(name,this.root);
if(root != null){
size--;
return true;
}
return false;
}
private Node remove(Name name,Node root){
int compare = root.element.compareTo(name);
if(compare == 0){
if(root.frequency>1){
root.frequency--;
}else{
/**根据删除节点的类型，分成以下几种情况
**①如果被删除的节点是叶子节点，直接删除
**②如果被删除的节点含有一个子节点，让指向该节点的指针指向他的儿子节点
**③如果被删除的节点含有两个子节点，找到左字数的最大节点，并替换该节点
**/
if(root.left == null && root.right == null){
root = null;
}else if(root.left !=null && root.right == null){
root = root.left;
}else if(root.left == null && root.right != null){
root = root.right;
}else{
//被删除的节点含有两个子节点
Node newRoot = root.left;
while (newRoot.left != null){
newRoot = newRoot.left;//找到左子树的最大节点
}
root.element = newRoot.element;
root.left = remove(root.element,root.left);
}
}
}else if(compare > 0){
if(root.left != null){
root.left = remove(name,root.left);
}else{
return null;
}
}else{
if(root.right != null){
root.right = remove(name,root.right);
}else{
return null;
}
}
return root;
}
public String toString(){
//中序遍历就可以输出树中节点的顺序
return toString(root);
}
private String toString(Node n){
String result = "";
if(n != null){
if(n.left != null){
result += toString(n.left);
}
result += n.element + " ";
if(n.right != null){
result += toString(n.right);
}
}
return result;
}
}
Node 和 辅助类 Name的相关实现：
class Node{
public Name element;
public Node left;
public Node right;
public int frequency = 1;
public Node(Name n){
this.element=n;
}
}
class Name implements Comparable<Name>{
private String firstName;
private String lastName;
public Name(String firstName,String lastName){
this.firstName=firstName;
this.lastName=lastName;
}
public int compareTo(Name n) {
int result = this.firstName.compareTo(n.firstName);
return result==0?this.lastName.compareTo(n.lastName):result;
}
public String toString(){
return firstName + "-" +lastName;
}
}
BST的 前序 ，中序 ，后续，层序的遍历方式都在之前的二叉树中有对应的实现
详情请看二叉树初探
功能测试：
public static void main(String[] args){
//System.out.println("sunlunqian");
Node root = new Node(new Name("sun","lunqian5"));
BinarySearchTree bst =new BinarySearchTree(root);
bst.insert(new Name("sun","lunqian3"));
bst.insert(new Name("sun","lunqian7"));
bst.insert(new Name("sun","lunqian2"));
bst.insert(new Name("sun","lunqian4"));
bst.insert(new Name("sun","lunqian6"));
bst.insert(new Name("sun","8"));
System.out.println(bst);
bst.remove(new Name("sun","lunqian2"));
System.out.println(bst);
bst.remove(new Name("sun","lunqian7"));
System.out.println(bst);
}
结果输出：
sun-lunqian2 sun-lunqian3 sun-lunqian4 sun-lunqian5 sun-lunqian6 sun-lunqian7 sun-lunqian8
sun-lunqian3 sun-lunqian4 sun-lunqian5 sun-lunqian6 sun-lunqian7 sun-lunqian8
sun-lunqian3 sun-lunqian4 sun-lunqian5 sun-lunqian6 sun-lunqian8
