国外做游戏的视频网站有哪些,网站页面设计制作,网站开发前段和后端,做窗帘网站个人主页#xff1a;C忠实粉丝 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 C忠实粉丝 原创 数据结构之二叉树的超详细讲解(3)--(二叉树的遍历和操作) 收录于专栏【数据结构初阶】 本专栏旨在分享学习数据结构学习的一点学习笔记#xff0c;欢迎大家在评… 个人主页C忠实粉丝 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 C忠实粉丝 原创 数据结构之二叉树的超详细讲解(3)--(二叉树的遍历和操作) 收录于专栏【数据结构初阶】 本专栏旨在分享学习数据结构学习的一点学习笔记欢迎大家在评论区交流讨论 目录 1.前置说明
2.二叉树的遍历
2.1 前序、中序以及后序遍历
代码实现:
2.1.1前序遍历: 2.1.2中序遍历:
2.1.3后序遍历:
力扣oj练习
2.2 层序遍历
代码实现:
练习
3.结点个数以及高度等
3.1二叉树节点个数
3.2二叉树叶子节点个数
3.3二叉树第k层节点个数
3.4二叉树查找值为x的节点
3.5二叉树的高度
4.二叉树的创建和销毁
4.1通过前序遍历的数组ABD##E#H##CF##G##构建二叉树
4.2二叉树销毁
4.3判断二叉树是否时完全二叉树 1.前置说明
如果没看树和二叉树的结构和概念建议先去看看
----数据结构之二叉树的超详细讲解(1)--(树和二叉树的概念和结构)-CSDN博客
---数据结构之二叉树的超详细讲解(2)--(堆的概念和结构的实现,堆排序和堆排序的应用)-CSDN博客 在学习二叉树的基本操作前需先要创建一棵二叉树然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入为了降低大家学习成本此处手动快速创建一棵简单的二叉树快速进入二叉树 操作学习等二叉树结构了解的差不多时我们反过头再来研究二叉树真正的创建方式。 二叉树的结构表示:
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;手动创造一棵树:
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);BTNode* node7 BuyNode(7);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;node5-right node7;return node1;
} 将创造树节点的方法封装成一个函数(BuyNode):
BTNode* BuyNode(int x)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));if (node NULL){perror(malloc fail);return NULL;}node-data x;node-left NULL;node-right NULL;return node;
}
这样我们就完成了一棵树的创建,如下图所示: 注意上述代码并不是创建二叉树的方式真正创建二叉树方式后序详解重点讲解。 再看二叉树基本操作前再回顾下二叉树的概念二叉树是 1. 空树 2. 非空根结点根结点的左子树、根结点的右子树组成的。 从概念中可以看出二叉树定义是递归式的因此后序基本操作中基本都是按照该概念实现的。 2.二叉树的遍历
2.1 前序、中序以及后序遍历
学习二叉树结构最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则依次对二叉树中的结点进行相应的操作并且每个结点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一也是二叉树上进行其它运算的基础。 按照规则二叉树的遍历有前序/中序/后序的递归结构遍历 1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。 2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中间。 3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。 由于被访问的结点必是某子树的根所以N(Node、L(Left subtree和R(Right subtree又可解释为 根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
示例:
假如我们的二叉树为: 前序遍历: 前序遍历即访问根结点的操作发生在遍历其左右子树之前。也就是先访问根节点在访问左右子树,简称为根左右 所以前序遍历为: 1 2 3 NULL NULL NULL 4 5 NULL 6 NULL NULL 中序遍历: 中序遍历即访问左节点的操作发生在遍历其根节点和右节点之前,也就是先访问左节点在访问根右,简称左根右 所以中序遍历为:NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL 后序遍历: 后序遍历即先访问左节点,在访问右节点和根节点,简称左右根 所以后序遍历为:NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1 代码实现:
我们之前已经手动创建了一棵树: 2.1.1前序遍历:
void PrevOrder(BTNode* root)
{if (root NULL){printf(N );return;}printf(%d , root-data);PrevOrder(root-left);PrevOrder(root-right);
} 我们这里的逻辑为:首先判断节点是否为空,为空即返回NULL(这里N就代表为NULL),并return,注意:这里的return并不是直接退出,而是返回函数上一层,不为空即直接打印节点data值,然后递归左右子树,满足根左右的性质. 结果如下: 递归展开图: 这里怕宝子们还是不理解递归的原理,这里就展示前序的递归展开图,中序和后序是一样的 由于篇幅有限,没有完全展示,但是原理都是一样的 2.1.2中序遍历:
void InOrder(BTNode* root)
{if (root NULL){printf(N );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
} 我们这里的逻辑和前序方法差不多,也是使用递归,满足左根右的性质进行后序遍历 结果如下: 2.1.3后序遍历:
void postorder(BTNode* root)
{if (root NULL){printf(N );return;}postorder(root-left);postorder(root-right);printf(%d , root-data);
}
结果如下: 力扣oj练习
--144. 二叉树的前序遍历 - 力扣LeetCode
--94. 二叉树的中序遍历 - 力扣LeetCode
--145. 二叉树的后序遍历 - 力扣LeetCode 只要能把上面的知识看懂弄明白,这三个题目能很轻松的做出来.大家去看二叉树经典OJ练习-CSDN博客,里面进行了详细的讲解. 2.2 层序遍历 层序遍历除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。设二叉树的根结点所在 层数为1层序遍历就是从所在二叉树的根结点出发首先访问第一层的树根结点然后从左到右访问第2层 上的结点接着是第三层的结点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。 上图层序遍历的结果为:A B C D E F G H I 代码实现:
void TreeLevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);printf(%d , front-data);if (front-left)QueuePush(q, front-left);if (front-right)QueuePush(q, front-right);}QueueDestroy(q);
} 具体步骤 初始化队列 初始化一个队列并将根节点入队。如果根节点为空则直接跳过。 层序遍历 使用队列进行层序遍历。每次取出队列中的节点打印节点的值并将该节点的左右子节点分别入队。 清理资源 销毁队列释放资源。 这里需要用到队列的知识,使其能一层一层的遍历二叉树,对队列还不清楚的宝子们,可以看看下面的博客--数据结构之队列的超详细讲解-CSDN博客
练习
1.某完全二叉树按层次输出同一层从左到右的序列为 ABCDEFGH 。该完全二叉树的前序序列为A A ABDHECFG B ABCDEFGH C HDBEAFCG D HDEBFGCA 2.二叉树的先序遍历和中序遍历如下先序遍历EFHIGJK; 中序遍历HFIEJKG.则二叉树根结点为A A E B F C G D H 3.设一课二叉树的中序遍历序列badce后序遍历序列bdeca则二叉树前序遍历序列为__D__。 A adbce B decab C debac D abcde 4.某二叉树的后序遍历序列与中序遍历序列相同均为 ABCDEF 则按层次输出同一层从左到右的序列A A FEDCBA B CBAFED C DEFCBA D ABCDEF 解答: 1. 完全二叉树按层次输出的序列为 ABCDEFGH 该完全二叉树的前序序列为A 根据完全二叉树的定义给出的层次遍历序列 ABCDEFGH 可以直接构建出二叉树其中 根节点是 A第二层是 B 和 C第三层是 D, E, F, G第四层是 H 从这个结构我们可以推导前序遍历 前序遍历是根 - 左子树 - 右子树根是 A左子树的前序遍历是 B - D - H - E右子树的前序遍历是 C - F - G 因此前序遍历是ABDHECFG 答案是 AABDHECFG 2. 二叉树的先序遍历和中序遍历如下 先序遍历EFHIGJK; 中序遍历HFIEJKG 从先序遍历可以看出根结点是 E。根据中序遍历E 左边的部分是左子树右边的部分是右子树 中序遍历分割为: 左子树 HFI 和右子树 EJKG按照先序遍历的顺序E 后面的字符分别属于左子树和右子树 左子树的先序遍历是 FHI右子树的先序遍历是 JKG 所以根结点是 E。 答案是 AE 3. 二叉树的中序遍历序列badce后序遍历序列bdeca 从后序遍历可以看出根结点是 a。根据中序遍历a 左边的是左子树右边的是右子树 中序遍历分割为: 左子树 b 和右子树 dce后序遍历的顺序左子树的顺序是 b右子树的顺序是 dec 前序遍历是根 - 左子树 - 右子树abcde 答案是 Dabcde 4. 二叉树的后序遍历序列与中序遍历序列相同均为 ABCDEF 这意味着每个节点只有一个子节点并且这些节点按顺序排列如果它们按层次输出那么最深的节点将排在最后。 如果后序遍历和中序遍历相同 最右边的节点即最后一个节点是树的根节点其余节点依次按照层次遍历的顺序向左添加 按层次遍历从根开始从层次的最右边开始因此应该是 F - E - D - C - B - A 答案是 AFEDCBA 3.结点个数以及高度等
3.1二叉树节点个数
这里大家很容易写出错误代码,比如:
int TreeSize(BTNode* root)
{int size 0;if (root NULL)return 0;elsesize;TreeSize(root-left);TreeSize(root-right);return size;
} 这段代码看起来非常好理解,相当于进行了一次前序遍历,将遍历的节点进行返回. 在这个函数中size 是一个局部变量每次调用 TreeSize 时都会重新初始化为 0。让我们逐步分析一下这个函数的行为。
分析: 当 root NULL 时函数直接返回 0。这是树为空的情况。 如果 root 不为 NULL int size 0; 初始化 size 为 0。size; 将 size 增加 1所以 size 现在为 1。 然后递归调用 TreeSize(root-left) 和 TreeSize(root-right)但是这些调用的返回值并没有被使用或累加到 size 上。 因此无论左右子树中有多少节点这些递归调用的结果都不会影响当前函数中的 size 变量。每次递归调用都会在自己的栈帧中初始化一个新的 size 变量并且最终返回 1 或 0。
函数递归展开图: 用static进行改进:
int TreeSize(BTNode* root)
{static int size 0;if (root NULL)return 0;elsesize;TreeSize(root-left);TreeSize(root-right);return size;
} static 变量在整个程序运行期间只会被初始化一次,这样就避免了局部变量一直的初始化 结果如下: 结果是没有问题的,可是当我们多次调用呢?
这里我重复调用三次: 结果如下: 正是因为 static 变量在整个程序运行期间只会被初始化一次,所以如果你多次用 TreeSize 函数size 会一直累积之前的计算结果而不会重新开始计算新的树的大小。 正确代码:
int TreeSize(BTNode* root)
{return root NULL ? 0 :TreeSize(root-left) TreeSize(root-right) 1;
} 为了修正这些问题可以将递归调用的结果累加到 size 中并将最终的 size 值作为函数的返回值。 函数递归展开图: 这段代码利用递归的方式计算二叉树的节点总数通过递归遍历所有节点实现了对整个二叉树的全面统计。递归的基准情况是遇到空节点返回 0而在非空节点情况下递归地计算左右子树的大小并进行累加从而获得整棵树的节点总数。 3.2二叉树叶子节点个数
补充一下什么是叶子节点:
没有子树的节点叫做叶子节点,也称度为0的节点
代码展示:
int TreeLeafSize(BTNode* root)
{if (root NULL)return 0;if (root-left NULL root-right NULL)return 1;return TreeLeafSize(root-left) TreeLeafSize(root-right);
} 分析 基准情况 如果 root 为 NULL则树为空没有叶节点。因此返回 0。 叶节点情况 如果 root 的左子节点和右子节点都为 NULL那么当前节点为叶节点。因此返回 1。 递归情况 如果当前节点不是叶节点则递归计算其左、右子树中的叶节点数量并将它们加起来。通过递归调用 TreeLeafSize(root-left) 和 TreeLeafSize(root-right) 来分别计算左、右子树中的叶节点数量并将结果相加。 递归展开图: 结果如下: 结果为3,没有问题
3.3二叉树第k层节点个数
代码展示:
int TreeLevelKSize(BTNode* root, int k)
{if (root NULL)return 0;if (k 1)return 1;// 子问题return TreeLevelKSize(root-left, k - 1) TreeLevelKSize(root-right, k - 1);
} 函数递归展开图: 分析 基础情况处理 if (root NULL) return 0;如果当前节点 root 为空则返回 0。这是递归的终止条件之一表示空节点没有子节点因此在任何层级上都没有节点。 if (k 1) return 1;当 k 等于 1 时表示已经递归到目标层级。根据题设每个节点自身被视为一个层级因此返回 1。 递归调用 return TreeLevelKSize(root-left, k - 1) TreeLevelKSize(root-right, k - 1);如果当前节点 root 不为空且 k 1则递归调用 TreeLevelKSize 函数来计算左子树和右子树中第 k-1 层级的节点数目。最终返回的是左子树第 k-1 层级节点数目和右子树第 k-1 层级节点数目的和。 3.4二叉树查找值为x的节点
代码展示:
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-data x)return root;BTNode* ret1 TreeFind(root-left, x);if (ret1)return ret1;BTNode* ret2 TreeFind(root-right, x);if (ret2)return ret2;return NULL;
}
函数递归展开图: 分析 基础情况处理 if (root NULL) return NULL;如果当前节点 root 为空则直接返回 NULL表示未找到目标节点。 if (root-data x) return root;如果当前节点的值等于 x则返回当前节点 root表示已找到目标节点。 递归查找 BTNode* ret1 TreeFind(root-left, x); 递归在左子树中查找值为 x 的节点。如果找到了即 ret1 不为 NULL直接返回 ret1。 BTNode* ret2 TreeFind(root-right, x); 如果左子树中未找到目标节点继续递归在右子树中查找值为 x 的节点。如果找到了即 ret2 不为 NULL直接返回 ret2。 返回结果 如果在当前节点及其左右子树中都未找到值为 x 的节点则返回 NULL表示整棵树中没有该节点。 3.5二叉树的高度
代码一:
int TreeHeight(BTNode* root)
{if (root NULL)return 0;return TreeHeight(root-left) TreeHeight(root-right) ?TreeHeight(root-left) 1 : TreeHeight(root-right) 1;
} 分析 基准情况 如果 root 为 NULL则树为空高度为 0。因此返回 0。 递归情况 如果当前节点不为空则递归计算其左、右子树的高度并返回较大的那个值加上 1。通过递归调用 TreeHeight(root-left) 和 TreeHeight(root-right) 来分别计算左、右子树的高度。使用条件运算符 ? : 来比较左、右子树的高度并将较大的那个值加上 1 返回。 这个解法是没有问题的,但是它的时间效率不高,它在递归过程中有的值会重复计算多次
函数递归展开图: 我们可以看到,我们每次计算出左右子树的高度后,并不会进行记录,导致我们比较完成后还需要进行递归计算,导致效率不高 代码二:
int TreeHeight(BTNode* root)
{if (root NULL)return 0;int leftHeight TreeHeight(root-left);int rightHeight TreeHeight(root-right);return leftHeight rightHeight ?leftHeight 1 : rightHeight 1;
} 函数递归展开图: 可以发现我们用两个变量存储之后,每次我们都只需要一次,避免了重复计算,提高了时间效率 这里大家可以试一试,在力扣上面右一道计a算二叉树的深度,如果你使用第一种代码,只通过了35个例子,超时了,因为后面的例子数据庞大,如果你使用第一种方案,最低层的值会被重复计算很多次,导致超出时间限制 而我们用第二种方法,能很顺利的通过 下面是原题链接:
--LCR 175. 计算二叉树的深度 - 力扣LeetCode
4.二叉树的创建和销毁
4.1通过前序遍历的数组ABD##E#H##CF##G##构建二叉树
代码展示:
BTNode* CreateTree(char* a, int* pi)
{if (a[*pi] #){(*pi);return NULL;}BTNode* root (BTNode*)malloc(sizeof(BTNode));root-data a[(*pi)];root-left CreateTree(a, pi);root-right CreateTree(a, pi);return root;
}
函数递归展开图: 函数分析 参数 char* a存储先序遍历序列的字符数组包含节点的数据和 # 表示的空节点。int* pi指向当前处理的字符在数组 a 中的索引的指针。 返回值 BTNode*返回值是指向根节点 BTNode 结构体的指针。 递归过程 如果当前字符是 #表示遇到空节点函数会返回 NULL并且将指针 pi 向后移动一位。如果当前字符不是 #则创建一个新的节点将当前字符作为节点的数据并将指针 pi 向后移动一位。然后递归调用 CreateTree 函数来构建左子树和右子树分别将它们赋给当前节点的 left 和 right 指针。 返回根节点 最后返回根节点的指针。 4.2二叉树销毁
代码展示:
// 二叉树销毁
void TreeDestory(BTNode* root)
{if (root NULL)return;TreeDestory(root-left);TreeDestory(root-right);free(root);
}
函数递归展开图: 函数分析 检查根节点是否为空 如果传入的根节点 root 为 NULL说明树为空或者已经到达叶子节点的子节点即空节点直接返回不进行任何操作。 递归销毁左子树 调用 TreeDestory(root-left) 递归地销毁左子树。此调用会一直递归到最左子节点然后逐级返回并销毁每个节点。 递归销毁右子树 调用 TreeDestory(root-right) 递归地销毁右子树。此调用会一直递归到最右子节点然后逐级返回并销毁每个节点。 释放当前节点的内存 在左右子树都被销毁后最后释放当前节点的内存 free(root)。 4.3判断二叉树是否时完全二叉树
代码展示:
// 判断二叉树是否是完全二叉树
bool TreeComplete(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);// 遇到第一个空就可以开始判断如果队列中还有非空就不是完全二叉树if (front NULL){break;}QueuePush(q, front-left);QueuePush(q, front-right);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);// 如果有非空就不是完全二叉树if (front){QueueDestroy(q);return false;}}QueueDestroy(q);return true;
} 具体步骤 初始化队列 初始化一个队列并将根节点入队。如果根节点为空则直接跳过。 层序遍历 使用队列进行层序遍历。每次取出队列中的节点如果遇到空节点NULL则退出该循环。否则将该节点的左右子节点分别入队。 检测后续节点 继续检查队列中剩余的节点。如果存在非空节点则树不是完全二叉树返回 false。否则继续检查直到队列为空。 清理与返回 销毁队列释放资源并返回 true 表示该二叉树是完全二叉树。
