[总结][数据结构][C++][树]二叉树基础知识

最近回顾数据结构，准备把一些比较基础的内容总结一下。同时好久没有自己输出过东西了，老想写东西，却懒得动弹，现在一回来，自己的行文水平差到家里去了。先从最基础的开始吧。

树和二叉树

树是数据结构中重要的一种结构，这一点是毋庸置疑的，在实际应用当中，许多高效的算法架构都是基于树的。本篇文章仅仅在基础应用上，具体树张什么样，相信读者们都懂。可以举一个简单的例子，下图是Linux系统中实际应用的树，其目录结构就是一个树的结构。

一个实际应用当中的树

而二叉树是树的其中一种结构。n叉树中的n表示每个节点的孩子数量不超过n个，那么空树也可以说是n叉树，当然也可以说成二叉树，只有根节点的，也可以这么说(n=1,2,3,4,5...)。二叉树是树中的一个典型，掌握二叉树便可以推广到n叉树上面去。

遍历二叉树

如何遍历一棵二叉树？学过算法都知道，有先序、中序和后序这三种基本的方法（叫法可能不同，当然都可以），其中的区别是父节点与左右孩子的访问顺序的区别。那么开始写代码：

// 针对一棵二叉树，有：
/**
 * 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) {}
 * };
 */

在实现上，三者的遍历主要是根节点的放置位置不同，那么举一反三，此处仅仅展示先序遍历的代码。其他可以自行推导。

以下是递归的实现，只要考虑我们需要遍历的顺序既可。

先中后序遍历

1. 递归

class Solution {
private:
    vector<int> res;
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if (root == nullptr) {
            return this->res;
        }
        // 中
        res.push_back(root->val);
        // 左
        preorderTraversal(root->left);
        // 右
        preorderTraversal(root->right);

        return this->res;
    }
};

当然我们也可以通过迭代实现：

2. 迭代

// 此处是BFS
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if (root == nullptr) {
            return vector<int>{};
        }
        // 迭代实现
        // 中 左 右
        vector<int> res;

        stack<TreeNode *> tStack;
        TreeNode *node = root;
        tStack.push(node);

        // 存储遍历左子树的
        while(!tStack.empty()) {
            // 中
            node = tStack.top();
            tStack.pop();
            res.push_back(node->val);

            // 栈 先进后出，顺序不应该乱
            // 右
            if (node->right != nullptr)
                tStack.push(node->right);
            // 左
            if (node->left != nullptr)
                tStack.push(node->left);
        }

        return res;
    }
};

下面同样是迭代，但思路不同

// DFS
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }

        stack<TreeNode*> tStack;
        TreeNode* node = root;
        while (!tStack.empty() || node != nullptr) {
            while (node != nullptr) {
                // 中
                res.push_back(node->val);
                tStack.push(node);
                node = node->left;
            }
            // 左
            node = tStack.top();
            tStack.pop();
            // 右
            node = node->right;
        }
        return res;
    }
};

3. `Morris`遍历

class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res;
        // 判空
        if (root == nullptr) {
            return res;
        }

        // p1<-现在所在节点
        TreeNode *p1 = root, *p2 = nullptr;
        while (p1 != nullptr) {
            p2 = p1->left;
            if (p2 != nullptr) {
                while (p2->right != nullptr && p2->right != p1) {
                    p2 = p2->right;
                }
                if (p2->right == nullptr) {
                    res.push_back(p1->val);
                    p2->right = p1;
                    p1 = p1->left;
                    continue;
                } else {
                    p2->right = nullptr;
                }
            } else {
                res.push_back(p1->val);
            }
            p1 = p1->right;
        }
        return res;
    }
};

TODO: 待完善