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

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

一、快速搭建二叉树

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

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




相关文章
|
6月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
149 3
 算法系列之数据结构-Huffman树
|
6月前
|
存储 自然语言处理 数据库
【数据结构进阶】AVL树深度剖析 + 实现(附源码)
在深入探讨了AVL树的原理和实现后,我们不难发现,这种数据结构不仅优雅地解决了传统二叉搜索树可能面临的性能退化问题,还通过其独特的平衡机制,确保了在任何情况下都能提供稳定且高效的查找、插入和删除操作。
485 19
|
7月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》图、查找、排序专题考点(含解析)
408考研——《数据结构》图,查找和排序专题考点选择题汇总(含解析)。
280 29
|
7月前
|
存储 机器学习/深度学习 人工智能
C 408—《数据结构》易错考点200题(含解析)
408考研——《数据结构》精选易错考点200题(含解析)。
472 27
|
8月前
|
存储 C++
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
188 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
8月前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
179 12
|
8月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
162 10
|
8月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
257 3
|
10月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
268 5
|
8月前
|
数据采集 存储 算法
【C++数据结构——图】图的遍历(头歌教学实验平台习题) 【合集】
本文介绍了图的遍历算法,包括深度优先遍历(DFS)和广度优先遍历(BFS)。深度优先遍历通过递归方式从起始节点深入探索图,适用于寻找路径、拓扑排序等场景;广度优先遍历则按层次逐层访问节点,适合无权图最短路径和网络爬虫等应用。文中提供了C++代码示例,演示了如何实现这两种遍历方法,并附有测试用例及结果,帮助读者理解和实践图的遍历算法。
315 0

热门文章

最新文章