C++ 数据结构——二叉树（最最最最最实用的二叉树教程）

标签：最最遍历 TreeNode val C++ right 二叉树 root left

本文章以实用为主，所以不多废话直接开整

本文所介绍的二叉树是最基础的二叉树，不是二叉搜索树，也不是平衡二叉树，就基本的二叉树

若需要 Python 版，请跳转到 Python 数据结构——二叉树（最最最最最实用的二叉树教程）

二叉树的构建

二叉树为一个父节点连接到两个子节点，若还要加入新的节点，那么此时的子节点将会变成新加入节点的父节点，以此类推，每一个父节点最多只有两个节点（所以叫二叉树）

struct TreeNode 
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 创建一个简单的二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);

就和 Python 介绍的二叉树树一样，一个最简单二叉树的创建不需要过多的东西，只需一个节点的类或者结构体即可

TreeNode* root = new TreeNode(1); // 表示最初的祖先节点
root->left = new TreeNode(2);// 表示左孩子
root->right = new TreeNode(3);// 表示右孩子
root->left->left = new TreeNode(4);// 表示左孩子的左孩子

..............................

以此类推即可，有点类似于套娃

二叉树的遍历

二叉树的遍历有别于线性表的遍历，很明显，二叉树是一个复杂的二维结构，所以二叉树有很多不同的遍历方法，其中常见的是：先序遍历，中序遍历，后序遍历以及层序遍历

先序遍历

先序遍历，中序遍历，后序遍历其实本质上都差不多，只不过是遍历顺序的不同罢了

先序遍历：就是先遍历根节点，其次是左孩子，最后是右孩子

 // 先序遍历
 void preOrderTraversal(TreeNode* root) 
 {
     if (root == NULL) return;
     cout << root->val << " ";
     preOrderTraversal(root->left);
     preOrderTraversal(root->right);
 }

对左子树进行递归，然后对子树进行递归，即可完成 根->左->右 的遍历，即先序遍历

中序遍历

中序遍历：就是先遍历左孩子，其次是根节点，最后是右孩子

// 中序遍历
void inOrderTraversal(TreeNode* root) 
{
    if (root == NULL) return;
    inOrderTraversal(root->left);
    cout << root->val << " ";
    inOrderTraversal(root->right);
}

有没有发现上述代码和有点小眼熟，其实上述代码就是先序遍历的代码只不过调换了 result 元素纳入的顺序罢了，即交换了两行代码而已，就可得到中序遍历的代码

后序遍历

后序遍历：就是先遍历左孩子，其次是右孩子，最后是根节点

// 后序遍历
void postOrderTraversal(TreeNode* root) 
{
    if (root == NULL) return;
    postOrderTraversal(root->left);
    postOrderTraversal(root->right);
    cout << root->val << " ";
}

此时或许你已经可以举一反三了，也不用我过多的解释了，将根节点的插入放到最后即可得到后序遍历的代码

层序遍历

在这里你就要稍微注意一下了，层序遍历有别于先序中序后序遍历，层序遍历是按树的高度进行遍历的，即先遍历最上面的一层，随后是第二层，再就是第三层.......等等等等

// 层序遍历
void levelOrderTraversal(TreeNode* root) 
{
    if (root == NULL) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) 
    {
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << " ";
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

我们可以借助队列，队列的性质是先进先出（FIFO），首先将根节点加入到队列中，随后开始遍历，不过要注意的是，此时的队列是动态的：

当node存在左节点或者右节点的时候队列queue将会把node的左右孩子存入其中（哪个孩子存在，就将哪个孩子存入其中），随后继续进行遍历

几种常见操作

在LeetCode上刷题你就会发现，那些基础题的解决方法大差不差，其本质是以下三种方法的变式而已，只要熟练下列常规操作，你就可以秒杀绝大多数基础题

返回树的深度

聪明的你已经返现了，当你熟练掌握二叉树的层序遍历后，只要你能得到层序遍历的层数，你就能得到二叉树的深度

// 通过层序遍历返回树的深度
int getDepth(TreeNode* root) 
{
    if (root == NULL) return 0;
    queue<TreeNode*> q;
    q.push(root);
    int depth = 0;
    while (!q.empty()) 
    {
        int size = q.size();
        for (int i = 0; i < size; i++) 
        {
            TreeNode* node = q.front();
            q.pop();
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        depth++;
    }
    return depth;
}

没错，就是这么简单

返回节点个数

// 通过先序遍历或者中序遍历或者后序遍历返回节点个数
int countNodes(TreeNode* root) 
{
    if (root == NULL) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

通过先序遍历的方式遍历整个树结构，并返回节点的总数，countNodes本身的返回值为 return 1若递归的话也会返回1，所以将所有的返回值加起来即可得到结点的个数

寻找某个节点的父节点

其实不会有问题问你让你在某二叉树中寻找一个已知的节点，她会变着法的靠你对二叉树遍历的熟练度，比如找某两个节点公共祖先等等等等，所以与其掌握如何知道一个已知节点的位置，不如掌握如何知道一个未知节点的值

// 返回某个节点的父节点
TreeNode* findParent(TreeNode* root, int val) 
{
    if (root == NULL || root->val == val) return NULL;
    if (root->left && root->left->val == val) return root;
    if (root->right && root->right->val == val) return root;
    TreeNode* leftParent = findParent(root->left, val);
    if (leftParent) return leftParent;
    return findParent(root->right, val);
}

通过递归先序遍历整棵树，先检查祖先节点的左右节点是否为其目标节点的父节点，若不是则对左子树进行遍历，若其父节点存在与左子树，则返回当期遍历到的点，若不存在于左子树则对右子树进行相同的操作即可

完整代码

#include <iostream>
#include <queue>
using namespace std;

struct TreeNode 
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Tree 
{
public:
    // 先序遍历
    void preOrderTraversal(TreeNode* root) 
    {
        if (root == NULL) return;
        cout << root->val << " ";
        preOrderTraversal(root->left);
        preOrderTraversal(root->right);
    }

    // 中序遍历
    void inOrderTraversal(TreeNode* root) 
    {
        if (root == NULL) return;
        inOrderTraversal(root->left);
        cout << root->val << " ";
        inOrderTraversal(root->right);
    }

    // 后序遍历
    void postOrderTraversal(TreeNode* root) 
    {
        if (root == NULL) return;
        postOrderTraversal(root->left);
        postOrderTraversal(root->right);
        cout << root->val << " ";
    }

    // 层序遍历
    void levelOrderTraversal(TreeNode* root) 
    {
        if (root == NULL) return;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) 
        {
            TreeNode* node = q.front();
            q.pop();
            cout << node->val << " ";
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }

    // 通过层序遍历返回树的深度
    int getDepth(TreeNode* root) 
    {
        if (root == NULL) return 0;
        queue<TreeNode*> q;
        q.push(root);
        int depth = 0;
        while (!q.empty()) 
        {
            int size = q.size();
            for (int i = 0; i < size; i++) 
            {
                TreeNode* node = q.front();
                q.pop();
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            depth++;
        }
        return depth;
    }

    // 通过先序遍历或者中序遍历或者后序遍历返回节点个数
    int countNodes(TreeNode* root) 
    {
        if (root == NULL) return 0;
        return 1 + countNodes(root->left) + countNodes(root->right);
    }

    // 返回某个节点的父节点
    TreeNode* findParent(TreeNode* root, int val) 
    {
        if (root == NULL || root->val == val) return NULL;
        if (root->left && root->left->val == val) return root;
        if (root->right && root->right->val == val) return root;
        TreeNode* leftParent = findParent(root->left, val);
        if (leftParent) return leftParent;
        return findParent(root->right, val);
    }
};


int main() 
{
    // 创建一个简单的二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    Tree tree;

    // 先序遍历
    cout << "Pre-order traversal: ";
    tree.preOrderTraversal(root);
    cout << endl;

    // 中序遍历
    cout << "In-order traversal: ";
    tree.inOrderTraversal(root);
    cout << endl;

    // 后序遍历
    cout << "Post-order traversal: ";
    tree.postOrderTraversal(root);
    cout << endl;

    // 层序遍历
    cout << "Level-order traversal: ";
    tree.levelOrderTraversal(root);
    cout << endl;

    // 获取树的深度
    int depth = tree.getDepth(root);
    cout << "Tree depth: " << depth << endl;

    // 计算节点个数
    int count = tree.countNodes(root);
    cout << "Number of nodes: " << count << endl;

    // 查找某个节点的父节点
    int val = 5;
    TreeNode* parent = tree.findParent(root, val);
    if (parent) 
    {
        cout << "Parent of node " << val << " is: " << parent->val << endl;
    }
    else 
    {
        cout << "None" << endl;
    }

    return 0;
}

希望本文章对你有所帮助，也请你点点关注支持一下博主，若有什么问题可在评论区评论，博主会第一时间赶到现场，当然也不要忘了最最重要的 —— 自己试试看吧，你可以做得更好！

标签：最最,遍历,TreeNode,val,C++,right,二叉树,root,left
From： https://blog.csdn.net/Ahjol171/article/details/141883474