【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析

本文涉及的产品
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
简介: 【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析

一、快速搭建二叉树

为了方便我们更快地学习二叉的基本操作,这里直接手动搭建一颗二叉树。不仅如此,在做二叉树相关题目时,由于部分原因做题平台不支持普通用户使用调试功能,可以快速搭建二叉树在本地编译器上进行调试相关操作

typedef int BTDataType;
typedef struct BinaryTreeNode
{
    BTDataType _data;
    struct BinaryTreeNode* _left;
    struct BinaryTreeNode* _right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
    BTNode* tmp = (BTNode*)malloc(sizeof(BTNode));
    if (tmp == NULL)
    {
        // 处理内存分配失败的情况
        // 可以选择报错、退出程序或者其他适当的处理方式
        exit(EXIT_FAILURE)
    };  // 举例:退出程序
    
    tmp->_data = x;
    tmp->_left = NULL;
    tmp->_right = NULL;
    return tmp;
}
BTNode* CreatBinaryTree()
{
    BTNode* node1 = BuyNode(1);
    BTNode* node2 = BuyNode(2);
    BTNode* node3 = BuyNode(3);
    BTNode* node4 = BuyNode(4);
    BTNode* node5 = BuyNode(5);
    BTNode* node6 = BuyNode(6);
    node1->_left = node2;
    node1->_right = node4;
    node2->_left = node3;
    node4->_left = node5;
    node4->_right = node6;
    return node1;
}

二、二叉树组成结构

二叉树大致分为两种

  • 空树
  • 非空:根节点,的左子树,右子树(左右子树可能为空树)

从概念中可以看出来,根据不同节点可以划分多个子树,对此二叉树定义是递归式的,因此后续基本操作都是按照概念实现的。

三、二叉树的遍历

学习二叉树的结构,最简单的方式就是遍历,遍历是二叉树上最重要的运算之一,也是二叉树上进行其他运算的基础。二叉树遍历按照某种特定的规则,依次对二叉树中的节点进行对应的操作,并且每个节点只操作一次。

3.1 三种常见遍历(前序/中序/后序遍历)

根据规定,访问顺序左子树是先于右子树,导致了二叉树遍历有三种递归式结构前序/中序/后序的遍历,被访问节点必是某子树的根。根据英文缩写可以通过N、L、R表示根、左子树、右子树,对此NLR、LNR和LRN称为先根遍历、中根遍历和后根遍历。

根据例子更好的理解其中的含义,不然很难get到其中的真谛。尝试下前序/中序/后序,写出访问顺序(空也会访问,用N代表)

前序:123NNN45NN6NN

中序:N3N2N1N5N4N6N

后序:NN3N2NN5NN641

过程解析:

达到1号节点为根,访问左子树;达到2号节点为根;访问左子树;达到3号节点为根;访问左子树;达到为空位置返回,访问根(3号),访问右子树;达到空位置,以3号为根子树访问完;以2号为根左子树访问完,访问根(2号);以此类推直到遍历完毕(按照这种方式,剩下两种遍历也是很好掌握的)

3.2 层序遍历

除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历

void LevelOrder(BTNode* root)
{
    // 0. 声明队列
    queue<TreeNode*> q;
    // 1. 将根节点加入队列
    q.push(root);
    // 2. 遍历队列中每个节点
    while (!q.empty()) 
    {
        TreeNode* cur = q.front();
        q.pop();
        // 3. 记录当前节点值
        vec.push(cur->val);
        // 4. 将左右孩子放入队列
        q.push(cur->left);
        q.push(cur->right);
    }
}

这里使用C++语法直接调用库里面的queue容器,直接主要是分享思路,语法看不懂没有关系。

使用场景:判断是否为完全二叉树(C++代码)。

// 判断是否为完全二叉树
bool isCompleteTree(TreeNode* root) {
    if (root == nullptr) {
        return true;
    }
    
    queue<TreeNode*> q;
    q.push(root);
    bool foundNull = false;
    
    while (!q.empty()) {
        TreeNode* currentNode = q.front();
        q.pop();
        
        if (currentNode == nullptr) {
            foundNull = true;
        } else {
            if (foundNull) {
                return false;
            }
            q.push(currentNode->left);
            q.push(currentNode->right);
        }
    }
    
    return true;
}

大致思路:完全二叉树特性是从左到右是连续的,该特性保证了最后一个位置为空,那么判断是否为完全二叉树只需要在遇到空节点之后不会再出现非空节点即可。可以使用层序遍历(层序遍历也是适用于普通二叉树)如果队列出空,但是队列不为空说明不是完全二叉树.。

四、求二叉树相关信息

4.1 二叉树节点个数

瑕疵版本:使用静态局部变量进行计数

int TreeSize(TreeNode* root)
{
  static int size = 0;
  if (root == NULL)
  {
    return 0;
  }
  ++size;
  TreeSize(root->left);
  TreeSize(root->right);
  return size;
}

瑕疵版本:使用全局变量进行计数

int size = 0;
void TreeSize(TreeNode* root)
{
  if (root == NULL)
    return;
  ++size;
  TreeSize(root->left);
  TreeSize(root->right);
}

方法分析:无论是使用静态还是全局变量,使得生命周期不会受到函数栈帧销毁的影响,可以解决求节点个数的问题。问题在于静态还是全局变量只能被定义一次,这就意味着第一次计算出来的结果是正确的,那么第二次的结果会延用上一次变量存储的值,不会清空重新计数,程序结束(以上一次值为基准)导致结果错误。

修正版本:画图分析

int BinaryTreeSize(TreeNode* root)
{
    if (root == NULL) return 0;
    return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

过程解析:这里使用分治思想,可以将求整课树节点个数分为求左右子树节点个数加上根节点之和,不断划分,去看最几步过程去递推和归并去发现规律。比如:以3为根节点,得到左右子树为空返回结果为0,返回给2节点的结果就是0 + 0 + 1(1为根节点)返回结果为:以2为根节点左子树的节点个数BinaryTreeSize(root->left)等于BinaryTreeSize(root->left-left) + BinaryTreeSize(root->left->right) + 1(如果觉得这样子很难理解,建议画图去研究递归的过程)。

4.2 二叉树叶子节点个数

int BinaryTreeLeafSize(TreeNode* root)
{
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL) return 1;
    return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

过程解析这里也是使用了分治的思想,求整棵树叶子节点个数之和分为求左右子树叶子节点个数之后。根据题目要求访问三种情况:空节点返回0,不是空节点,属于叶子节点返回1,不是空节点也不是叶子节点,使用分治等于左右子树叶子之后。

4.3 求这个棵树的高度

过程解析这里也是使用了分治的思想,求整棵树高度分为求左右子树高度之间最大的高度再+1

瑕疵版本

int TreeHeight(TreeNode* root)
{
  if (root == NULL) return 0;
  
  return TreeHeight(root->left) > TreeHeight(root->right) ?
    TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1;
}

由于TreeHeight(root->left) > TreeHeight(root->right) 的比较是不会记录结果,需要高的那一份再次递归调用,因此多次递归调用 TreeHeight(root->left)TreeHeight(root->right),造成重复计算。

修正版本:(记录得到目前高度进行比较)

int TreeHeight(TreeNode* root) 
{
  if (root == NULL) return 0;
  int leftHeight = TreeHeight(root->left);
  int rightHeight = TreeHeight(root->right);
  return max(leftHeight, rightHeight) + 1;
}

4.4 二叉树第k层节点个数

int TreeLevelK(TreeNode* root, int k)
{
  assert(k > 0);
  if (root == NULL)
    return 0;
  if (k == 1)
    return 1;
  return TreeLevelK(root->left, k-1)
    + TreeLevelK(root->right, k-1);
}

过程解析:跟求整棵树节点个数问题是差不多,主要差异在于对于范围的限制,无非添加一个变量(临时变量)进行递归,每一层的k值是不同的,到达一定条件停止返回如果为空返回0,如果为非空返回1,都建立在k>0的前提下。

4.5 二叉树查找值为x的节点

瑕疵版本:

TreeNode* TreeFind(TreeNode* root, BTDataType x)
{
  if (root == NULL) return NULL;
  if (root->data == x) return root;
  TreeFind(root->left, x);
  TreeFind(root->right, x);
    
  return NULL;
}

过程解析:return 是return 上一层的,不是直接到最外层的。这里导致了没有接受到返回值传出。

修正版本

TreeNode* TreeFind(TreeNode* root, BTDataType x)
{
  if (root == NULL) return NULL;
  if (root->data == x) return root;
  TreeNode* ret1 = TreeFind(root->left, x);
  if (ret1) return ret1;
  TreeNode* ret2 =  TreeFind(root->right, x);
  if (ret2) return ret2;
  return NULL;
}

4.5 单值二叉树

bool isUnivalTree(TreeNode* root)
{
    if(root == NULL) return true;
    if(root->left && root->left->val != root->val)
        return false;
    if(root->right && root->right->val != root->val)
        return false;
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

4.6 相同的树

bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{
    //都为空
    if(p == NULL && q == NULL) return true;
    //其中一个为空(前面排除了都为空的情况)
    if(p == NULL || q == NULL) return false;
    //都不为空且不相等
    if(p->val != q->val) return false;
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

4.7 树的销毁(后序)

五、二叉树的性质

二叉树的性质

  1. 若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2(i-1)个结点
  2. 若规定根节点的层数为1,则深度为h的二叉树的最大结点数是2h-1
  3. 若规定根节点的层数为1,具有n个结点的满二叉树的深度,h= log2(n + 1)(ps: 是log以2为底,n+1为对数)
  4. 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为n2,则有 n0 = n2 + 1




相关文章
|
9天前
|
自然语言处理 数据可视化 前端开发
从数据提取到管理:合合信息的智能文档处理全方位解析【合合信息智能文档处理百宝箱】
合合信息的智能文档处理“百宝箱”涵盖文档解析、向量化模型、测评工具等,解决了复杂文档解析、大模型问答幻觉、文档解析效果评估、知识库搭建、多语言文档翻译等问题。通过可视化解析工具 TextIn ParseX、向量化模型 acge-embedding 和文档解析测评工具 markdown_tester,百宝箱提升了文档处理的效率和精确度,适用于多种文档格式和语言环境,助力企业实现高效的信息管理和业务支持。
3920 2
从数据提取到管理:合合信息的智能文档处理全方位解析【合合信息智能文档处理百宝箱】
|
2天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
31 16
|
1天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
20 4
|
7天前
|
存储 消息中间件 NoSQL
Redis数据结构:List类型全面解析
Redis数据结构——List类型全面解析:存储多个有序的字符串,列表中每个字符串成为元素 Eelement,最多可以存储 2^32-1 个元素。可对列表两端插入(push)和弹出(pop)、获取指定范围的元素列表等,常见命令。 底层数据结构:3.2版本之前,底层采用**压缩链表ZipList**和**双向链表LinkedList**;3.2版本之后,底层数据结构为**快速链表QuickList** 列表是一种比较灵活的数据结构,可以充当栈、队列、阻塞队列,在实际开发中有很多应用场景。
|
18天前
|
人工智能 前端开发 JavaScript
拿下奇怪的前端报错(一):报错信息是一个看不懂的数字数组Buffer(475) [Uint8Array],让AI大模型帮忙解析
本文介绍了前端开发中遇到的奇怪报错问题,特别是当错误信息不明确时的处理方法。作者分享了自己通过还原代码、试错等方式解决问题的经验,并以一个Vue3+TypeScript项目的构建失败为例,详细解析了如何从错误信息中定位问题,最终通过解读错误信息中的ASCII码找到了具体的错误文件。文章强调了基础知识的重要性,并鼓励读者遇到类似问题时不要慌张,耐心分析。
|
24天前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
16 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
6天前
|
存储 NoSQL 关系型数据库
Redis的ZSet底层数据结构,ZSet类型全面解析
Redis的ZSet底层数据结构,ZSet类型全面解析;应用场景、底层结构、常用命令;压缩列表ZipList、跳表SkipList;B+树与跳表对比,MySQL为什么使用B+树;ZSet为什么用跳表,而不是B+树、红黑树、二叉树
|
22天前
|
Java C++
【数据结构】探索红黑树的奥秘:自平衡原理图解及与二叉查找树的比较
本文深入解析红黑树的自平衡原理,介绍其五大原则,并通过图解和代码示例展示其内部机制。同时,对比红黑树与二叉查找树的性能差异,帮助读者更好地理解这两种数据结构的特点和应用场景。
23 0
|
24天前
探索顺序结构:栈的实现方式
探索顺序结构:栈的实现方式

推荐镜像

更多