当前位置：首页 > news >正文

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

news 2026/7/25 23:46:37

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

Bilibili 同步视频
一、现实树 vs 计算机树：反向生长的“倒栽葱”
二、链表与树的关联：链表是特殊的树形结构
- C++代码对比（核心差异）
三、二叉树：树形结构的核心（重点）
- 1. 二叉树节点定义（C++标准版）
- 2. 二叉树结构示例
- 3. 示例二叉树初始化（C++）
四、节点的“度”：衡量分叉能力的关键
五、二叉树经典性质（必记）
- 简化推导（初中数学可懂）
六、写在最后

Bilibili 同步视频

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

🌳 数据结构是程序设计的基石，树形结构更是贯穿各类技术场景（数据库索引、文件系统等）的核心。二叉树作为树形结构的经典代表，是每个程序员的必备知识点。本文从现实场景出发，简化拆解从链表到二叉树的演变、核心定义及经典性质，帮你快速吃透底层逻辑！

一、现实树 vs 计算机树：反向生长的“倒栽葱”

现实中的树：根在地下，向上分叉、枝繁叶茂，遵循“根→树干→枝叶”的生长逻辑。

计算机中的树：恰好相反，是“倒栽葱”结构——根节点在最上方，叶子节点在最下方，通过节点与有向边的指向关系，实现层级关联。

【文本绘制：结构对比】

现实树：枝叶 → 树干 → 树根（地下）

计算机树：根节点（1）→ 子节点（2、3、4）→ 叶子节点（5、6）

核心本质：计算机树 = 节点（存储数据） + 有向边（表示层级关系）。

二、链表与树的关联：链表是特殊的树形结构

💡 核心结论：链表是一种特殊的树形结构，二者的核心区别的在于指针域的指向能力。

链表：每个节点只有1个指针域，仅能唯一指向一个后继节点，呈线性结构（一对一关联）；
树形结构：将单一指针域改为数组指针域，可指向多个子节点，实现“分叉”（一对多关联）。

【文本绘制：树转链表示意】

原始树：根（1）→ [2、3、4] → 2→5，4→[5、6] → 砍去多余分支 → 链表：1→2→5

C++代码对比（核心差异）

// 1. 链表节点（单一指针域）structListNode{intval;ListNode*next;// 仅指向1个后继节点ListNode(intx):val(x),next(nullptr){}};// 2. 树形节点（数组指针域，以三叉树为例）#include<vector>usingnamespacestd;structTreeNode{intval;vector<TreeNode*>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只有右孩子6；4、5、6为叶子节点（无孩子）。

3. 示例二叉树初始化（C++）

intmain(){// 创建所有节点BinaryTreeNode*root=newBinaryTreeNode(1);BinaryTreeNode*node2=newBinaryTreeNode(2);BinaryTreeNode*node3=newBinaryTreeNode(3);BinaryTreeNode*node4=newBinaryTreeNode(4);BinaryTreeNode*node5=newBinaryTreeNode(5);BinaryTreeNode*node6=newBinaryTreeNode(6);// 建立左右孩子关联root->left=node2;root->right=node3;node2->left=node4;node2->right=node5;node3->right=node6;return0;}