从链表到二叉树：树形结构的入门与核心性质解析

从链表到二叉树树形结构的入门与核心性质解析Bilibili 同步视频一、现实树 vs 计算机树反向生长的“倒栽葱”二、链表与树的关联链表是特殊的树形结构C代码对比核心差异三、二叉树树形结构的核心重点1. 二叉树节点定义C标准版2. 二叉树结构示例3. 示例二叉树初始化C四、节点的“度”衡量分叉能力的关键五、二叉树经典性质必记简化推导初中数学可懂六、写在最后Bilibili 同步视频从链表到二叉树树形结构的入门与核心性质解析 数据结构是程序设计的基石树形结构更是贯穿各类技术场景数据库索引、文件系统等的核心。二叉树作为树形结构的经典代表是每个程序员的必备知识点。本文从现实场景出发简化拆解从链表到二叉树的演变、核心定义及经典性质帮你快速吃透底层逻辑一、现实树 vs 计算机树反向生长的“倒栽葱”现实中的树根在地下向上分叉、枝繁叶茂遵循“根→树干→枝叶”的生长逻辑。计算机中的树恰好相反是“倒栽葱”结构——根节点在最上方叶子节点在最下方通过节点与有向边的指向关系实现层级关联。【文本绘制结构对比】现实树 枝叶 → 树干 → 树根地下计算机树根节点1→ 子节点2、3、4→ 叶子节点5、6核心本质计算机树 节点存储数据 有向边表示层级关系。二、链表与树的关联链表是特殊的树形结构 核心结论链表是一种特殊的树形结构二者的核心区别的在于指针域的指向能力。链表每个节点只有1个指针域仅能唯一指向一个后继节点呈线性结构一对一关联树形结构将单一指针域改为数组指针域可指向多个子节点实现“分叉”一对多关联。【文本绘制树转链表示意】原始树根1→ [2、3、4] → 2→54→[5、6] → 砍去多余分支 → 链表1→2→5C代码对比核心差异// 1. 链表节点单一指针域structListNode{intval;ListNode*next;// 仅指向1个后继节点ListNode(intx):val(x),next(nullptr){}};// 2. 树形节点数组指针域以三叉树为例#includevectorusingnamespacestd;structTreeNode{intval;vectorTreeNode*children;// 可指向多个子节点TreeNode(intx):val(x){}};注每个节点最多有3个指针域的树称为三叉树多余指针域指向nullptr空节点。三、二叉树树形结构的核心重点 定义每个节点最多有2个指针域分别称为左孩子left和右孩子right分叉方向严格限定为左右是应用最广泛的树形结构。1. 二叉树节点定义C标准版structBinaryTreeNode{intval;// 数据域BinaryTreeNode*left;// 左孩子指针BinaryTreeNode*right;// 右孩子指针// 构造函数默认左右孩子为空BinaryTreeNode(intx):val(x),left(nullptr),right(nullptr){}};2. 二叉树结构示例【文本绘制经典二叉树】根1/2 3/ \4 5 6结构说明根节点1的左孩子为2、右孩子为3节点2有左右孩子4、5节点3只有右孩子64、5、6为叶子节点无孩子。3. 示例二叉树初始化Cintmain(){// 创建所有节点BinaryTreeNode*rootnewBinaryTreeNode(1);BinaryTreeNode*node2newBinaryTreeNode(2);BinaryTreeNode*node3newBinaryTreeNode(3);BinaryTreeNode*node4newBinaryTreeNode(4);BinaryTreeNode*node5newBinaryTreeNode(5);BinaryTreeNode*node6newBinaryTreeNode(6);// 建立左右孩子关联root-leftnode2;root-rightnode3;node2-leftnode4;node2-rightnode5;node3-rightnode6;return0;}四、节点的“度”衡量分叉能力的关键 定义节点的度 该节点拥有的孩子节点数量不包含空指针分为3类度为0无孩子叶子节点如4、5、6度为1仅有1个孩子如节点3只有右孩子6度为2有2个孩子如节点1、2。小科普“度”源自图论树形结构中的“度”本质是图论中的“出度”节点指向其他节点的边数无需复杂记忆记住“度孩子数”即可。五、二叉树经典性质必记✅ 核心性质任意二叉树中度为0的叶子节点数n0 度为2的节点数n2 1无例外简化推导初中数学可懂前提1总节点数N 度为0节点数n0 度为1节点数n1 度为2节点数n2前提2N个节点的树必有N-1条边树的基本特征推导边数 所有节点度之和度为0贡献0条度1贡献1条度2贡献2条即边数 n1 2n2联立等式n0 n1 n2 n1 2n2 1 → 化简得 n0 n2 1。验证示例二叉树中n034、5、6n221、2321完全符合。六、写在最后从链表线性单一指向到二叉树层级左右分叉是数据结构从“线性”到“层级”的关键跨越。二叉树的核心价值的在于解决链表“查找效率低”的问题而n0 n2 1这一性质是后续学习二叉搜索树、平衡二叉树的基础。 数据结构的学习核心是理解“按需设计”的逻辑——每一种结构的升级都是为了适配更复杂的业务场景。下一篇我们将拆解二叉树的三种遍历方式用C实现递归与非递归代码敬请期待