最近看了一下大学的数据结构，🈶学到了以前没学到的东西看到了二叉树那一块，感觉二叉树是个很重要的东西，就看了一下底层是怎么实现的，虽然能看懂书上用c语言写的伪代码，但是不能运行，身为一个Java程序员，既然别人能用其他的语言能实现，自己也去试着写了一下。
首先给出二叉树的节点代码
public class BinTree {
public BinTree(String name) {
this.name = name;
}
public BinTree(int name) {
this.name = name + "";
}
BinTree left;
BinTree right;
public String name;
public void setLeft(BinTree left) {
this.left = left;
}
public void setRight(BinTree right) {
this.right = right;
}
public void setName(String name) {
this.name = name;
}
}
然后模拟一个栈的代码，会在后面非递归的时候用到
由于只是去遍历所有节点，没有考虑性能上的问题，只是让大家了解思路，底层用ArrayList去实现栈功能
/*
模拟栈的功能
*/
public class Stack<E> {
public List<E> mBinTrees = new ArrayList<>();
/**
* 把节点放入栈
*
* @param binTree
*/
public void push(E binTree) {
mBinTrees.add(binTree);
}
/**
* 从栈顶pop出一个节点并得到这个节点
*
* @return
*/
public E pop() {
if (mBinTrees != null) {
return mBinTrees.remove(mBinTrees.size() - 1);
}
return null;
}
/**
* 判断栈里是否还有数据
*
* @return
*/
public boolean isEmpty() {
return mBinTrees.size() == 0;
}
/**
* 查看当前栈顶的元素
*
* @return
*/
public E top() {
return mBinTrees.get(mBinTrees.size() - 1);
}
}
（1）先序遍历
先看下先序遍历的流程图，接下来的代码也会根据此图是遍历
先序遍历顾名思义，就是先会遍历根节点->左孩子->右孩子。遍历是从根节点开始，遇到每个节点时，其遍历过程为：
- 访问根节点；
- 先序遍历其左子树；
- 先序遍历其右子树；
先序遍历递归实现代码：
/**
* 前序遍历 递归
*/
public static void preOrderTraversal(BinTree binTree) {
if (binTree != null) {
System.out.print(binTree.name);
preOrderTraversal(binTree.left);
preOrderTraversal(binTree.right);
}
}
先序遍历非递归实现代码
/**
* 前序遍历 非递归
* 输出结果 ABDFECGHI
*/
public static void preOrderTraversalNoDIGUI(BinTree binTree) {
Stack<BinTree> stack = new Stack();
BinTree t = binTree;
while (t != null || !stack.isEmpty()) {
while (t != null) {
System.out.print(t.name);
stack.push(t);
t = t.left;
}
if (!stack.isEmpty()) {
t = stack.pop();
t = t.right;
}
}
}
输出结果
ABDFECGHI
(2)中序遍历
中序遍历是指对树中任一节点的访问是在遍历完其左子树后进行的，访问此结点后再对其右子树遍历。遍历从根节点开始，遇到每个结点时，其遍历过程为：
- 中序遍历其左子树；
- 访问根节点；
- 中序遍历其右子树
中序遍历递归实现代码：
/**
* 中序遍历 递归
* DBEFAGHCI
*/
public static void inOrderTraversal(BinTree binTree) {
if (binTree != null) {
inOrderTraversal(binTree.left);
System.out.print(binTree.name);
inOrderTraversal(binTree.right);
}
}
中序遍历非递归实现代码：
/**
* 中序遍历 非递归
* DBEFAGHCI
*/
public static void inOrderTraversalNODIGUI(BinTree binTree) {
Stack<BinTree> stack = new Stack();
BinTree t = binTree;
while (t != null || !stack.isEmpty()) {
while (t != null) {
stack.push(t);
t = t.left;
}
if (!stack.isEmpty()) {
t = stack.pop();
System.out.println(t.name);
t = t.right;
}
}
}
过程
在沿左子树深入时，进入一个结点就将其压人堆栈。若是先序遍历，则在入栈之前访问之；
当沿左分支深人不下去时，则返回，即从堆栈中弹出前面压人的结点；若为中序遍历，则此时访问
该结点，然后从该结点的右子树继续深入；若为后序遍历，则将此结点二次入栈，然后从该结点的
右子树继续深入，与前面类同，仍为进入一个结点入栈一个结点，深入不下去再返回，直到第二次
从栈里弹出该结点，才访问之。
因此，按照上述描述的过程，使用堆栈可以直接实现相应的非递归算法。先序和中序算法相
对间果些，而后序遍历因为需要两次将一个结点人栈，情况稍复杂些。下面只以中序遍所头份
介绍二叉树遍历的非递归算法。
在按中序遍历二叉树时，遇到一个结点，就把它入栈，并去遍历它的左子树，当左子树遍历结束后，从栈顶弹出这个结点并访问它，然后按其右指针再去中序遍历该结点的右子树。
（3）后序遍历
后序遍历是指对树中任一节点的访问是在遍历完其左、右子树后进行的。遍历从根节点开始，遇到每个结点时，其遍历过程为：
- 后序遍历其左子树；
- 后序遍历其右子树
- 访问根节点；
后序遍历递归实现代码：
/**
* 后续遍历 递归
* DEFBHGICA
*
* @param tree
*/
public static void postOrderTraversal(BinTree tree) {
if (tree != null) {
postOrderTraversal(tree.left);
postOrderTraversal(tree.right);
System.out.print(tree.name);
}
}
后序遍历非递归实现代码：
有两种思路：
第一种思路：对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。
/**
* 后续遍历 非递归
* DEFBHGICA
*
* @param root
*/
public static void postOrderTraversalNODIGUI(BinTree root) {
BinTree cur;
BinTree pre = null;
Stack<BinTree> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
cur = stack.top();
if ((cur.left == null && cur.right == null)
|| (pre != null && (pre == cur.left || pre == cur.right))) {
System.out.println(cur.name);
stack.pop();
pre = cur;
} else {
if (cur.right != null) {
stack.push(cur.right);
}
if (cur.left != null) {
stack.push(cur.left);
}
}
}
}
第二种思路：对于任一节点，将其左子树入栈，直到左子树为空，查看当前栈顶得元素是否有右子树或者当前右子树不等于前一访问节点，如有，重复之前将其左子树入栈，没有，访问当前节点，并把此节点出栈，并把当前节点作为访问过的节点。
/**
* 后续遍历 非递归
* DEFBHGICA
*
* @param root
*/
public static void postOrderTraversalNODIGUI2(BinTree root) {
BinTree tree = root;
BinTree cur = null;
BinTree pre = null;
Stack<BinTree> stack = new Stack<>();
while (!stack.isEmpty() || tree != null) {
while (tree != null) {
stack.push(tree);
tree = tree.left;
}
cur = stack.top();
if (cur.right != null && (pre != null && cur.right != pre)) {
tree = cur.right;
} else {
System.out.println(cur.name);
stack.pop();
}
pre = cur;
}
}
（4）层序遍历
层序遍历用到了队列，Java中有现成的队列，所以就选择了链表式的队列。
非递归代码
/**
* 层序遍历
*
* @param boot
*/
public static void LevelOrderTraversal(BinTree boot) {
LinkedBlockingQueue<BinTree> queue = new LinkedBlockingQueue<>();
BinTree tree;
if (boot == null) return;
queue.add(boot);
while (!queue.isEmpty()) {
tree = queue.remove();
System.out.println(tree.name);
if (tree.left != null) {
queue.add(tree.left);
}
if (tree.right != null) {
queue.add(tree.right);
}
}
}
先写到这吧，等学到了再更新。
2017.3.9
（5）求一个二叉树的深度
/**
* 树的深度
*用到了递归
* @param bt
*/
public static int postOrderGetHeight(BinTree bt) {
int leftHeight;
int rightHeight;
int maxHeight;
if (bt != null) {
leftHeight = postOrderGetHeight(bt.left);
rightHeight = postOrderGetHeight(bt.right);
maxHeight = leftHeight > rightHeight ? leftHeight : rightHeight;
return maxHeight + 1;
}
return 0;
}
