前情提要：
在上次KNN中我們用到了KD樹的搭建以及回溯算法，尤其是回溯算法給我搞得要死要活的，所以今天停了一下手里的工作，來重新學(xué)些一次二叉樹的搭建以及深度優(yōu)先搜索的三種遍歷方式。

二叉樹是什么

在計(jì)算機(jī)科學(xué)中，二叉樹（英語：Binary tree）是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支（即不存在分支度大于2的節(jié)點(diǎn)）的樹結(jié)構(gòu)。通常分支被稱作“左子樹”或“右子樹”。二叉樹的分支具有左右次序，不能隨意顛倒。

這是來自wiki的解釋，我們來劃一下重點(diǎn)：
1、最多只有兩個(gè)
2、具有左右順序，不能顛倒

搭建二叉樹

寫到這里，我又停了幾分鐘，因?yàn)楸闅v的時(shí)候有前序，中序，后序，那么搭建有沒有呢？我仔細(xì)想了一下，我覺得有，因?yàn)橹栽诒闅v的時(shí)候，會(huì)有這些情況，是因?yàn)樵诒闅v的時(shí)候，我們會(huì)有一個(gè)取值的操作，正是這個(gè)取值的操作的順序決定了三種不同的遍歷方式，相似的，搭建的時(shí)候也有一個(gè)賦值的操作，所以我們應(yīng)該也可以用三種方式搭建（這是深度優(yōu)先搜索的范疇，廣度優(yōu)先搜索不行，因?yàn)閺V度優(yōu)先搜索依賴于隊(duì)列長度）。
現(xiàn)在先用前序展示一下：

pNode BinaryTree::PlanetTree(int val, int pos) {
    pNode tree = new node(val);
    if (pos >= depth) {
        return tree;
    } else {
        srand(time(0));
        tree->left = PlanetTree(rand() % 9, pos + 1);
        tree->right = PlanetTree(rand() % 9, pos + 1);
        return tree;
    }
}

寫到這里，我還加入一個(gè)小插曲：
因?yàn)閼械媒o每個(gè)節(jié)點(diǎn)賦值，于是我想用c++的隨機(jī)數(shù)來生成，想著就掏出了

#include <random>

等我rand()函數(shù)一用，傻眼了。
怎么數(shù)都一樣呢？

rand()函數(shù)是C++標(biāo)準(zhǔn)函數(shù)庫提供的隨機(jī)數(shù)生成器，生成0－RAND_MAX之間的一個(gè)“偽隨機(jī)”整數(shù)，理論上可以產(chǎn)生的最大數(shù)值為2^16-1,即32767。
rand()函數(shù)不接受參數(shù)，默認(rèn)以1為種子（seed,即起始值），這里的種子在隨機(jī)數(shù)產(chǎn)生的過程中起了很大的作用，甚至可以說是起了決定性的作用。

想必大家現(xiàn)在明白了，就是因?yàn)檫@個(gè)種子數(shù)都是1，導(dǎo)致了所有的隨機(jī)數(shù)一樣，當(dāng)時(shí)我看到這里，整個(gè)人都不好了，說好的隨機(jī)數(shù)呢？但是，深入一查，原來是這樣（偷笑

#include <time.h>
#include <random>

//僅僅是演示，別問我主方法哪里去了
srand(time(0));
int x = rand();
int y = rand() % (b - a) * a; //生成區(qū)間[a, b]之間的隨機(jī)數(shù)，友情提示，a不要為0哦。

然后還有什么呢？
我還想說一下，c++ 的偽隨機(jī)數(shù)是怎么生成的？
電腦是做不到真正隨機(jī)的，給大家返回的都是偽隨機(jī)數(shù)，想必這個(gè)大家都知道。但是，偽隨機(jī)數(shù)是怎么產(chǎn)生的呢？
計(jì)算機(jī)對(duì)一個(gè)數(shù)（隨機(jī)種子）進(jìn)行線性變化，得到一個(gè)數(shù)，這個(gè)數(shù)就是偽隨機(jī)數(shù)，但是當(dāng)隨機(jī)種子多的時(shí)候，這些數(shù)就成高斯分布，所以把他視為隨機(jī)數(shù)。

扯遠(yuǎn)了。
然后是什么呢？

遍歷二叉樹

遍歷二叉樹其實(shí)有兩種方法，
1、廣度優(yōu)先搜索
2、深度優(yōu)先搜索
我說一下，我對(duì)他們兩個(gè)的理解吧。
凡是DFS可以解決的問題，BFS都可以，而且，DFS因?yàn)樗倪f歸思想簡單易懂，而處于鄙視鏈的下游，而且BFS可以自定義隊(duì)列長度，不用擔(dān)心遞歸太深而爆棧（其實(shí)DFS也行，就是自己寫個(gè)棧，然后不調(diào)用遞歸，也就是非遞歸調(diào)用方式）。
今天我們主要說一下DFS：

前序遍歷

所謂前序遍歷,就是遍歷的時(shí)候，先取根節(jié)點(diǎn)(狹義的根節(jié)點(diǎn))的值，然后再取左子樹，最后右子樹。
反應(yīng)在代碼上就是：

void BinaryTree::PreOrder(pNode root) {
    if (root != NULL) {
        std::cout<<root->val<<std::endl;
        PreOrder(root->left);
        PreOrder(root->right);
    }
}

簡單吧，注意取值的位置，也就是輸出的位置。

中序遍歷

對(duì)比前序遍歷，我們就可以發(fā)現(xiàn)不同的地方，中序遍歷就是，先取左節(jié)點(diǎn)（最左面節(jié)點(diǎn)）的值，然后再去取根節(jié)點(diǎn)的值，最后取右節(jié)點(diǎn)的值。
代碼：

void BinaryTree::InOrder(pNode root) {
    if (root) {
        InOrder(root->left);
        std::cout<<root->val<<std::endl;
        InOrder(root->right);
    }
}

后序遍歷

后序遍歷就比較有意思了，大家可以先猜一下是什么順序，再看后面的代碼

void BinaryTree::PostOrder(pNode root) {
    if (root) {
        PostOrder(root->left);
        PostOrder(root->right);
        std::cout<<root->val<<std::endl;
    }
}

沒錯(cuò)，左右中

聯(lián)想

在知乎，看到一個(gè)回答，說遞歸爆棧，但是BFS沒事的，讓我想到了，那種非遞歸的實(shí)現(xiàn)方式，我就好奇，為啥都叫棧，實(shí)現(xiàn)方法就不一樣呢，后來我發(fā)現(xiàn)其實(shí)這兩種都一樣，都是調(diào)用棧，只不過為了防止爆棧，自己實(shí)現(xiàn)了一個(gè)棧。

最后貼上完整代碼：

//
// Created by vophan on 19-1-27.
//

#ifndef BINARYTREE_BINARYTREE_H
#define BINARYTREE_BINARYTREE_H

#include <random>
#include <time.h>

typedef struct Node{
    int val;
    struct Node* left;
    struct Node* right;
    Node(int val):val(val) {}
}node,*pNode;

class BinaryTree{
public:
    BinaryTree(int depth);
    int depth;
    pNode root;
    pNode PlanetTree(int val, int pos);
    void PreOrder(pNode root);
    void InOrder(pNode root);
    void PostOrder(pNode root);
};

BinaryTree::BinaryTree(int depth):depth(depth) {
    root = PlanetTree(1,0);
}
pNode BinaryTree::PlanetTree(int val, int pos) {
    pNode tree = new node(val);
    if (pos >= depth) {
        return tree;
    } else {
        srand(time(0));
        tree->left = PlanetTree(rand() % 9, pos + 1);
        tree->right = PlanetTree(rand() % 9, pos + 1);
        return tree;
    }

}

void BinaryTree::PreOrder(pNode root) {
    if (root != NULL) {
        std::cout<<root->val<<std::endl;
        PreOrder(root->left);
        PreOrder(root->right);
    }
}

void BinaryTree::InOrder(pNode root) {
    if (root) {
        InOrder(root->left);
        std::cout<<root->val<<std::endl;
        InOrder(root->right);
    }
}

void BinaryTree::PostOrder(pNode root) {
    if (root) {
        PostOrder(root->left);
        PostOrder(root->right);
        std::cout<<root->val<<std::endl;
    }

}

#endif //BINARYTREE_BINARYTREE_H