前情提要：
在上次KNN中我们用到了KD树的搭建以及回溯算法，尤其是回溯算法给我搞得要死要活的，所以今天停了一下手里的工作，来重新学些一次二叉树的搭建以及深度优先搜索的三种遍历方式。
二叉树是什么
在计算机科学中，二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。
这是来自wiki的解释，我们来划一下重点：
1、最多只有两个
2、具有左右顺序，不能颠倒
搭建二叉树
写到这里，我又停了几分钟，因为遍历的时候有前序，中序，后序，那么搭建有没有呢？我仔细想了一下，我觉得有，因为之所以在遍历的时候，会有这些情况，是因为在遍历的时候，我们会有一个取值的操作，正是这个取值的操作的顺序决定了三种不同的遍历方式，相似的，搭建的时候也有一个赋值的操作，所以我们应该也可以用三种方式搭建（这是深度优先搜索的范畴，广度优先搜索不行，因为广度优先搜索依赖于队列长度）。
现在先用前序展示一下：
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;
}
}
写到这里，我还加入一个小插曲：
因为懒得给每个节点赋值，于是我想用c++的随机数来生成，想着就掏出了
#include <random>
等我rand()函数一用，傻眼了。
怎么数都一样呢？
rand()函数是C++标准函数库提供的随机数生成器，生成0－RAND_MAX之间的一个“伪随机”整数，理论上可以产生的最大数值为2^16-1,即32767。
rand()函数不接受参数，默认以1为种子（seed,即起始值），这里的种子在随机数产生的过程中起了很大的作用，甚至可以说是起了决定性的作用。
想必大家现在明白了，就是因为这个种子数都是1，导致了所有的随机数一样，当时我看到这里，整个人都不好了，说好的随机数呢？但是，深入一查，原来是这样（偷笑
#include <time.h>
#include <random>
//仅仅是演示，别问我主方法哪里去了
srand(time(0));
int x = rand();
int y = rand() % (b - a) * a; //生成区间[a, b]之间的随机数，友情提示，a不要为0哦。
然后还有什么呢？
我还想说一下，c++ 的伪随机数是怎么生成的？
电脑是做不到真正随机的，给大家返回的都是伪随机数，想必这个大家都知道。但是，伪随机数是怎么产生的呢？
计算机对一个数（随机种子）进行线性变化，得到一个数，这个数就是伪随机数，但是当随机种子多的时候，这些数就成高斯分布，所以把他视为随机数。
扯远了。
然后是什么呢？
遍历二叉树
遍历二叉树其实有两种方法，
1、广度优先搜索
2、深度优先搜索
我说一下，我对他们两个的理解吧。
凡是DFS可以解决的问题，BFS都可以，而且，DFS因为他的递归思想简单易懂，而处于鄙视链的下游，而且BFS可以自定义队列长度，不用担心递归太深而爆栈（其实DFS也行，就是自己写个栈，然后不调用递归，也就是非递归调用方式）。
今天我们主要说一下DFS：
前序遍历
所谓前序遍历,就是遍历的时候，先取根节点(狭义的根节点)的值，然后再取左子树，最后右子树。
反应在代码上就是：
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;
}
}
没错，左右中
联想
在知乎，看到一个回答，说递归爆栈，但是BFS没事的，让我想到了，那种非递归的实现方式，我就好奇，为啥都叫栈，实现方法就不一样呢，后来我发现其实这两种都一样，都是调用栈，只不过为了防止爆栈，自己实现了一个栈。
最后贴上完整代码：
//
// 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
网友评论