数据结构-二叉搜索树（BST）
定义：二叉搜索树是一个节点类的二叉树数据结构，包含以下特点：
-左子树仅包含比根节点小的节点
-右子树仅包含比根节点大的节点
-左右子树同样都是binary search tree
且没有重复节点。
BST的目的： 定义这样的结构主要是为了便于搜索，找到最小值最大值等。如：我们要搜索某个值时，只需要从根节点开始遍历该树，遍历前和根节点比大小，如果比根节点值大，遍历右子树，否则遍历左子树，这样不用所有节点遍历完，最坏的情况下遍历的次数也等同于树的深度，大大提高了查找效率。
BST的常见操作：搜索，插入，删除
首先我们看插入节点操作，首先插入的节点应该都是叶子节点，根据BST的特性，插入的节点应该从root节点开始比较值的大小，如果比root值大，则递归遍历右子树，否则递归遍历左子树，直到新节点作为叶子节点被添加到二叉搜索树里。
class BST {
//root of BST
Node root;
//constructor
BST(){
root = null;
}
//internal class in BST class: node, which includes left and right node and a key.
class Node{
int key;
Node left, right;
public Node(int item){
key = item;
left = right = null;
}
}
//insert method
void insert (int key){
root = insertRec(root,key)
}
Node insertRec(Node root, key){
if(root == null){
root = new Node(key);
return root;
}
if(key <root.key){
root.left = insertRec(root.left, key);
}
else if(key>root.key)
root.right = insertRec(root.right,key);
return root;
}
void inorder(){
inorderRec(root);
}
void inorderRec(Node root){
if(root != null){
inorderRec(root.left);
System.out.println(root.key);
inorderRec(root.right);
}
}
}
test:
public static void main(String[ ] args ){
BST tree = new BST();
tree.inset(50);
tree.inset(30);
//......
tree.inorder();
}
源代码来自：geeksforgeeks.org
BST
网友评论