上 数据结构及算法 | 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;