树
一、树的基本概念
1.1 树的定义
树是一种非线性的数据结构,由n(n≥0)个有限节点组成一个具有层次关系的集合。
1.2 树的示意图
A ← 根节点
/ \
B C ← A的子节点
/ \ \
D E F ← 叶节点
1.3 树的组成部分
- 根节点(Root): 树的最顶层节点(如A)
- 父节点/子节点: B是A的子节点,A是B的父节点
- 叶节点(Leaf): 没有子节点的节点(如D,E,F)
- 边(Edge): 连接两个节点的线
- 深度: 从根到该节点的边数(A深度为0,B为1,D为2)
- 高度: 从该节点到最深叶节点的边数
- 根节点(Root): 树的最顶层节点(如A)
二、树的常见类型
2.1 二叉树
- 每个节点最多有两个子节点(左子节点和右子节点)
A
/ \
B C
/ \ \
D E F
- 每个节点最多有两个子节点(左子节点和右子节点)
满二叉树
- 每个节点都有0或2个子节点,且所有叶节点在同一层
A
/ \
B C
/ \ / \
D E F G
- 每个节点都有0或2个子节点,且所有叶节点在同一层
2.3 完全二叉树
- 除最后一层外,其他层都填满,且最后一层节点靠左排列
A
/ \
B C
/ \ /
D E F
- 除最后一层外,其他层都填满,且最后一层节点靠左排列
三、树的应用场景
- 文件系统: 文件夹和文件的层级结构
- 组织结构图: 公司部门层级关系
- 家谱图: 家族成员关系
- HTML DOM树: 网页元素嵌套关系
- 决策树: 机器学习中的分类模型
四、树的基本操作示意图
- 4.1 遍历方式
- 前序遍历: 根→左→右
- 中序遍历: 左→根→右
- 后序遍历: 左→右→根
4.2 查找操作
查找E节点路径: A → B → E
4.3 插入操作
在C节点下插入G:
A
/ \
B C
/ \ \
D E G
逻辑结构
树的几要素:
二叉树
满二叉树
完全二叉树
满二叉树与完全二叉树的关系:
使用总边数一致推导:
N0 = N2 + 1
题目
一棵节点已知的二叉树,求至多有多少个节点有2个子节点公式:
- 2 * n2 + 1 + n1 = 10
n2:度数为2的节点,n1度数为1的节点,n0度数为0的节点