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

在这里插入图片描述

初阶数据结构	相关知识点	可以通过点击	以下链接进行学习	一起加油！
时间与空间复杂度的深度剖析	深入解析顺序表:探索底层逻辑	深入解析单链表:探索底层逻辑	深入解析带头双向循环链表:探索底层逻辑	深入解析栈:探索底层逻辑
深入解析队列:探索底层逻辑	深入解析循环队列:探索底层逻辑	树与二叉树：从零开始的奇幻之旅	理解堆的特性与应用：深入探索完全二叉树的独特魅力

本篇将介绍掌握二叉树的遍历和信息获取方法，有助于我们更好地理解树的结构与统计分析，为接下来学习AVL树与红黑树等高阶数据结构打下基础。对于最后面关于二叉树的特性，需要理解掌握在遇到相关题目可以直接套用。

请添加图片描述
Alt

🌈个人主页：是店小二呀
🌈C语言笔记专栏：C语言笔记
🌈C++笔记专栏： C++笔记
🌈初阶数据结构笔记专栏：初阶数据结构笔记

🌈喜欢的诗句:无人扶我青云志我自踏雪至山巅
请添加图片描述

一、快速搭建二叉树

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

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