【二叉树】1-5,理论基础、前中后序遍历的递归法和迭代法、层序遍历

这篇具有很好参考价值的文章主要介绍了【二叉树】1-5,理论基础、前中后序遍历的递归法和迭代法、层序遍历。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1,二叉树的种类

满二叉树

除最后一层无任何子节点外,每一层上的所有结点都有两个子结点的二叉树。
【二叉树】1-5,理论基础、前中后序遍历的递归法和迭代法、层序遍历,代码随想录笔记,数据结构

完全二叉树

一个深度为k的有n个节点的二叉树,对树中的节点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。
【二叉树】1-5,理论基础、前中后序遍历的递归法和迭代法、层序遍历,代码随想录笔记,数据结构

二叉搜索树

二叉搜索树(Binary Search Tree),又名二叉排序树(Binary Sort Tree)。

二叉搜索树是具有有以下性质的二叉树:

若左子树不为空,则左子树上所有节点的值均小于或等于它的根节点的值。
若右子树不为空,则右子树上所有节点的值均大于或等于它的根节点的值。
左、右子树也分别为二叉搜索树。
【二叉树】1-5,理论基础、前中后序遍历的递归法和迭代法、层序遍历,代码随想录笔记,数据结构

平衡二叉搜索树

平衡二叉搜索树的任何结点的左子树和右子树高度最多相差1。,并且左右两个子树都是一棵平衡二叉树。
【二叉树】1-5,理论基础、前中后序遍历的递归法和迭代法、层序遍历,代码随想录笔记,数据结构

容器map、set、multimap、multiset的底层原理都是平衡二叉搜索树
所以map中key和set中的元素都是有序的

unordered map和unordered set的底层原理为哈希表

2,存储方式

分为链式存储和线式存储

链式存储

链式存储方式就用指针
【二叉树】1-5,理论基础、前中后序遍历的递归法和迭代法、层序遍历,代码随想录笔记,数据结构

线式存储

(用的少了解即可)

顺序存储的方式就是用数组。
【二叉树】1-5,理论基础、前中后序遍历的递归法和迭代法、层序遍历,代码随想录笔记,数据结构

线式存储时,有一点i,他的左孩子下标为2i+1,他的右孩子下标为2i+2

3,二叉树的遍历

分为深度优先搜索和广度优先搜索

深度优先搜索

分为前序遍历、中序遍历、后续遍历
【二叉树】1-5,理论基础、前中后序遍历的递归法和迭代法、层序遍历,代码随想录笔记,数据结构
写法可以分为递归法和迭代法

递归的底层原理是栈

确定递归函数的参数和返回值
确定终止条件
确定单层递归的逻辑

迭代法就是模拟递归的过程,因为递归的底层原理为栈,所以迭代法用栈展示

面试简单的可能需要写出简单的非递归代码

前序遍历(递归法、迭代法)

中左右
递归法:

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

迭代法:
因为模拟栈的过程,前序遍历是中左右,但是栈是先进后出的,所以入栈顺序为右左中

访问顺序和处理顺序相同(后续遍历也是如此,所以稍作改动就可以变为后续遍历)

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();                       // 中
            st.pop();
            result.push_back(node->val);
            if (node->right) st.push(node->right);           // 右(空节点不入栈)
            if (node->left) st.push(node->left);             // 左(空节点不入栈)
        }
        return result;
    }
};

中序遍历(递归法、迭代法)

左中右
递归法:

void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    vec.push_back(cur->val);    // 中
    traversal(cur->right, vec); // 右
}

迭代法:
访问顺序和处理顺序不同,所以代码和前后续遍历不同

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) { // 指针来访问节点,访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top(); // 从栈里弹出的数据,就是要处理的数据(放进result数组里的数据)
                st.pop();
                result.push_back(cur->val);     // 中
                cur = cur->right;               // 右
            }
        }
        return result;
    }
};

后序遍历(递归法、迭代法)

左右中
递归法:

void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    traversal(cur->right, vec); // 右
    vec.push_back(cur->val);    // 中
}

迭代法:
访问顺序和处理顺序相同

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            result.push_back(node->val);
            if (node->left) st.push(node->left); // 相对于前序遍历,这更改一下入栈顺序 (空节点不入栈)
            if (node->right) st.push(node->right); // 空节点不入栈
        }
        reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了
        return result;
    }
};

广度优先搜索

层次遍历(迭代法、递归法)

借助一个队列,保存每一层的节点

队列记录当前层的元素个数,弹出时按队列里储存的个数弹出

迭代法:

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            // 这里一定要使用固定大小size,不要使用que.size(),因为que.size是不断变化的
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

递归法:文章来源地址https://www.toymoban.com/news/detail-642411.html

class Solution {
public:
    void order(TreeNode* cur, vector<vector<int>>& result, int depth)
    {
        if (cur == nullptr) return;
        if (result.size() == depth) result.push_back(vector<int>());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth + 1);
        order(cur->right, result, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        int depth = 0;
        order(root, result, depth);
        return result;
    }
};

4,二叉树的定义

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

到了这里,关于【二叉树】1-5,理论基础、前中后序遍历的递归法和迭代法、层序遍历的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构——二叉树线索化遍历(前中后序遍历)

    为什么要转换为线索化         二叉树线索化是一种将普通二叉树转换为具有特殊线索(指向前驱和后继节点)的二叉树的过程。这种线索化的目的是为了提高对二叉树的遍历效率,特别是在不使用递归或栈的情况下进行遍历。         将二叉树线索化的主要目的是为了

    2024年02月09日
    浏览(40)
  • ( “树” 之 前中后序遍历) 145. 二叉树的后序遍历 ——【Leetcode每日一题】

    层次遍历顺序:[1 2 3 4 5 6] 前序遍历顺序:[1 2 4 5 3 6] 中序遍历顺序:[4 2 5 1 3 6] 后序遍历顺序:[4 5 2 6 3 1] 层次遍历使用 BFS 实现,利用的就是 BFS 一层一层遍历的特性;而前序、中序、后序遍历利用了 DFS 实现。 前序、中序、后序遍只是在对节点访问的顺序有一点不同,其它

    2023年04月20日
    浏览(37)
  • 【数据结构】二叉树的前中后序遍历(C语言)

    [二叉树] 顾名思义就是有 两个分支节点的树,不仅如此,除了叶子外的所有节点都具有两个分支节点; 由于结构像一棵倒立的树,顾名思义为二叉树 ; 如下图所示,该图即为一棵 野生的二叉树 ; 既然二叉树为树,固然有着和树一样的部分( 叶子、根、分支… ) 这些也成为

    2024年02月17日
    浏览(45)
  • 数据结构 | 二叉树的概念及前中后序遍历

    下面内容来自百度百科 二叉树(Binary tree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。二叉树特点是每个节点最多只能

    2024年02月05日
    浏览(37)
  • C++ 二叉树(建立、销毁、前中后序遍历和层次遍历,寻找双亲结点等)

    (1) 结构体和类定义 (2)创建二叉树 (3)前中后序遍历和层序遍历 (4)复制二叉树 (5)销毁二叉树 (6)析构函数 (7)求树的高度 (8)获取结点,判断其是否在二叉树中 (9)计算结点个数和获取结点个数 (10)二叉树判空 (11)获取根结点 源代码: btree.h btree.cp

    2024年02月13日
    浏览(39)
  • 【数据结构】二叉树的·深度优先遍历(前中后序遍历)and·广度优先(层序遍历)

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 :阿然成长日记 👈点击可跳转 📆 个人专栏: 🔹数据结构与算法🔹C语言进阶 🚩 不能则学,不知则问,耻于问人,决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 (1) 先序遍历 的过

    2024年01月24日
    浏览(45)
  • (“树” 之 前中后序遍历 ) 94. 二叉树的中序遍历 ——【Leetcode每日一题】

    层次遍历顺序:[1 2 3 4 5 6] 前序遍历顺序:[1 2 4 5 3 6] 中序遍历顺序:[4 2 5 1 3 6] 后序遍历顺序:[4 5 2 6 3 1] 层次遍历使用 BFS 实现,利用的就是 BFS 一层一层遍历的特性;而前序、中序、后序遍历利用了 DFS 实现。 前序、中序、后序遍只是在对节点访问的顺序有一点不同,其它

    2023年04月23日
    浏览(49)
  • 二叉树(下)+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”

    各位CSDN的uu们你们好呀,今天小雅兰的内容仍然是二叉树和Leetcode每日一题,下面,就让我们进入二叉树的世界吧!!! 这个题目需要重新定义一个函数,函数参数需要有左子树和右子树,题目所给定的函数无法解决问题。 每个不为空的结点,都可以认为是一棵子树的根 

    2024年02月16日
    浏览(46)
  • 【数据结构】前中后层序遍历 --二叉树的结构特点与遍历方式

      Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法......感兴趣就关注我吧!你定不会失望。 🌈个人主页:主页链接 🌈算法专栏:专栏链接       我会一直往里填充内容哒! 🌈LeetCode专栏:专栏链接       目前在刷初级算法的LeetBook 。若每日一题当中有力所能

    2023年04月09日
    浏览(85)
  • 数据结构——二叉树的先中后序遍历

    ——本节内容为Bilibili王道考研《数据结构》P43~P45视频内容笔记。 目录 一、二叉树的先中后序遍历 1.先中后序遍历 2.举例  3.先中后序遍历和前中后缀的关系 4.代码实现 5.求遍历序列 6.应用:求树的深度 二、二叉树的层次遍历 1.层次遍历 2.算法思想: 3.算法演示: 4.代码实

    2024年02月12日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包