数据结构-二叉树的定义、创建和周游（前序、中序、后序和层序）

数据结构-二叉树的定义、创建和周游（前序、中序、后序和层序）

• 前言
• 二叉树
• • 二叉树的定义
  • 完全二叉树的创建
• 二叉树的周游
• • 前序遍历
  • • 递归解决
    • 迭代解决
  • 中序遍历
  • • 递归解决
    • 迭代解决
  • 后序迭代
  • • 递归解决
    • 迭代解决
  • 层序遍历

前言

课程学习用书为《算法与数据结构-C语言描述（第三版）》
此次使用语言为C++，为了使程序清晰，建立了多个.h和.cpp的类进行实现
完整代码上传至Github可自行下载：

https://github.com/BilboJunzhou/Binary-tree

其中包括队列与二叉树的定义、创建和周游，使用时引用头文件即可

二叉树

树 是一种经常用到的数据结构，用来模拟具有树状结构性质的数据集合。

树里的每一个节点有一个值和一个包含所有子节点的列表。从图的观点来看，树也可视为一个拥有N 个节点和N-1 条边的一个有向无环图。

二叉树是一种更为典型的树状结构。如它名字所描述的那样，二叉树是每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。

二叉树的定义

二叉树包括树值、左子树节点、右子树节点，具体节点定义如下

 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) {}  
  };

完全二叉树的创建

一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
这里对函数提供数组，通过层序遍历方式建立二叉树，主要运用数据结构中队列的概念。

TreeNode* SolutionTree::SetTree(std::vector<int> nums) // 建立完全二叉树
{
    if (nums.empty())return NULL;
    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> saveNode;
    saveNode.push(root);

    for (int i = 1; i < nums.size();i++) {
        int num = nums[i];
        auto Node = saveNode.front();
        if (!Node->left) {
            TreeNode* left = new TreeNode(num);
            Node->left = left;
            saveNode.push(left);
        }
        else {
            TreeNode* right = new TreeNode(num);
            Node->right = right;
            saveNode.pop();
            saveNode.push(right);
        }
    }
    return root;
}

二叉树的周游

二叉树周游实现仔细阅读代码即可理解，就不详细介绍了，如有问题可私信。

前序遍历

按照访问根节点——左子树——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。

递归解决

void preorder(TreeNode* root, vector<int>& res) {
    if (root == nullptr) {
        return;
    }
    res.push_back(root->val);
    preorder(root->left, res);
    preorder(root->right, res);
}

vector<int> SolutionTree::RecPreorderTraversal(TreeNode* root)// 前序递归
{
    vector<int> nums;
    preorder(root, nums);
    return nums;
}

迭代解决

std::vector<int> SolutionTree::ItePreorderTraversal(TreeNode* root) // 前序迭代
{
    vector<int> nums;
    if (root == nullptr) {
        return nums;
    }

    stack<TreeNode*> stk;
    TreeNode* node = root;
    while (!stk.empty() || node != nullptr) {
        while (node != nullptr) {
            nums.push_back(node->val);
            stk.push(node);
            node = node->left;
        }
        node = stk.top();
        stk.pop();
        node = node->right;
    }
    return nums;
}

中序遍历

按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。

递归解决

void inorder(TreeNode* root, vector<int>& res) {
    if (!root) {
        return;
    }
    inorder(root->left, res);
    res.push_back(root->val);
    inorder(root->right, res);
}

std::vector<int> SolutionTree::RecInorderTraversal(TreeNode* root)// 中序递归
{
    vector<int> res;
    inorder(root, res);
    return res;
}

迭代解决

std::vector<int> SolutionTree::IteInorderTraversal(TreeNode* root)// 中序迭代
{
    vector<int> nums;
    stack<TreeNode*> stk;
    while (root != nullptr || !stk.empty()) {
        while (root != nullptr) {
            stk.push(root);
            root = root->left;
        }
        root = stk.top();
        stk.pop();
        nums.push_back(root->val);
        root = root->right;
    }
    return nums;
}

后序迭代

按照访问左子树——右子树——根节点的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。

递归解决

void postorder(TreeNode* root, vector<int>& nums) {
    if (root == nullptr) {
        return;
    }
    postorder(root->left, nums);
    postorder(root->right, nums);
    nums.push_back(root->val);
}

std::vector<int> SolutionTree::RecPostorderTraversal(TreeNode* root)// 后序递归
{
    vector<int> nums;
    postorder(root, nums);
    return nums;
}

迭代解决

std::vector<int> SolutionTree::ItePostorderTraversal(TreeNode* root)// 后序迭代
{
    vector<int> nums;
    if (root == nullptr) {
        return nums;
    }

    stack<TreeNode*> stk;
    TreeNode* prev = nullptr;
    while (root != nullptr || !stk.empty()) {
        while (root != nullptr) {
            stk.emplace(root);
            root = root->left;
        }
        root = stk.top();
        stk.pop();
        if (root->right == nullptr || root->right == prev) {
            nums.emplace_back(root->val);
            prev = root;
            root = nullptr;
        }
        else {
            stk.emplace(root);
            root = root->right;
        }
    }
    return nums;
}

层序遍历

逐层地，从左到右访问所有节点

std::vector<std::vector<int>> SolutionTree::LevelOrder(TreeNode* root)// 层序递归
{
    vector <vector <int>> ret;
    if (!root) {
        return ret;
    }

    queue <TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int currentLevelSize = q.size();
        ret.push_back(vector <int>());
        for (int i = 1; i <= currentLevelSize; ++i) {
            auto node = q.front(); q.pop();
            ret.back().push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }

    return ret;
}