二分搜索树的特点
二分搜索树首先是一个二叉树，其次其必须满足的条件是：每个节点的键值必须大于其左子节点，每个节点的键值必须小于其右子节点，这样以左右孩子为根的子树仍为二分搜索树，需要注意的是，二分搜索树不一定是一颗完全二叉树。
深度优先遍历
深度优先遍历的基本思想：对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。深度优先遍历的非递归的通用做法是采用栈。要特别注意的是，二分搜索树的深度优先遍历比较特殊，可以细分为前序遍历、中序遍历、后序遍历。
前序遍历：先访问当前节点，再依次递归访问左右子树 ，访问到前面节点才继续 中序遍历：先递归访问左子树，再访问自身，再递归访问右子树，访问到中间节点才继续 后序遍历：先递归访问左右子树，再访问自身节点，访问到后面节点才继续 例如，对于下面的这个二分搜索树，其前序遍历结果是：28 16 13 22 30 29 42，其中序遍历结果是：13 16 22 28 29 30 42，其后序遍历结果是：13 22 16 29 42 30 28。
广度优先遍历
深度优先遍历的基本思想：从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。广度优先遍历的非递归的通用做法是采用队列。
例如，对于上面的这个二分搜索树，其层序遍历（广度优先遍历）结果是：28 16 30 13 22 29 42。
Java代码实现深度优先遍历和广度优先遍历 下面采用Java语言来构建这个二分搜索树，并且实现前序遍历、中序遍历、后序遍历三种不同方式的深度优先遍历和广度优先遍历（层序遍历）。
package com.allSorts;
import java.util.LinkedList;
import java.util.Queue;
/**
* Created by Demrystv.
*/
public class BSTTraverseTest {
public static void main(String[] args) {
BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
tree.insertNode(28);
tree.insertNode(16);
tree.insertNode(13);
tree.insertNode(22);
tree.insertNode(30);
tree.insertNode(29);
tree.insertNode(42);
System.out.print("前序遍历（递归）：");
tree.preOrderTraverse(tree.getRoot());
System.out.println();
System.out.print("中序遍历（递归）：");
tree.inOrderTraverse(tree.getRoot());
System.out.println();
System.out.print("后序遍历（递归）：");
tree.postOrderTraverse(tree.getRoot());
System.out.println();
System.out.print("前序遍历（非递归）：");
tree.preOrderTraverseNoRecursion(tree.getRoot());
System.out.println();
System.out.print("中序遍历（非递归）：");
tree.inOrderTraverseNoRecursion(tree.getRoot());
System.out.println();
System.out.print("后序遍历（非递归）：");
tree.postOrderTraverseNoRecursion(tree.getRoot());
System.out.println();
System.out.print("广度优先遍历：");
tree.breadthFirstTraverse(tree.getRoot());
}
/**
* 结点
*/
public static class Node<E extends Comparable<E>> {
E value;
Node<E> left;
Node<E> right;
Node(E value) {
this.value = value;
left = null;
right = null;
}
}
/**
* 使用一个前序遍历构建一棵二分搜索树
*/
public static class BinarySearchTree<E extends Comparable<E>> {
private Node<E> root;
BinarySearchTree() {
root = null;
}
public void insertNode(E value) {
if (root == null) {
root = new Node<E>(value);
return;
}
Node<E> currentNode = root;
while (true) {
if (value.compareTo(currentNode.value) > 0) {
if (currentNode.right == null) {
currentNode.right = new Node<E>(value);
break;
}
currentNode = currentNode.right;
} else {
if (currentNode.left == null) {
currentNode.left = new Node<E>(value);
break;
}
currentNode = currentNode.left;
}
}
}
public Node<E> getRoot(){
return root;
}
/**
* 前序遍历二分搜索树（递归）
* @param node
*/
public void preOrderTraverse(Node<E> node) {
System.out.print(node.value + " ");
if (node.left != null)
preOrderTraverse(node.left);
if (node.right != null)
preOrderTraverse(node.right);
}
/**
* 中序遍历二分搜索树（递归）
* @param node
*/
public void inOrderTraverse(Node<E> node) {
if (node.left != null)
inOrderTraverse(node.left);
System.out.print(node.value + " ");
if (node.right != null)
inOrderTraverse(node.right);
}
/**
* 后序遍历二分搜索树（递归）
* @param node
*/
public void postOrderTraverse(Node<E> node) {
if (node.left != null)
postOrderTraverse(node.left);
if (node.right != null)
postOrderTraverse(node.right);
System.out.print(node.value + " ");
}
/**
* 前序遍历二分搜索树（非递归），用的是栈
* @param root
*/
public void preOrderTraverseNoRecursion(Node<E> root) {
LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
Node<E> currentNode = null;
stack.push(root);
while (!stack.isEmpty()) {
currentNode = stack.pop();
System.out.print(currentNode.value + " ");
if (currentNode.right != null)
stack.push(currentNode.right);
if (currentNode.left != null)
stack.push(currentNode.left);
}
}
/**
* 中序遍历二分搜索树（非递归），用的是栈
* @param root
*/
public void inOrderTraverseNoRecursion(Node<E> root) {
LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
Node<E> currentNode = root;
while (currentNode != null || !stack.isEmpty()) {
// 一直循环到二叉排序树最左端的叶子结点（currentNode是null）
while (currentNode != null) {
stack.push(currentNode);
currentNode = currentNode.left;
}
currentNode = stack.pop();
System.out.print(currentNode.value + " ");
currentNode = currentNode.right;
}
}
/**
* 后序遍历二分搜索树（非递归），用的是栈
* @param root
*/
public void postOrderTraverseNoRecursion(Node<E> root) {
LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
Node<E> currentNode = root;
Node<E> rightNode = null;
while (currentNode != null || !stack.isEmpty()) {
// 一直循环到二叉排序树最左端的叶子结点（currentNode是null）
while (currentNode != null) {
stack.push(currentNode);
currentNode = currentNode.left;
}
currentNode = stack.pop();
// 当前结点没有右结点或上一个结点（已经输出的结点）是当前结点的右结点，则输出当前结点
while (currentNode.right == null || currentNode.right == rightNode) {
System.out.print(currentNode.value + " ");
rightNode = currentNode;
if (stack.isEmpty()) {
return; //root以输出，则遍历结束
}
currentNode = stack.pop();
}
stack.push(currentNode); //还有右结点没有遍历
currentNode = currentNode.right;
}
}
/**
* 广度优先遍历二分搜索树，又称层次遍历，用的是队列
* @param root
*/
public void breadthFirstTraverse(Node<E> root) {
Queue<Node<E>> queue = new LinkedList<Node<E>>();
Node<E> currentNode = null;
queue.offer(root);
while (!queue.isEmpty()) {
currentNode = queue.poll();
System.out.print(currentNode.value + " ");
if (currentNode.left != null)
queue.offer(currentNode.left);
if (currentNode.right != null)
queue.offer(currentNode.right);
}
}
}
}
运行结果如下，与前面理论分析完全对应。
