二分搜索树
前言：
在计算机科学中，二分搜索树（Binary Search Tree）
（有时称为有序或者排序的二叉树）是一种能存储特定数据类型的容器，二叉搜索树 允许快速查找、添加或者删除某一个节点，并且它是动态的集合。
二叉搜索树按照关键字顺序地保存节点，因此查找和其他操作可以使用二叉搜索原理：当在树（或者寻找插入新节点的地方）中查找节点时，它从根节点遍历到叶子节点，与每个节点的关键字进行比较，然后基于比较的结果，决定继续在左子树还是在右子树中进行搜索比较。这样一来，每次比较理论上都活筛选掉一半的元素，这样使得每次查找，插入或者删除一个节点所花费的时间与树的节点个数的对数成（树的高度）正比，比线性表的性能要好很多。
定义
二叉搜索树是以一颗二叉树组织，每个节点就是一个对象，包括key，卫星数据。除此之外还包括一些维护树结构所需要的信息：left、light、parent，分别指向左孩子、右孩子、父节点。其中如果孩子节点或者父节点不存在时，用null表示。根节点时树中唯一一个父节点为null的节点。
一、二叉树性质简介
1.如果节点的左孩子不为空，则左孩子树上所有的节点的值均小于它的根节点的值。
2.如果节点的右孩子不为空，则右孩子树上所有的节点的值均大于它的根节点的值。
3.任意节点的左右孩子也分别为二叉搜索树（只要满足二叉搜索树的基本结构都属于二叉搜索树。）如下图！！！
这里是本人写的一个不支持重复数据的简单的二叉搜索树的源码！
https://gitee.com/ligangyun/data_structure/tree/master/BinarySearchTree
构建二分搜索树
一、初始化二分搜索树对象（本实现树对象不满足包含重复数据）
首先需要明确二分搜索树的结构特点，二分搜索树需要维护一个Node对象
private class Node {
E e;
Node left, right;
/**
* 提供构造方法
*
* @param e 真实元素
*/
Node(E e) {
this.e = e;
left = null;
right = null;
}
}
提供构造函数
/**
* 提供无参构造
*/
public BST() {
root = null;
size = 0;
}
维护整个树的元素大小：
private int size;
提供根节点：
private Node root;
一个简单的二分搜索树基本初始化完成。
二、添加功能
首先在网二分树中添加元素时，需要计算出该元素添加的位置，所以需要使用到递归算法，计算出添加的元素具体的添加位置。
public void add(E e) {
root = NewAdd(root, e);
}
private Node NewAdd(Node node, E e) {
// 判断当前二分树是否为空
if (node == null) {
// 维护size 的大小
size++;
return new Node(e);
}
if (e.compareTo(node.e) < 0) {
node.left = NewAdd(node.left, e);
} else if (e.compareTo(node.e) > 0) {
node.right = NewAdd(node.right, e);
}
return node;
}
这里的元素对比是在二分树泛型中继承java comparable 类 实现的
其他一些列操作 包含 删除 查找等操作都是居于递归实现的！本人提供的源码均详细实现。
二分搜索树的深度遍历
说明：
二分搜索树的遍历分为三大类：先序遍历（preorder tree walk）、中序遍历（inorder tree walk）、后序遍历（postorder tree walk）
使用递归的方式访问节点每个节点都会被访问三次
1.首先访问当前节点。
2.再访问该节点的左孩子，再会回到该节点，访问该节点的右孩子
3.最终右孩子访问结束后，还是返回到该节点，标志着该节点即下面的所有子节点都访问完毕！
前序递归遍历
所以上述图中遍历流程如下
1.第一次当问root节点时记录28；
2.然后访问root 节点的左孩子节点记录16；
3.再访问16节点的左孩子节点，记录13；
4.然后访问13的左孩子节点，为空，回到13节点，再访问13节点的右孩子节点也为空，有一次回到13节点；
5.此时访问回到16节点，此时访问16节点的右孩子节点，来到22节点，记录22；
6.22 节点左右孩子节点都为空，所以回到16节点（至此16节点的所有右孩子节点遍历完毕。）
7.来到28根节点（以此类推进行根节点的右孩子节点的遍历）
所以上述二分搜索树中遍历的结果为：28、16、13、22、30、29、42
/**
* 二分搜索树 递归前序遍历
*/
public void preOrder() {
preOrder(root);
}
private void preOrder(Node node) {
if (node == null) {
return;
}
System.out.println(node.e);
// 递归遍历 左右孩子节点,这里一定要注意左孩子在前面
preOrder(node.left);
preOrder(node.right);
}
中序递归遍历
原理与前序遍历基本相同，只是在节点第二次出现时，获取节点信息。
/**
* 二分搜索树 递归中序遍历
*/
public void inOrder() {
inOrder(root);
}
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);
}
private void postOrder(Node node) {
if (node == null) {
return;
}
postOrder(node.left);
postOrder(node.right);
System.out.println(node.e);
}
二分搜索树非递归遍历
使用栈线性结构实现二分搜索树前序遍历
简单的流程动态图：
/**
* 使用栈 实现前序遍历
*/
public void preOrderByStack() {
preOrderByStack(root);
}
private void preOrderByStack(Node node) {
if (node == null) {
return;
}
Stack<Node> stack = new Stack<>();
stack.push(node);
// 有序栈结构先进后出的特性，需要向将右孩子先于左孩子压入栈底
while (!stack.isEmpty()) {
Node pop = stack.pop();
System.out.println(pop.e);
if (pop.right != null) {
stack.push(pop.right);
}
if (pop.left != null) {
stack.push(pop.left);
}
}
}
使用栈线性结构实现二分搜索树中序遍历
中序遍历相较于前序遍历会比较的复杂（前序遍历应用的比较广泛，这里视时间的充裕程度选择阅读）
首先分析
在使用栈结果实现中序遍历的时候，需要重点考虑节点是否存在左孩子节点。当节点有左孩子节点时，需要将该节点优先入栈，如果该节点没有左孩子节点，此时应该访问该节点。再考虑有叶子节点。
操作步骤
步骤一：如果节点有左叶子节点，将该节点入栈，如果节点没有左叶子节点，访问当前节点。
步骤二：如果节点有右叶子节点，重复步骤一，如果节点没有有叶子节点（该节点下所有的子节点访问完毕）回退，让栈顶元素出栈，并且访问栈顶元素的右叶子元素，然后重复步骤一。
步骤二：当栈为空时，说明遍历结束
代码如下：
/**
* 栈 实现 中序遍历
*/
public ArrayList<E> inOrderByStack() {
return inOrderByStack(root);
}
private ArrayList<E> inOrderByStack(Node node) {
ArrayList<E> result = new ArrayList<>();
if (node == null) {
return result;
}
Stack<Node> nodeStack = new Stack<>();
/**
* 分析：
* 步骤1：节点如果有左叶子节点，该节点入栈，
* 如果该节点没有左叶子节点，访问该节点
* 步骤2：如果节点有右叶子节点，重复步骤1
* 如果节点没有右叶子节点（说明访问完毕）回退，让栈顶元素出栈，并且访问栈顶元素的右叶子树，重复步骤1
* 步骤3：当栈为空时，遍历结束
*/
Node cur = node;
// 判断 当前节点 是否为空，并且 栈是否遍历完结
while (cur != null || !nodeStack.empty()) {
// 将当前节点下所有的左叶子节点压入栈顶
while (cur != null) {
nodeStack.push(cur);
cur = cur.left;// 定义当前变量
}
// 获取栈顶元素
cur = nodeStack.peek();
result.add(cur.e);
// 弹出栈顶
nodeStack.pop();
cur = cur.right;
}
return result;
}
使用栈线性结构实现二分搜索树后序遍历
/**
* 栈 实现后序遍历
*
* @return
*/
public ArrayList<E> postOrderByStack() {
return postOrderByStack(root);
}
private ArrayList<E> postOrderByStack(Node node) {
ArrayList<E> result = new ArrayList<>();
Stack<Node> nodeStack = new Stack<>();
Node cur = node;
while (cur != null || !nodeStack.empty()) {
/**
* 分析：
* 后序遍历 在中序遍历的基础上，需要注意的是：节点的所有右孩子节点访问完毕后，该节点才可以出栈
*/
// 先遍历所有的左孩子节点
while (cur != null) {
nodeStack.push(cur);
cur = cur.left;
}
cur = nodeStack.peek();
if (cur.right == null) {
// 当前节点 为左节点的最后一个节点，添加到结果集中，并且将当前cur 设置为栈顶值。
result.add(cur.e);
// 该节点 出栈
nodeStack.pop();
//判断此时的栈顶的右孩子是否与当前的cur 相等，相等 则说明 该栈顶元素下面的所有元素遍历完毕，需要出栈
while (!nodeStack.empty() && nodeStack.peek().right.equals(cur)) {
cur = nodeStack.peek();
result.add(nodeStack.pop().e);
}
//将 此时栈顶的右孩子 赋值给cur
cur = nodeStack.empty() ? null : nodeStack.peek().right;
} else {
// 该节点没有左叶子树，但是有右叶子树,并将右叶子节点复制给cur
cur = cur.right;
}
}
return result;
}
以上所有遍历都可以划分为 二分搜索树的深度优先遍历：对每一个可能的分支路径深入到不能再深入为止
二分搜索树的广度遍历（层序遍历）
广度遍历：从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。广度优先遍历的非递归的通用做法是采用队列。
利用队列实现层序遍历
/**
* 广度优先遍历（层序遍历） 使用队列
*
* @return
*/
public ArrayList<E> sequenceOrder() {
return sequenceOrder(root);
}
private ArrayList<E> sequenceOrder(Node node) {
ArrayList<E> result = new ArrayList<>();
if (node == null)
return result;
Queue<Node> nodeQueue = new LinkedList<>();
nodeQueue.add(node);
while (!nodeQueue.isEmpty()) {
Node cur = nodeQueue.remove();
result.add(cur.e);
if (cur.left != null)
nodeQueue.add(cur.left);
if (cur.right != null) {
nodeQueue.add(cur.right);
}
}
return result;
}
此文经作为作者学习记录。如有不对的地方还望指出和谅解。谢谢
祝各位工作顺利！
