最近看了一下大學(xué)的數(shù)據(jù)結(jié)構(gòu)，??學(xué)到了以前沒學(xué)到的東西看到了二叉樹那一塊，感覺二叉樹是個很重要的東西，就看了一下底層是怎么實現(xiàn)的，雖然能看懂書上用c語言寫的偽代碼，但是不能運行，身為一個Java程序員，既然別人能用其他的語言能實現(xiàn)，自己也去試著寫了一下。
首先給出二叉樹的節(jié)點代碼
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;
}
}
然后模擬一個棧的代碼，會在后面非遞歸的時候用到
由于只是去遍歷所有節(jié)點，沒有考慮性能上的問題，只是讓大家了解思路，底層用ArrayList去實現(xiàn)棧功能
/*
模擬棧的功能
*/
public class Stack<E> {
public List<E> mBinTrees = new ArrayList<>();
/**
* 把節(jié)點放入棧
*
* @param binTree
*/
public void push(E binTree) {
mBinTrees.add(binTree);
}
/**
* 從棧頂pop出一個節(jié)點并得到這個節(jié)點
*
* @return
*/
public E pop() {
if (mBinTrees != null) {
return mBinTrees.remove(mBinTrees.size() - 1);
}
return null;
}
/**
* 判斷棧里是否還有數(shù)據(jù)
*
* @return
*/
public boolean isEmpty() {
return mBinTrees.size() == 0;
}
/**
* 查看當(dāng)前棧頂?shù)脑? *
* @return
*/
public E top() {
return mBinTrees.get(mBinTrees.size() - 1);
}
}
（1）先序遍歷
先看下先序遍歷的流程圖，接下來的代碼也會根據(jù)此圖是遍歷
先序遍歷顧名思義，就是先會遍歷根節(jié)點->左孩子->右孩子。遍歷是從根節(jié)點開始，遇到每個節(jié)點時，其遍歷過程為：
- 訪問根節(jié)點；
- 先序遍歷其左子樹；
- 先序遍歷其右子樹；
先序遍歷遞歸實現(xiàn)代碼：
/**
* 前序遍歷 遞歸
*/
public static void preOrderTraversal(BinTree binTree) {
if (binTree != null) {
System.out.print(binTree.name);
preOrderTraversal(binTree.left);
preOrderTraversal(binTree.right);
}
}
先序遍歷非遞歸實現(xiàn)代碼
/**
* 前序遍歷 非遞歸
* 輸出結(jié)果 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;
}
}
}
輸出結(jié)果
ABDFECGHI
(2)中序遍歷
中序遍歷是指對樹中任一節(jié)點的訪問是在遍歷完其左子樹后進行的，訪問此結(jié)點后再對其右子樹遍歷。遍歷從根節(jié)點開始，遇到每個結(jié)點時，其遍歷過程為：
- 中序遍歷其左子樹；
- 訪問根節(jié)點；
- 中序遍歷其右子樹
中序遍歷遞歸實現(xiàn)代碼：
/**
* 中序遍歷 遞歸
* DBEFAGHCI
*/
public static void inOrderTraversal(BinTree binTree) {
if (binTree != null) {
inOrderTraversal(binTree.left);
System.out.print(binTree.name);
inOrderTraversal(binTree.right);
}
}
中序遍歷非遞歸實現(xiàn)代碼：
/**
* 中序遍歷 非遞歸
* 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;
}
}
}
過程
在沿左子樹深入時，進入一個結(jié)點就將其壓人堆棧。若是先序遍歷，則在入棧之前訪問之；
當(dāng)沿左分支深人不下去時，則返回，即從堆棧中彈出前面壓人的結(jié)點；若為中序遍歷，則此時訪問
該結(jié)點，然后從該結(jié)點的右子樹繼續(xù)深入；若為后序遍歷，則將此結(jié)點二次入棧，然后從該結(jié)點的
右子樹繼續(xù)深入，與前面類同，仍為進入一個結(jié)點入棧一個結(jié)點，深入不下去再返回，直到第二次
從棧里彈出該結(jié)點，才訪問之。
因此，按照上述描述的過程，使用堆棧可以直接實現(xiàn)相應(yīng)的非遞歸算法。先序和中序算法相
對間果些，而后序遍歷因為需要兩次將一個結(jié)點人棧，情況稍復(fù)雜些。下面只以中序遍所頭份
介紹二叉樹遍歷的非遞歸算法。
在按中序遍歷二叉樹時，遇到一個結(jié)點，就把它入棧，并去遍歷它的左子樹，當(dāng)左子樹遍歷結(jié)束后，從棧頂彈出這個結(jié)點并訪問它，然后按其右指針再去中序遍歷該結(jié)點的右子樹。
（3）后序遍歷
后序遍歷是指對樹中任一節(jié)點的訪問是在遍歷完其左、右子樹后進行的。遍歷從根節(jié)點開始，遇到每個結(jié)點時，其遍歷過程為：
- 后序遍歷其左子樹；
- 后序遍歷其右子樹
- 訪問根節(jié)點；
后序遍歷遞歸實現(xiàn)代碼：
/**
* 后續(xù)遍歷 遞歸
* DEFBHGICA
*
* @param tree
*/
public static void postOrderTraversal(BinTree tree) {
if (tree != null) {
postOrderTraversal(tree.left);
postOrderTraversal(tree.right);
System.out.print(tree.name);
}
}
后序遍歷非遞歸實現(xiàn)代碼：
有兩種思路：
第一種思路：對于任一結(jié)點P，將其入棧，然后沿其左子樹一直往下搜索，直到搜索到?jīng)]有左孩子的結(jié)點，此時該結(jié)點出現(xiàn)在棧頂，但是此時不能將其出棧并訪問，因此其右孩子還為被訪問。所以接下來按照相同的規(guī)則對其右子樹進行相同的處理，當(dāng)訪問完其右孩子時，該結(jié)點又出現(xiàn)在棧頂，此時可以將其出棧并訪問。這樣就保證了正確的訪問順序?？梢钥闯?，在這個過程中，每個結(jié)點都兩次出現(xiàn)在棧頂，只有在第二次出現(xiàn)在棧頂時，才能訪問它。因此需要多設(shè)置一個變量標(biāo)識該結(jié)點是否是第一次出現(xiàn)在棧頂。
/**
* 后續(xù)遍歷 非遞歸
* 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);
}
}
}
}
第二種思路：對于任一節(jié)點，將其左子樹入棧，直到左子樹為空，查看當(dāng)前棧頂?shù)迷厥欠裼杏易訕浠蛘弋?dāng)前右子樹不等于前一訪問節(jié)點，如有，重復(fù)之前將其左子樹入棧，沒有，訪問當(dāng)前節(jié)點，并把此節(jié)點出棧，并把當(dāng)前節(jié)點作為訪問過的節(jié)點。
/**
* 后續(xù)遍歷 非遞歸
* 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中有現(xiàn)成的隊列，所以就選擇了鏈表式的隊列。
非遞歸代碼
/**
* 層序遍歷
*
* @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);
}
}
}
先寫到這吧，等學(xué)到了再更新。
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;
}
