数据结构及算法 | 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）首先二叉搜索树有节点，BSTNode存储当前节点的值和两个孩子节点的域:

class BSTNode>{private T data; // 数据域private BSTNode left; // 左孩子域private BSTNode right; // 右孩子域public BSTNode(T data, BSTNode left, BSTNode right) {this.data = 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增加元素的操作的，定义一个insert方法：
（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）如果根节点为空，那么这个树就是空的，说明没有元素，就直接return掉；
（2）树不为空，就搜索一遍BST树，找到data的位置；
（3）判断待删除节点是否有两个孩子，如果有的话，找到该节点的前驱位置的元素覆盖该节点，然后再删除掉刚那个前驱元素；
（4）待删除节点如果有一个孩子或者无孩子节点，都看作是有一个孩子节点，没有孩子节点的看作一个孩子为null处理；
注：
1、前驱元素指：父节点的左孩子的右孩子…一直访问右孩子，直到没有右孩子就是父节点的前驱；后继元素指：父节点的右孩子的左孩子…一直左孩子直到没有左孩子的结点称作后继结点。例如58的前驱节点是：47；58的后继结点是：69；
2、删除元素的三种情况：该节点没有孩子节点、有一个孩子节点和有两个孩子节点，因为假如待删除节点还有孩子，我们不能把该节点及该节点的所有孩子一起删除了，而是只能删除这个节点的这一个元素，所以我们需要区分不同情况来不同的处理。
非递归实现如下：

public void non_remove(T data){if(this.root == null){return;}// 1. 先搜索BST树，找到待删除的节点BSTNode node = this.root;BSTNode parent = null;//记录当前父节点while(node != data){if(node.getData().compareTo(data) > 0){parent = node;node = node.getLeft();}else if(node.getData().compareTo(data) < 0){parent = node;node = node.getRight();}else{break;}}if(node == null){//表示BST树中没有值为data的节点return;}// 2. 判断删除节点是否有两个孩子，如果有，用前驱的值代替，直接删除前驱if(node.getLeft() != null && node.getRight() != null){//两个孩子节点BSTNode old = node;parent = node;node = parent.getLeft();//node记录父节点的左孩子节点while(node.getRight() != null) {//node的右孩子节点不为空parent = node;node = node.getRight();//继续找右孩子节点}//将找到的前驱结点放在父节点的位置，删除前驱结点old.setData(node.getData());}// 3. 删除有一个孩子的节点，或者没有孩子的节点（看作有一个孩子，孩子是null）BSTNode child = node.getLeft();if(child == null){//左边为空时，child就指向右孩子嘛child = node.getRight();}if(parent == null){this.root = child;//当前父节点为空，其root节点直接指向他的孩子}
}

3、二叉搜索树查找元素
其实查找也就是相当于遍历了，而遍历在前面的增加删除操作中均有涉及；
设待查找元素为data，找到返回true，找不到返回false，查找过程如下：
（1）从根节点开始比较，根节点为空，找不到元素返回false；
（2）比根节点小的话，与左孩子进行比较（小于父节点就向左比）；
（3）比根节点大的话，与右孩子进行比较（大于父节点就向右比）；
（4）如果与根节点大小相同的话就是找到这个元素了吖，返回true嘛！
非递归实现如下：

public boolean non_query(T data){BSTNode node = this.root;while(node != data) {if (node.getData().compareTo(data) > 0) {node = node.getLeft();} else if (node.getData().compareTo(data) < 0) {node = node.getRight();} else {return true; //找到返回true}}return false;//找不到data值，返回false
}

三、四种遍历方式

4、前序遍历
前序遍历就是先访问父节点，再访问左孩子、再访问右孩子；
如上图中的数值前序遍历的输出顺序就是：58 23 12 18 35 47 82 69 74 87 95
递归实现：

/*
* 前序遍历BST树的API接口
*/
public void preOrder(){System.out.print("前序遍历：");preOrder(this.root);System.out.println();
}
/*** 前序遍历BST树的递归操作 VLR*/
private void preOrder(BSTNode root) {if(root != null){System.out.print(root.getData() + " ");preOrder(root.getLeft());preOrder(root.getRight());}
}

5、中序遍历
中序遍历就是先访问左孩子，再访问父节点，再访问右孩子；
上图中的数值中序遍历的输出顺序就是：12 18 23 35 47 58 69 74 82 87 95
可以发现，中序遍历之后数是按照从小到大的顺序排列的。
递归实现：

//中序遍历
public void inOrder(){System.out.print("中序遍历：");inOrder(this.root);System.out.println();
}
public void inOrder(BSTNode root){if(root != null){inOrder(root.getLeft());System.out.print(root.getData() + "  ");inOrder(root.getRight());}
}

6、后序遍历
后序遍历就是先访问左孩子，再访问右孩子，再访问父节点；
上图中的数值经过后序遍历输出是：18 12 47 35 23 74 69 95 87 82 58
递归实现：

//后序遍历
public void postOrder(){System.out.print("后序遍历：");inOrder(this.root);System.out.println();
}
public void postOrder(BSTNode root){postOrder(root.getLeft());postOrder(root.getRight());System.out.print(root.getData() + "  ");
}

7、层序遍历
层序遍历就是按照从上到下，从左到右一层一层的将元素输出；
结合图中数据输出顺序也就是：58 23 82 12 35 69 87 18 47 74 95

//层序遍历BST树
public void levelOrder(){//API接口System.out.print("层序遍历：");int hight = level();for(int i = 0;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！