二叉树-树形结构

作者: 嗯o哼 | 来源:发表于2020-11-14 22:46 被阅读0次

一、树形结构

线性结构：数组、链表、栈、队列都是线性结构
树形结构：类似于一颗树的形状，一个结点会有多个子结点。

$\color{#ea4335}{二叉树:}$ 结点最多只有两个结点
$\color{#ea4335}{多叉树:}$ 大于两个结点

二、常见的树形结构

1.公司的组织架构
2.文件夹的组织

三、树的基本概念

$\color{#ea4335}{结点}$ ：结构中的每一个元素都是结点
$\color{#ea4335}{根结点}$ ：树顶端的结点，一个树，有且仅有一个根结点，没有父结点
$\color{#ea4335}{父结点}$ ：结点的上层结点
$\color{#ea4335}{子结点}$ ：结点的下层结点
$\color{#ea4335}{兄弟结点}$ ：具有同一个父结点的结点

$\color{#ea4335}{空树}$ ：没有结点
$\color{#ea4335}{子树}$ ：由结点和它的后代组合的树
$\color{#ea4335}{左树}$ ：结点左边的子树
$\color{#ea4335}{右树}$ ：结点右边的子树

结点的 $\color{#ea4335}{度}$ ：结点子树的个数
树的 $\color{#ea4335}{度}$ ：各结点度的最大值
$\color{#ea4335}{叶子结点}$ ：度为0的结点
$\color{#ea4335}{非叶子结点}$ ：度不为0的结点

$\color{#ea4335}{层数}$ ：根结点在第一层，子结点在第二层，依次类推
结点的 $\color{#ea4335}{深度}$ ：从根结点到当前结点的唯一路径上结点总数
结点的 $\color{#ea4335}{高度}$ ：从当前结点到最远叶子结点的路径上的结点总数

$\color{#ea4335}{树的深度}$ ：所有结点深度的最大值
$\color{#ea4335}{树的高度}$ ：所有结点高度的最大值
$\color{#ea4335}{树的高度}$ 等于 $\color{#ea4335}{树的深度}$

$\color{#ea4335}{有序树}$ ：树中任意结点的子结点之间是有顺序关系，如果调换顺序就成为了两个不同的树
$\color{#ea4335}{无序树}$ ：树中任意结点的子结点之间是没有顺序关系
$\color{#ea4335}{森林}$ ：由m(m≥0)棵不相交的树集合

四、二叉树（Binary Tree）

每个结点的度最大为2（最多只有两颗子树）
左右子树有顺序，不可以调换，是有序树
如果某一个结点只有一课子树，也要区分左右子树

空树：没有结点
只有一个结点的树也是二叉树
只有左子树或右子树也是二叉树
具有左右子树的树也是二叉树

1.二叉树的性质

非空二叉树的第i层最多有2^i-1个结点 (i≥1)

高度为h的二叉树上最多有2^h-1个结点 (h ≥ 1)

对于任一非空二叉树，叶子结点数等于度为2的结点数 + 1

推理
假设叶子结点数n0，度为1的结点数n1，度为2的结点数n2
二叉树的总结点数 = n0 + n1 + n2
二叉树的边数 = n1 + 2 * n2 = n - 1 = n0 + n1 + n2 - 1
即 n1 + 2 *n2 = n0 + n1 + n2 - 1    推出 n0 = n2 + 1
即叶子结点数 等于 度为2的结点数 + 1

2.真二叉树

所有结点的度要么为0要么为2

image.png

3.满二叉树

所有结点的度要么为0，要么为2，且所有的叶子结点都在最后一层
同样高度的二叉树中，满二叉树的叶子结点是最多的，总结点数量最多
满二叉树一定是真二叉树，真二叉树不一定是满二叉树

image.png

第i层的结点数：2^i-1

叶子结点的数量（最后一层的结点数） 2^h-1 （h为高度）
高度h = ${log_2{n+1}}$ ( n为结点总数)

4.完全二叉树

叶子结点只会出现在最后两层，且最后一层的叶子结点是靠左对齐
完全二叉树从根结点到倒数第二层是一课满二叉树
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

二叉树-树形结构

一、树形结构

二、常见的树形结构

三、树的基本概念

四、二叉树（Binary Tree）

1.二叉树的性质

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读