二叉树的几种遍历方式

发表于 更新于 分类于

二叉树的几种遍历

FIRST

一些废话先写在前面

不论是什么时候，假如你想要前进，想要进步，那就先让自己动起来，只要自己动起来了，那么很多东西都好说了。

很多的时候就是不想动起来，那么就今天不想动，明天不想动，后天不想动，以后也都不想动了。

努力的时候要想想自己是真的收获了吗，而不是只是努力了一个小时就觉得自己有收获了。

进入正题：

什么是二叉树？

简单的来说，那就是树的一种特型，是树中比较简单的一种，其中每个节点都有左子树和右子树（只不过有可能是空的nullptr）
将示意图画出来，就像是现实中的树倒过来一样，所以叫做树，而这种树就叫做二叉树。
由二叉树左右节点是否为空，是否对称等又可以引出来不同的二叉树类型，比如说完美二叉树，对称二叉树等等，但是这些二叉树只不过是在描述二叉树的样式，并不像树、二叉树的提出这么惊世骇俗，那么别出心裁。

什么是树？

树是一种形象化的说法。
从根部开始，向一个方向延伸，具有多个分支结构，这样的数据就叫做树。从图像上看是如此，实际上在编程中树的构成方式有很多种，力扣中的题目大多是使用结构体，外加抽象的树类型（Treenode）的方式构成的。

A Treenode is a data structure that represents one entry of a tree, which is composed of multiple of such nodes.
The topmost node of a tree is called the “root”, and each node (with the exception of the root node) is associated with one parent node. Likewise, each node can have an arbitrary number of child nodes.

怎么求二叉树？

对于一个简单的二叉树：有三种经典的遍历的方法。
前序遍历：根左右
中序遍历：左根右
后序遍历：左右根

前序遍历就是从根节点出发，先遍历到最左边的根，然后再逐一向左遍历，其中会遍历完左边的某一个节点下面的所有节点，再会去遍历这个节点的父节点的右子节点。

1
2
3
4
5
6
7
8
void preorder(TreeNode *root, vector<int> &res) {
    if (root == nullptr) {
        return;
    }
    res.push_back(root->val);//将当前节点的值存到res里
    preorder(root->left, res);
    preorder(root->right, res);
}

这里以灵神的一段程序为例：

这是一段leetcode上的代码，由灵神撰写，为了方便我直接拿来用了。
**这里为了方便储存数据，使用了栈，使用了递归的写法，假如下一个节点是空，那么就返回。所以我们现在模拟一下它的行动，在根节点，假如不是空节点，那么就会将当前节点的数据储存起来，也就是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
push_back(root->val)
```  

然后搜索左边的那一个节点，接下来，储存当前节点的数据，紧接着，又是递归到左边的节点…………  

**直到左边的节点已经没有下一个数据，也就是nullptr的时候**，会从“下一个节点”返回到 **“最后一个有数据的节点”** ，随后，搜索“最后一个有数据的节点”的右节点……    

然后就是返回到父节点，也就是上一层，再次搜索右节点，因为之前就是左节点下到了最底部，现在返回，就是搜索的从低到高的每一层节点的右节点。  

这就是**前序遍历**。    

那么，什么是中序遍历呢？    

>中序遍历：**左根右**  

那么就是先递归到最左的节点，然后记录最左边的节点，然后从最左边的节点开始向上记录每一个父节点的值，然后就是父节点的右节点的值，仿照上面灵神的程序，我们可以这么写：    

```C++
if(root == nullptr)
    return;
p(root->left,ans);
ans.push_back(root);
p(root->right,ans);
```    

>后序遍历：**左右根**  

这个也是十分简单的了，既然是左右根，那就是先是搜索到最左端节点的值，然后搜索与它同父节点的值，然后再搜索父节点的值，再以此类推。  

```C++  

if(root == nullptr)
    return;
p(root->left,ans);
p(root->right,ans);
ans.push_back(root);
```  

那么在力扣中使用的二叉树到底是什么结构呢？
>以下代码来自[leetcode](leetcode.com)  

```C++ 
 // Definition for a binary tree node.
  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  };

下面是对TreeNode结构的介绍：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct TreeNode {  
      int val;                     // 节点中存储的整数值  
      TreeNode *left;              // 指向左子节点的指针  
      TreeNode *right;             // 指向右子节点的指针  
  
      // 默认构造函数，初始化节点值为0，左右子节点指针为nullptr  
      TreeNode() : val(0), left(nullptr), right(nullptr) {}  
  
      // 带一个参数的构造函数，只初始化节点值，左右子节点指针为nullptr  
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}  
  
      // 带三个参数的构造函数，初始化节点值以及左右子节点指针  
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}  
  };

int val;：每个TreeNode结构体都有一个整数值val，用于存储节点的值。
TreeNode *left; 和 TreeNode *right;：这两个是指针，分别指向节点的左子节点和右子节点。
该结构体还提供了三个构造函数：

默认构造函数：这个构造函数不接受任何参数。它将val初始化为0，并将left和right指针初始化为nullptr（表示没有子节点）。

带一个参数的构造函数：这个构造函数接受一个整数x作为参数，将val初始化为x，并将left和right指针初始化为nullptr。

带三个参数的构造函数：这个构造函数接受一个整数x以及两个TreeNode指针left和right作为参数。它将val初始化为x，并将left和right指针分别初始化为传入的left和right指针。

这样的设计使得在创建二叉树节点时，可以根据需要选择使用哪个构造函数，从而提供更大的灵活性。

-我的Bilibili墨泽moozy

-我的公众号墨泽moozy

-我的知乎干干净净我的心

-我的博客