樹(shù)是編程中的一種最為重要的數(shù)據(jù)結(jié)構(gòu)了，應(yīng)用范圍很廣。比如說(shuō)人們常用的操作系統(tǒng)，如Windows和Linux，它們的文件管理系統(tǒng)都是樹(shù)型結(jié)構(gòu)的。而這其中二叉樹(shù)又是應(yīng)用最廣的樹(shù)，因此也是很多程序員入門(mén)時(shí)學(xué)習(xí)的主要數(shù)據(jù)結(jié)構(gòu)。

從外表上來(lái)看，二叉樹(shù)非常簡(jiǎn)單，每個(gè)節(jié)點(diǎn)延伸出兩個(gè)子節(jié)點(diǎn)，一層一層地延續(xù)下去，像人們的祖譜一樣，非常容易理解。

二叉樹(shù)相關(guān)的編程中，二叉樹(shù)的遍歷是最為常見(jiàn)的一種，對(duì)于普通人來(lái)說(shuō)，如果想遍歷上圖的二叉樹(shù)的話(huà)，很多人都會(huì)很直白地一層一層讀下去，于是遍歷出來(lái)的結(jié)果就是ABCDEFG。非常直觀(guān)。

但是計(jì)算機(jī)的計(jì)算方式和人們的思維方式是不一樣的，這種層次遍歷對(duì)于人來(lái)說(shuō)非常好理解，但是對(duì)于計(jì)算機(jī)來(lái)說(shuō)，并不是很好理解。

所以為了更符合計(jì)算機(jī)的思考方式，研究人員提出了先序遍歷、中序遍歷、后序遍歷三種算法。這三種算法都是如何遍歷二叉樹(shù)的呢？我們來(lái)看一下。

一、先序遍歷

先序遍歷(Pre-order)，也叫前序遍歷，按照根左右的順序沿一定路徑經(jīng)過(guò)路徑上所有的結(jié)點(diǎn)。在二叉樹(shù)中，對(duì)每個(gè)節(jié)點(diǎn)都是，先根后左再右。也就是，根左右。具體實(shí)現(xiàn)方法如下：

public static void preOrder(BinTreeNode t) {
    if (null == t ) return;
    System.out.println(t.getData());
    preOrder(t.getlChild());
    preOrder (t.getrChild());
}

對(duì)于上圖的二叉樹(shù)，遍歷結(jié)果為，abdcegf。

二、中序遍歷

中序遍歷，也叫中根遍歷、中序周游。中序遍歷首先遍歷左子樹(shù)，然后訪(fǎng)問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)。也就是，左根右。具體實(shí)現(xiàn)方法如下：

public static void inOrder(BinTreeNode t) {
    if (null == t ) return;
    inOrder(t.getlChild());
    System.out.println(t.getData());
    inOrder (t.getrChild());
}

對(duì)于上圖的二叉樹(shù)，遍歷結(jié)果為：dbagefc。

三、后序遍歷

后序遍歷（LRD）也叫做后根遍歷、后序周游。后序遍歷首先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪(fǎng)問(wèn)要節(jié)點(diǎn)。也就是，左右根。具體實(shí)現(xiàn)方法如下：

public static void postOrder(BinTreeNode t) {
    if (null == t ) return;
    postOrder(t.getlChild());
    postOrder (t.getrChild());
    System.out.println(t.getData());
}

對(duì)于上圖的二叉樹(shù)，遍歷結(jié)果為：dbgefca。

可以看到，上面的三種算法中，區(qū)別就是在于打印節(jié)點(diǎn)數(shù)據(jù)（應(yīng)用節(jié)點(diǎn)數(shù)據(jù)域）的代碼位置不一樣而已。對(duì)于計(jì)算機(jī)來(lái)說(shuō)，使用遞歸算法，非常簡(jiǎn)潔明了。

四、層次遍歷

那么更符合人們習(xí)慣的層次遍歷，計(jì)算機(jī)又需要怎樣執(zhí)行呢？我們可以看到，對(duì)于計(jì)算機(jī)而言，最大的問(wèn)題在于它并不知道哪個(gè)節(jié)點(diǎn)屬于哪一層，因此，我們需要使用代碼記錄，每個(gè)層次的節(jié)點(diǎn)信息。通常情況下，我們可以使用隊(duì)列來(lái)實(shí)現(xiàn)。代碼如下：

public static void levelOrder(BinTreeNode t) {
    Queue<BinTreeNode> q = new LinkedList<>();
    q.offer(t);
    while (!q.isEmpty()){
        int size = q.size();
        for (int i=0; i<size; i++) {
            BinTreeNode node = q.poll();
            System.out.println(node.getData());
            if (node.getlChild()!= null) q.offer(node.getlChild());
            if (node.getrChild() != null) q.offer(node.getrChild());
        }
    }
}

打印結(jié)果為：abcdefg。

我們可以看到，對(duì)于人類(lèi)來(lái)講最為簡(jiǎn)潔明了的層次算法，對(duì)于計(jì)算機(jī)編程來(lái)說(shuō)，需要的代碼量要大很多。原因在于對(duì)于人們來(lái)說(shuō)直觀(guān)的約束條件，如哪個(gè)節(jié)點(diǎn)在哪一層，對(duì)于計(jì)算機(jī)來(lái)說(shuō)并不直觀(guān)。因此，很多時(shí)候?qū)τ诔绦騿T來(lái)說(shuō)，要按照計(jì)算機(jī)的思維來(lái)看問(wèn)題，這樣寫(xiě)出的代碼才能更符合計(jì)算機(jī)的習(xí)慣。