网站系统名称是什么title:网站建设公司实力

网站系统名称是什么,title:网站建设公司实力,vi设计公司平台哪个好,商丘做网站公司新站seo快速收录网页内容页的方法#x1f3e0; 个人主页: EXtreme35 #x1f4da; 个人专栏: 专栏名称专栏主题简述《C语言》C语言基础、语法解析与实战应用《数据结构》线性表、树、图等核心数据结构详解《题解思维》算法思路、解题技巧与高效编程实践目录二叉树全栈进阶指南#xff1a;从内存布局到递归… 个人主页:EXtreme35 个人专栏:专栏名称专栏主题简述《C语言》C语言基础、语法解析与实战应用《数据结构》线性表、树、图等核心数据结构详解《题解思维》算法思路、解题技巧与高效编程实践目录二叉树全栈进阶指南从内存布局到递归本质的深度复盘一、二叉树的底层逻辑与核心概念1.1 核心定义与特点1.2 二叉树的五种基本形态1.3 特殊二叉树1.4 二叉树的五条性质1.5 存储结构二、遍历的递归之美2.1 前序遍历2.2 中序遍历 (In-order Traversal)2.3 后序遍历 (Post-order Traversal)2.4 层序遍历三、经典 OJ 题解析3.1 求二叉树的高度3.2 求节点个数3.3 判断两个二叉树是否相同四、递归的代价与内存风险五、 总结二叉树全栈进阶指南从内存布局到递归本质的深度复盘一、二叉树的底层逻辑与核心概念二叉树是一种重要的数据结构它具有一些独特的性质这些性质在算法设计和数据结构的优化中非常有用。以下是二叉树的一些基本性质1.1 核心定义与特点节点Node二叉树的最小单元。通常定义为一个结构体包含数据域和两个指针域。深度Depth与高度Height深度是从根节点自顶向下看根为1。高度是从叶子节点自底向上看。公式推导在一棵高度为h hh的二叉树中最多有2 h − 1 2^h - 12h−1个节点。每个结点最多有两棵子树所以二叉树中不存在度大于 2 的结点。注意不是只有两棵子树而是最多有。没有子树或者有一棵子树都是可以的。左子树和右子树是有顺序的次序不能任意颠倒。就像人有双手、双脚但显然左手、左脚和右手、右脚是不一样的右手戴左手套、右脚穿左鞋都会极其别扭和难受。即使树中某结点只有一棵子树也要区分它是左子树还是右子树。下图中树 1 和树 2 是同一棵树但它们却是不同的二叉树。就好比你一不小心摔伤了手伤的是左手还是右手对你的生活影响度是完全不同的。1.2 二叉树的五种基本形态空树、只有根节点、根节点只有左子树、根节点只有右子树以及根节点同时有左子树和右子树这五种形态构成了所有二叉树的逻辑基础其递归定义是根据这些基本单元构建的。五种基本形态详解空二叉树 (Empty Binary Tree)不含任何节点的树是递归的基准情况。只有根节点 (A Single Node)只包含一个根节点没有子节点。根节点只有左子树 (Root with Left Subtree)根节点有左孩子但没有右孩子左孩子可能本身又是另一个二叉树。根节点只有右子树 (Root with Right Subtree)根节点有右孩子但没有左孩子右孩子可能本身也是一个二叉树。根节点既有左子树又有右子树 (Root with Both Left and Right Subtrees)根节点同时拥有左子树和右子树。这五种基本形态是后续二叉树相关算法的基础。1.3 特殊二叉树再来介绍一些特殊的二叉树。这些树可能暂时你不知道他们有什么用处但还是先了解一下后续会提到它们的具体用处。斜树顾名思义斜树是指所有结点都向一侧偏转的二叉树左斜树所有结点都只有左子树。右斜树所有结点都只有右子树。特点斜树每一层只有一个结点其结点总数等于树的深度。在某种程度上斜树可以看作是线性表的一种特殊表现形式。满二叉树满二叉树被视为一种“完美”的结构。在一棵二叉树中如果所有分支结点都存在左子树和右子树并且所有的叶子结点都在同一层上这样的树就称为满二叉树。核心特点叶子只能出现在最下一层。非叶子结点的度一定为 2。在同样深度的二叉树中满二叉树的结点个数最多叶子数也最多。完全二叉树对一棵具有n nn个结点的二叉树按层序编号如果编号为i ii(1 ≤ i ≤ n 1 \le i \le n1≤i≤n) 的结点与同样深度的满二叉树中编号为i ii的结点在二叉树中位置完全相同则这棵二叉树称为完全二叉树。叶子结点只能出现在最下两层。最下层的叶子一定集中在左部连续位置。倒数两层若有叶子结点一定都在右部连续位置。如果结点度为 1则该结点只有左孩子即不存在只有右孩子的情况。同样结点数的二叉树完全二叉树的深度最小。首先从字面上要区分“完全”和“满”的差异满二叉树一定是一棵完全二叉树但完全二叉树不一定是满的。 其次完全二叉树的所有结点与同样深度的满二叉树它们按层序编号相同的结点是一一对应的。这里有个关键词是按层序编号。其中完全二叉树还算是相对较了解的因为这是之前我们实现的堆结构的物理基础。1.4 二叉树的五条性质性质 1在二叉树的第i ii层上至多有2 i − 1 2^{i-1}2i−1个节点 (i ≥ 1 i \ge 1i≥1)。解析第一层是2 0 1 2^0 1201个节点第二层是2 1 2 2^1 2212个节点第三层是2 2 4 2^2 4224个节点。以此类推每层节点的上限遵循几何级数。性质 2深度为k kk的二叉树至多有2 k − 1 2^k - 12k−1个节点 (k ≥ 1 k \ge 1k≥1)。解析这是一个等比数列求和的结果。如果每一层都达到最大节点数即满二叉树总节点数即为∑ i 1 k 2 i − 1 2 k − 1 \sum_{i1}^{k} 2^{i-1} 2^k - 1∑i1k​2i−12k−1。性质 3对任何一棵二叉树T TT如果其终端节点数为n 0 n_0n0​度为 2 的节点数为n 2 n_2n2​则n 0 n 2 1 n_0 n_2 1n0​n2​1。解析设n nn为总结点数n 1 n_1n1​为度为 1 的节点数则n n 0 n 1 n 2 n n_0 n_1 n_2nn0​n1​n2​。从分支线连线的角度看连线总数等于n − 1 n-1n−1除了根节点每个节点上方都有一条连线同时也等于n 1 2 n 2 n_1 2n_2n1​2n2​度为 1 的节点引出 1 条线度为 2 的节点引出 2 条线。通过方程n 0 n 1 n 2 − 1 n 1 2 n 2 n_0 n_1 n_2 - 1 n_1 2n_2n0​n1​n2​−1n1​2n2​可推导出n 0 n 2 1 n_0 n_2 1n0​n2​1。性质 4具有n nn个节点的完全二叉树的深度为⌊ log ⁡ 2 n ⌋ 1 \lfloor \log_2 n \rfloor 1⌊log2​n⌋1。解析根据性质 2深度为k kk的满二叉树节点数为2 k − 1 2^k - 12k−1。对于完全二叉树其节点数n nn满足2 k − 1 − 1 n ≤ 2 k − 1 2^{k-1} - 1 n \le 2^k - 12k−1−1n≤2k−1。通过对数运算可得k ⌊ log ⁡ 2 n ⌋ 1 k \lfloor \log_2 n \rfloor 1k⌊log2​n⌋1。性质 5如果对一棵有n nn个节点的完全二叉树的节点按层序编号对任一节点i ii(1 ≤ i ≤ n 1 \le i \le n1≤i≤n) 有根节点判断如果i 1 i1i1则节点i ii是二叉树的根无双亲如果i 1 i1i1则其双亲是节点⌊ i / 2 ⌋ \lfloor i/2 \rfloor⌊i/2⌋。左孩子判断如果2 i n 2i n2in则节点i ii无左孩子节点i ii为叶子节点否则其左孩子是节点2 i 2i2i。右孩子判断如果2 i 1 n 2i 1 n2i1n则节点i ii无右孩子否则其右孩子是节点2 i 1 2i 12i1。1.5 存储结构⽤链表来表⽰⼀棵⼆叉树即⽤链来指⽰元素的逻辑关系。 通常的⽅法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址 其结构如下typedefstructBinaryTreeNode{BTDataType data;//数据structBinaryTreeNode*left;//左孩子structBinaryTreeNode*right;//右孩子}BTNode;二、遍历的递归之美二叉树的遍历原理假设我手头有 20 张 100 元的和 2000 张 1 元的奖券同时撒向了空中大家比赛看谁最终捡的最多。如果是你你会怎么做相信所有同学都会说一定先捡 100 元的。道理非常简单因为捡一张 100 元等于 1 元的捡 100 张效率高的不是一点点。所以可以得到这样的结论同样是捡奖券在有限时间内要达到最高效率次序非常重要。对于二叉树的遍历来讲次序同样显得很重要。二叉树的遍历traversing binary tree是指从根结点出发按照某种次序依次访问二叉树中的所有结点使得每个结点被访问一次且仅被访问一次。这里有两个关键词访问和次序。访问其实是要根据实际的需要来确定具体做什么比如对每个结点进行相关计算输出打印等它算作是一个抽象操作。在这里我们可以简单地假定访问就是输出结点的数据信息。二叉树的遍历次序不同于线性结构最多也就是从头至尾、循环、双向等简单的遍历方式。树的结点之间不存在唯一的初始前驱和后继关系在访问一个结点后下一个被访问的结点面临着不同的选择。主要分为以下的形式2.1 前序遍历逻辑顺序可以总结为根结点 - 左子树 - 右子树。voidPreOrder(BTNode*root){if(rootNULL){printf(NULL );return;}printf(%d ,root-data);// 访问根PreOrder(root-left);// 递归左子树PreOrder(root-right);// 递归右子树}规则是若二叉树为空则空操作返回否则先访问根结点然后前序遍历左子树再前序遍历右子树。如下图所示遍历的顺序为ABDGHCEIF。2.2 中序遍历 (In-order Traversal)逻辑顺序可以总结为左子树 - 根节点 - 右子树。voidInOrder(BTNode*root){if(rootNULL){printf(NULL );return;}InOrder(root-left);printf(%d ,root-data);InOrder(root-right);}规则是若树为空则空操作返回否则从根结点开始注意并不是先访问根结点中序遍历根结点的左子树然后是访问根结点最后中序遍历右子树。如下图所示遍历的顺序为GDHBAEICF。2.3 后序遍历 (Post-order Traversal)逻辑顺序可以总结为左子树 - 右子树 - 根节点。voidPostOrder(BTNode*root){if(rootNULL){return;}PostOrder(root-left);PostOrder(root-right);printf(%d ,root-data);}规则是若树为空则空操作返回。否则从左到右先叶子后结点的方式遍历访问左右子树最后是访问根结点。如下图所示遍历的顺序为GHDBIEFCA。2.4 层序遍历规则若树为空则空操作返回。顺序否则从树的第一层也就是根结点开始访问从上而下逐层遍历在同一层中按从左到右的顺序对结点逐个访问。示例顺序ABCDEFGHI。层序遍历需要借助队列这里就不给源码了给出参考思路若树为空则返回否则从根结点开始按从上到下、从左到右的顺序逐层访问每个结点。在实际算法实现中通常利用队列这一数据结构先将根结点入队然后循环执行“出队一个结点进行访问并将该结点的左、右孩子若存在依次入队”的操作直到队列为空为止。三、经典 OJ 题解析二叉树的题目几乎全靠递归。递归的精髓在于不要试图在大脑里压入所有的执行栈而是要相信函数的功能并处理好边界条件。3.1 求二叉树的高度一棵树的高度是多少它取决于它的左子树和右子树中较那个“更高”的一个再加上根节点本身的一层。详细逻辑推导子问题求左子树高度leftHeight求右子树高度rightHeight。结束条件如果节点为空高度为 0。返回逻辑比较左右高度取最大值 1。intTreeHeight(BTNode*root){if(rootNULL){return0;}// 注意一定要定义变量存储结果否则会导致指数级的重复计算intleftHeightTreeHeight(root-left);intrightHeightTreeHeight(root-right);returnleftHeightrightHeight?leftHeight1:rightHeight1;}深度性能优化笔记在 C 语言中如果不使用变量记录leftHeight而是在return时写TreeHeight(root-left) TreeHeight(root-right) ? ...会导致在比较时调用一次递归在返回加一时又调用一次递归。这会使时间复杂度从O ( N ) O(N)O(N)降级为O ( 2 N ) O(2^N)O(2N)在OJ测试中会超时。3.2 求节点个数如何统计一棵森林里有多少棵树数数叶子数数中间。对于二叉树总节点数 左子树节点数 右子树节点数 1根节点。intTreeSize(BTNode*root){// 递归出口空树节点数为0returnrootNULL?0:TreeSize(root-left)TreeSize(root-right)1;}解析这段代码极其简洁体现了递归的分治思想。每一次调用TreeSize都在解决一个小规模的“根左右”问题。3.3 判断两个二叉树是否相同要判断两棵树 p 和 q 是否相同必须满足结构相同该有节点的地方都有。数值相同。递归逻辑拆解如果都为空说明这一侧比较到底了依然一致返回true。其中一个为空另一个不为空结构不对等返回false。值不相等内容不对等返回false。递归检查只有当left相同且right也相同时整棵树才相同。boolisSameTree(structBinaryTreeNode*p,structBinaryTreeNode*q){// 1. 同时为空是真的相同if(pNULLqNULL){returntrue;}// 2. 一个为空一个不为空或者值不同则不同if(pNULL||qNULL||p-val!q-val){returnfalse;}// 3. 递归比较左右子树returnisSameTree(p-left,q-left)isSameTree(p-right,q-right);}四、递归的代价与内存风险虽然二叉树的递归解法非常优雅但在 C 语言中我们必须时刻关注栈溢出Stack Overflow风险。空间复杂度二叉树递归的空间复杂度取决于树的高度h hh。在最坏情况下树退化成链表h N h NhN此时递归深度为N NN极易导致系统栈空间耗尽。尾递归优化虽然部分编译器支持尾递归优化但由于二叉树通常需要两次递归调用左和右无法直接应用标准尾递归优化。五、 总结二叉树的学习不仅仅是掌握几种遍历算法更是对递归思想的一次洗礼。通过 C 语言的手动内存管理和指针操作你能更清晰地看到节点是如何在堆区诞生的以及递归是如何在系统栈上起舞的。前中后序是底功决定了你观察树的角度。高度与节点数是分治法的典型应用。相同树的判断则是对多路递归边界条件的极致考察。