上数据结构及算法 | Java数据结构——BST二叉搜索树

一、BST相关概念
BST（二叉搜索树）可以实现增加、删除、搜索的时间复杂度都为log2n(以2为底，并非2n) 。关于树的基础概念根据图中数据解释以便理解：
58是根节点root；23是58的左孩子；82是58的右孩子；
23是12和35的父节点；12是23的左孩子；35是23的右孩子；
而23作为父节点，它的左孩子以及孩子和孩子，即23、12、35、18、47这些叫做58的左子树；他的右孩子及孩子的孩子，即82、69、87、74、95这些叫做58的右子树；
而没有孩子节点的节点，自身称作叶子节点，例如：18、47、74、95是叶子节点。
树的层数设为n，n从0开始，58就处于第0层；
那么每层的元素个数是多少呢？
每层元素个数是：2^n个
所以如果知道元素个数，那么树的高度（也就是层数）就是log2n(以2为底的对数值）
二、BST树的增加、删除、查找
（1）首先二叉搜索树有节点，存储当前节点的值和两个孩子节点的域:
class BSTNode>{private T data; // 数据域private BSTNode left; // 左孩子域private BSTNode right; // 右孩子域public BSTNode(T data, BSTNode left, BSTNode right) {this.data = http://www.kingceram.com/post/data;this.left = left;this.right = right;}public T getData() {return data;}public void setData(T data) {this.data = data;}public BSTNode getLeft() {return left;}public void setLeft(BSTNode left) {this.left = left;}public BSTNode getRight() {return right;}public void setRight(BSTNode right) {this.right = right;}}
（2）实现一下BST树，虽然没有操作，但先初始化一下：
class BST>{private BSTNode root; // 指向根节点/*** BST树的初始化*/public BST () {this.root = null;}}
1、二叉搜索树的增加元素：
接下来就是BST增加元素的操作的，定义一个方法：
（1）判断根节点是否为空，如果为空就将待插入值直接插入在根节点的位置；
（2）如果根节点不为空，从根节点开始，如果待插入值大于根节点root值，与根节点右孩子比较；如果待插入值小于根节点root的值，则与根节点左孩子比较，以此类推，找到一个合适的位置；
（3）生成新的节点存放待插入值，把节点的地址（刚找到的合适位置）写入父节点的相应地址域；
非递归实现如下：
public void insert(T data){//1.判断如果root是null,如果root为空，直接生成根节点，让root指向，结束if (root==null){this.root=new BSTNode(data,null,null);return;}//2.如果root不为空，从根节点开始搜索一个合适的位置，放新节点BSTNode cur=this.root;BSTNode parent=null;while (cur!=null){if (cur.getData().compareTo(data)>0){parent=cur;cur=cur.getLeft();}else if (cur.getData().compareTo(data)<0){parent=cur;cur=cur.getRight();}else {return ;}}//3.生成新节点，把节点的地址，写入父节点相应的地址域if (parent.getData().compareTo(data)<0){parent.setRight(new BSTNode(data,null,null));}else {parent.setLeft(new BSTNode(data,null,null));}}
2、二叉搜索树删除元素：
过程（待删除元素记为data）：
（1）如果根节点为空，那么这个树就是空的，说明没有元素，就直接掉；
（2）树不为空，就搜索一遍BST树，找到data的位置；
（3）判断待删除节点是否有两个孩子，如果有的话，找到该节点的前驱位置的元素覆盖该节点，然后再删除掉刚那个前驱元素；
（4）待删除节点如果有一个孩子或者无孩子节点，都看作是有一个孩子节点，没有孩子节点的看作一个孩子为null处理；
注：
1、前驱元素指：父节点的左孩子的右孩子…一直访问右孩子，直到没有右孩子就是父节点的前驱；后继元素指：父节点的右孩子的左孩子…一直左孩子直到没有左孩子的结点称作后继结点。例如58的前驱节点是：47；58的后继结点是：69；

上 数据结构及算法 | Java数据结构——BST二叉搜索树

上数据结构及算法 | Java数据结构——BST二叉搜索树