一 为什么要研究树结构。
树结构是计算机世界中非常高效的一种数据结构，也是应用非常广泛的数据结构；
树结构图示.png
2⃣️ 树结构的应用场景。
计算机中文件目录结构图示.png
公司组织架构图示.png
以上这些应用场景都是树型结构的使用场景，树结构的特点就是层次清晰，高效。
3⃣️ 树结构常用的类型都有什么？
二分搜索树 平衡二叉树 线段树 Trie等都是很常用的树型数据结构。
二 二分搜索树基础
二分搜索树是树型结构中的一种，要了解二分搜索树需要先说一下二叉树结构；
二叉树图示.png
2⃣️ 二叉树的组成图示。
二叉树的组成图示.png
根节点：二叉树具有一个唯一的根节点；
左右节点：二叉树每个节点最多有两个节点(左节点和右节点);
父节点：二叉树每个节点最多有一个父节点；
3⃣️ 二叉树具有天然递归结构。
二叉树具有天然递归结构.png
为什么说二叉树具有天然的递归结构呢？因为对于一个父节点来说，下边的每个节点(左节点和右节点)又是一个新的二叉树；
4⃣️ 二叉树不一定都是满的。
满二叉树图示.png
非满二叉树图示1.png
非满二叉树图示2.png
非满二叉树图示3.png
最特殊的二叉树.png
5⃣️ 二分搜索树
在介绍完二叉树以后我们来看一下二分搜索树；
二分搜索树图示.png
二分搜索树概念图示.png
二分搜索树是二叉树的一种，二分搜索树的特点是每个节点的值都大于左子树的所有节点，每个节点的值都小于右子树中所有节点的值，然后每个父节点下边的子树也是一个二分搜索树，同时二分搜索树每个节点的值必须满足可比较性；
二分搜索树既然是二叉树的一种，也就意味着二分搜索树也不一定都是满的，更多的时候应该是不满的情况；
不规则的二分搜索树.png
三 代码实现一个二分搜索树
package com.mufeng.binarySearchTree;
/**
* Created by wb-yxk397023 on 2018/6/30.
*/
public class BST<E extends Comparable<E>> {
private class Node{
public E e;
public Node left, right;
public Node(E e){
this.e = e;
this.left = null;
this.right = null;
}
}
private Node root;
private int size;
public BST(){
root = null;
size = 0;
}
public int getSize(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
}
四 向二分搜索树中添加元素
1⃣️ 添加新元素图示
一个空的树
新添加的元素将会成为根
继续进行添加操作
通过对比找到位置
添加了多个元素的树
继续添加新元素
通过对比找到具体的位置
继续添加元素
通过对比找到位置
补充：我们的添加操作是不包含重复操作的；但是如果想要包含重复元素的只需要改变一个对比的条件就可以了，比如左子树可以放置小于或者等于根节点的元素或者右子树中放置大于或者等于根的元素即可；
2⃣️ 代码实现
/**
* 向二分搜索树中添加新的元素e
* @param e
*/
public void add(E e){
if (root == null){
root = new Node(e);
size++;
}else {
add(root, e);
}
}
/**
* 向以node为根的二分搜索树中插入元素e，递归算法
* @param node
* @param e
*/
public void add(Node node, E e){
// 递归的终止条件
if (e.equals(node.e)){
return;
}else if (e.compareTo(node.e) < 0 && node.left == null){
node.left = new Node(e);
size++;
return;
}else if (e.compareTo(node.e) > 0 && node.right == null){
node.right = new Node(e);
size++;
return;
}
// 递归调用
if (e.compareTo(node.e) < 0){
add(node.left, e);
}
add(node.right, e);
}
由于二分搜索树的结构非常适合使用递归的操作，所以我们的添加操作直接使用递归的方式进行实现，但是上边的代码递归的终止条件显得有些臃肿，所以我们需要对添加操作的代码逻辑进行优化；
/**
* 向二分搜索树中添加新的元素e
* @param e
*/
public void add(E e){
root = add(root, e);
}
/**
* 向以node为根的二分搜索树中插入元素e，递归算法
* 返回插入新节点后二分搜索树的根
* @param node
* @param e
* @return
*/
public Node add(Node node, E e){
// 递归的终止条件
if (node == null){
size++;
return new Node(e);
}
// 递归调用
if (e.compareTo(node.e) < 0){
node.left = add(node.left, e);
}else if (e.compareTo(node.e) > 0){
node.right = add(node.right, e);
}
return node;
}
五 二分搜索树的查询操作
如果大家理解了二分搜索树的添加操作，那么就可以很容易的理解二分搜索树的查询操作；
/**
* 二分搜索树中是否包含元素e
* @param e
* @return
*/
public boolean contains(E e){
return contains(root, e);
}
/**
* 查询以node为节点的二分搜索树中是否包含元素e
* @param node
* @param e
* @return
*/
private boolean contains(Node node, E e){
if (node == null){
return false;
}else if (e.compareTo(node.e) == 0){
return true;
}else if (e.compareTo(node.e) < 0){
return contains(node.left, e);
}
return contains(node.right, e);
}
六 二分搜索树的遍历
1⃣️ 前序遍历
二叉树图示
二分搜索树模型图
/**
* 二叉树的前序遍历
*/
public void preOrder(){
preOrder(root);
}
/**
* 前序遍历以node为根的二分搜索树，递归算法
* @param node
*/
private void preOrder(Node node){
if (node == null){
return;
}
System.out.println(node.e);
preOrder(node.left);
preOrder(node.right);
}
重写toString
/**
* 以前序遍历的方式重写toString
* @return
*/
@Override
public String toString(){
StringBuilder res = new StringBuilder();
generateBSTString(root, 0, res);
return res.toString();
}
/**
* 生成以node为根节点，深度为depth的描述二叉树的字符串
* @param node
* @param depth
* @param res
*/
private void generateBSTString(Node node, int depth, StringBuilder res){
if (node == null){
res.append(generateDepthString(depth) + "null\n");
return;
}
res.append(generateDepthString(depth) + node.e + "\n");
generateBSTString(node.left, depth + 1, res);
generateBSTString(node.right, depth + 1, res);
}
private String generateDepthString(int depth){
StringBuilder res = new StringBuilder();
for (int i = 0; i < depth; i++){
res.append("--");
}
return res.toString();
}
2⃣️ 中序遍历
中序遍历图示
/**
* 二分搜索树的中序遍历
*/
public void inOrder(){
inOrder(root);
}
/**
* 中序遍历以node为根的二分搜索树，递归算法
* @param node
*/
private void inOrder(Node node){
if (node == null){
return;
}
inOrder(node.left);
System.out.println(node.e);
inOrder(node.right);
}
3⃣️ 后序遍历
后序遍历的原理在遍历当前节点之前先遍历左右子树，然后在遍历当前节，得到的结果就是后序遍历的结果；
后续遍历的适用场景：比如释放二分搜索树的内存这样的操作需要用到后序遍历，因为要释放内存肯定需要先释放左右子树在释放当前节点；
/**
* 二分搜索树的后序遍历
*/
public void postOrder(){
postOrder(root);
}
/**
* 后续遍历以node为根的二分搜索树，递归算法
* @param node
*/
private void postOrder(Node node){
if (node == null){
return;
}
postOrder(node.left);
postOrder(node.right);
System.out.println(node.e);
}
4⃣️ 深度优先遍历
非递归实现二分搜索树的前序遍历
// 二分搜索树的非递归前序遍历
public void preOrderNR(){
if(root == null)
return;
Stack<Node> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
Node cur = stack.pop();
System.out.println(cur.e);
if(cur.right != null)
stack.push(cur.right);
if(cur.left != null)
stack.push(cur.left);
}
}
在二分搜索树这样的结构中，使用递归可以很简单的实现功能，但是非递归的话实现起来就会有一点困难，当使用非递归的方式实现前序遍历的话，需要借助栈来实现，这样的遍历方式也被称为深度优先遍历；
5⃣️ 广度优先遍历
// 二分搜索树的层序遍历
public void levelOrder(){
if(root == null)
return;
Queue<Node> q = new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
Node cur = q.remove();
System.out.println(cur.e);
if(cur.left != null)
q.add(cur.left);
if(cur.right != null)
q.add(cur.right);
}
}
二分搜索树的层序遍历也叫做广度优先遍历；深度优先遍历以及广度优先遍历更多的是应用与算法中的，所以这里不做深入的说明；
七 二分搜索树中的删除操作
1⃣️ 删除二分搜索树中的最大值和最小值
一个完整的二分搜索树
以此图为例，如果要删除这个二分搜索树的最小以及最大节点，我们需要从根节点开始执行查询操作，如果要删除最小值的话，就需要一直向左进行查询，直到找到最小值即可，删除最大值也是一样的操作；
删除后的二分搜索树
此处需要注意的是，如果我们在进行删除此树的最小值的话，则16将会被删除，22将作为此树根节点28的左子树的根节点。
需要注意的是，删除操作的前提是需要先找到待删除的树的最小值与最大值，所以我们需要先实现这个逻辑才能进行删除的操作；
/**
* 寻找二分搜索树的最小元素
* @return
*/
public E minimum(){
if(size == 0)
throw new IllegalArgumentException("BST is empty");
Node miniNode = minimum(root);
return miniNode.e;
}
/**
* 返回以node为根的二分搜索树的最小值所在的节点
* @param node
* @return
*/
private Node minimum(Node node){
if (node.left == null){
return node;
}
return minimum(node.left);
}
/**
* 寻找二分搜索树的最大元素
* @return
*/
public E maxmum(){
if (size == 0){
throw new IllegalArgumentException("BST is empty");
}
Node maxNode = maxmum(root);
return maxNode.e;
}
/**
* 返回以node为根的二分搜索树的最大值所在的节点
* @param node
* @return
*/
private Node maxmum(Node node){
if (node.right == null){
return node;
}
return maxmum(node.right);
}
待删除最小节点的二分搜索树
删除最小值后的二分搜索树
删除最小值后的二分搜索树
删除22节点后的二分搜索树
对于删除二分搜索树中的最大节点也是一样的操作，这里就不再进行图示了。
/**
* 从二分搜索树中删除最小值所在节点, 返回最小值
* @return
*/
public E removemin(){
E ret = minimum();
root = removemin(root);
return ret;
}
/**
* 删除掉以node为根的二分搜索树中的最小节点
* 返回删除节点后新的二分搜索树的根
* @param node
* @return
*/
private Node removemin(Node node){
if (node.left == null){
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
node.left = removemin(node.left);
return node;
}
/**
* 从二分搜索树中删除最大值所在节点，返回最大值
* @return
*/
public E removeMax(){
E ret = maxmum();
root = removeMax(root);
return ret;
}
/**
* 删除掉以node为根的二分搜索树中的最大节点
* 返回删除节点后新的二分搜索树的根
* @param node
* @return
*/
private Node removeMax(Node node){
if (node.right == null){
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
node.left = removeMax(node.right);
return node;
}
2⃣️ 删除二分搜索树中的任意元素
删除二分搜索树中任意元素分以下几种情况：
删除只有左子树的元素
删除只有右子树的元素
删除有左右子树的元素
第一种情况和第二种情况都比较简单，和我们删除最小值和最大值的逻辑基本一样，但是第三种情况则相对复杂一些，这里我们采取一种后继的做法，请看图示
删除任意元素1
删除任意元素2
删除任意元素3
删除任意元素4
删除任意元素5
删除任意元素6
/**
* 从二分搜索树中删除元素为e的节点
* @param e
*/
public void remove(E e){
root = remove(root, e);
}
/**
* 删除掉以node为根的二分搜索树中值为e的节点, 递归算法
* 返回删除节点后新的二分搜索树的根
* @param node
* @param e
* @return
*/
private Node remove(Node node, E e){
if( node == null )
return null;
if( e.compareTo(node.e) < 0 ){
node.left = remove(node.left , e);
return node;
}
else if(e.compareTo(node.e) > 0 ){
node.right = remove(node.right, e);
return node;
}
else{ // e.compareTo(node.e) == 0
// 待删除节点左子树为空的情况
if(node.left == null){
removeMin(node);
}
// 待删除节点右子树为空的情况
if(node.right == null){
removeMax(node);
}
// 待删除节点左右子树均不为空的情况
// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
// 用这个节点顶替待删除节点的位置
Node successor = minimum(node.right);
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
return successor;
}
}
八 二分搜索树相关代码
package com.mufeng.binarySearchTree;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/**
* Created by wb-yxk397023 on 2018/6/30.
*/
public class BST<E extends Comparable<E>> {
private class Node{
public E e;
public Node left, right;
public Node(E e){
this.e = e;
this.left = null;
this.right = null;
}
}
private Node root;
private int size;
public BST(){
root = null;
size = 0;
}
public int size(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
/**
* 向二分搜索树中添加新的元素e
* @param e
*/
public void add(E e){
root = add(root, e);
}
/**
* 向以node为根的二分搜索树中插入元素e，递归算法
* 返回插入新节点后二分搜索树的根
* @param node
* @param e
* @return
*/
public Node add(Node node, E e){
// 递归的终止条件
if (node == null){
size++;
return new Node(e);
}
// 递归调用
if (e.compareTo(node.e) < 0){
node.left = add(node.left, e);
}else if (e.compareTo(node.e) > 0){
node.right = add(node.right, e);
}
return node;
}
/**
* 二分搜索树中是否包含元素e
* @param e
* @return
*/
public boolean contains(E e){
return contains(root, e);
}
/**
* 查询以node为节点的二分搜索树中是否包含元素e
* @param node
* @param e
* @return
*/
private boolean contains(Node node, E e){
if (node == null){
return false;
}else if (e.compareTo(node.e) == 0){
return true;
}else if (e.compareTo(node.e) < 0){
return contains(node.left, e);
}
return contains(node.right, e);
}
/**
* 二分搜索树的前序遍历
*/
public void preOrder(){
preOrder(root);
}
/**
* 前序遍历以node为根的二分搜索树，递归算法
* @param node
*/
private void preOrder(Node node){
if (node == null){
return;
}
System.out.println(node.e);
preOrder(node.left);
preOrder(node.right);
}
/**
* 二分搜索树的非递归前序遍历
*/
public void preOrderNR(){
Stack<Node> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
Node cur = stack.pop();
System.out.println(cur.e);
if(cur.right != null)
stack.push(cur.right);
if(cur.left != null)
stack.push(cur.left);
}
}
/**
* 二分搜索树的中序遍历
*/
public void inOrder(){
inOrder(root);
}
/**
* 中序遍历以node为根的二分搜索树，递归算法
* @param node
*/
private void inOrder(Node node){
if (node == null){
return;
}
inOrder(node.left);
System.out.println(node.e);
inOrder(node.right);
}
/**
* 二分搜索树的后序遍历
*/
public void postOrder(){
postOrder(root);
}
/**
* 寻找二分搜索树的最小元素
* @return
*/
public E minimum(){
if(size == 0)
throw new IllegalArgumentException("BST is empty");
Node miniNode = minimum(root);
return miniNode.e;
}
/**
* 返回以node为根的二分搜索树的最小值所在的节点
* @param node
* @return
*/
private Node minimum(Node node){
if (node.left == null){
return node;
}
return minimum(node.left);
}
/**
* 寻找二分搜索树的最大元素
* @return
*/
public E maxmum(){
if (size == 0){
throw new IllegalArgumentException("BST is empty");
}
Node maxNode = maxmum(root);
return maxNode.e;
}
/**
* 返回以node为根的二分搜索树的最大值所在的节点
* @param node
* @return
*/
private Node maxmum(Node node){
if (node.right == null){
return node;
}
return maxmum(node.right);
}
/**
* 从二分搜索树中删除最小值所在节点, 返回最小值
* @return
*/
public E removemin(){
E ret = minimum();
root = removeMin(root);
return ret;
}
/**
* 删除掉以node为根的二分搜索树中的最小节点
* 返回删除节点后新的二分搜索树的根
* @param node
* @return
*/
private Node removeMin(Node node){
if (node.left == null){
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
/**
* 从二分搜索树中删除最大值所在节点，返回最大值
* @return
*/
public E removeMax(){
E ret = maxmum();
root = removeMax(root);
return ret;
}
/**
* 删除掉以node为根的二分搜索树中的最大节点
* 返回删除节点后新的二分搜索树的根
* @param node
* @return
*/
private Node removeMax(Node node){
if (node.right == null){
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
node.left = removeMax(node.right);
return node;
}
/**
* 后续遍历以node为根的二分搜索树，递归算法
* @param node
*/
private void postOrder(Node node){
if (node == null){
return;
}
postOrder(node.left);
postOrder(node.right);
System.out.println(node.e);
}
/**
* 二分搜索树的层序遍历
*/
public void levelOrder(){
Queue<Node> q = new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
Node cur = q.remove();
System.out.println(cur.e);
if(cur.left != null)
q.add(cur.left);
if(cur.right != null)
q.add(cur.right);
}
}
/**
* 从二分搜索树中删除元素为e的节点
* @param e
*/
public void remove(E e){
root = remove(root, e);
}
/**
* 删除掉以node为根的二分搜索树中值为e的节点, 递归算法
* 返回删除节点后新的二分搜索树的根
* @param node
* @param e
* @return
*/
private Node remove(Node node, E e){
if( node == null )
return null;
if( e.compareTo(node.e) < 0 ){
node.left = remove(node.left , e);
return node;
}
else if(e.compareTo(node.e) > 0 ){
node.right = remove(node.right, e);
return node;
}
else{ // e.compareTo(node.e) == 0
// 待删除节点左子树为空的情况
if(node.left == null){
removeMin(node);
}
// 待删除节点右子树为空的情况
if(node.right == null){
removeMax(node);
}
// 待删除节点左右子树均不为空的情况
// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
// 用这个节点顶替待删除节点的位置
Node successor = minimum(node.right);
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
return successor;
}
}
/**
* 以前序遍历的方式重写toString
* @return
*/
@Override
public String toString(){
StringBuilder res = new StringBuilder();
generateBSTString(root, 0, res);
return res.toString();
}
/**
* 生成以node为根节点，深度为depth的描述二叉树的字符串
* @param node
* @param depth
* @param res
*/
private void generateBSTString(Node node, int depth, StringBuilder res){
if (node == null){
res.append(generateDepthString(depth) + "null\n");
return;
}
res.append(generateDepthString(depth) + node.e + "\n");
generateBSTString(node.left, depth + 1, res);
generateBSTString(node.right, depth + 1, res);
}
private String generateDepthString(int depth){
StringBuilder res = new StringBuilder();
for (int i = 0; i < depth; i++){
res.append("--");
}
return res.toString();
}
}
