数据结构-二叉搜索树

数据结构-二叉搜索树（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