ㅤcoderitl
V1
2022/02/07阅读:47主题:萌绿
树、二叉树、森林
树和二叉树
树
-
树是一种新的逻辑结构
集合: 数据元素间除了"同属于一个集合"外,无其他关系
线性结构: "一对一的关系",如线性表,栈、队列、串
树形结构: "一对多的关系",如: 树
图形结构: "多对多"的关系,如: 图
-
常见的树形结构
目录
家庭关系
文件目录
...
-
树的定义
-
树是 n
个节点的有限集 -
节点个数为 零
的树成为空树
-
任意一个非空树中n>0 -
有且仅有一个特定的称为 根
的节点 -
非根的节点可以分为 互不相交
的有限集,每个集合本身又是一棵树,这些树称为根
的子树
-
度
: 节点最多分叉数量
-
-
节点的层次:
根
到该节点
的层数
树的度:
根的度:
关系树的度:
树的深度:
从根节点垂直向下数
-
树的
家谱图
双亲 上层的节点(直接前驱) 孩子 下层节点的子树的根(直接后驱) 祖先 从根到该节点所经分支的所有节点 子孙 该节点下层子树中的任一节点 兄弟 同一双亲的同层节点 堂兄弟 双亲位于同一层的节点(但并非同一双亲) -
森林
森林
: 删除根节点后不相交的树的集合
有序树
: 节点各子树从左至右有序,不能互换(左为第一)
无序树
: 节点各子树可互换位置
二叉树(Binary Tree
):
-
二叉树是
n >= 0
个节点所构成的集合,它或为空树n = 0
;或非空树,对于非空树T
-
有且仅有一个
称之为根
的节点 -
除根以外的其余节点分为两个互不相交的子集 T_1
和T_2
,分别称为T
的左子树和右子树,且T_1
和T_2
本身又都是二叉树
-
-
二叉树的特点及与树的异同
二叉树 树 具有递归性 具有递归性 至多只有两颗子树(节点的度不超过 2) 没有限制子树个数的上限 子树有左右之分,其次序不能任意颠倒(有序树) 子树可能有有序,也可能无序 -
二
叉树的几种形态image.png -
三节点
二叉树的五种
形态image.png -
为什么研究二叉树
普通树(多叉树)不转化为二叉树,运算很难实现
为何要重点研究每个节点最多只有两个二"叉"的树
可以证明,所有树都能转化为唯一对应的二叉树,不失一般性。
二叉树的性质
-
性质一 在二叉树的第
i
层上至多有2^(i-1)
个节点 -
性质二 深度为
k
的二叉树至多有(2^k)-1
个节点
深度为 1:1=(2^1)-1
个节点
... -
性质三 对于任何一个二叉树,若 2 度的节点数有
n_2
个,则叶子数n_0
必定为n_2+1
,即n_0 = n_2 + 1
完全二叉树与满二叉树
满二叉树 | 完全二叉树 |
---|---|
![]() |
![]() |
深度为k 且含有(2^k)-1 个节点的二叉树 |
深度为k ,有n 个节点的二叉树,当且仅当其每个节点都与深度为k 的满二叉树中(自上而下从左往右)编号从1 至n 的节点一 一对应 |
-
满二叉树的特点 -
每一层上的节点树都是最大节点数
-
每一层 i 的节点树都具有最大值 2^(i-1)
-
树和二叉树的转换及其应用
树转换为二叉树
-
转换的实现步骤
-
加线: 在兄弟之间加一条连线 -
抹线: 在每个节点,除了其左孩子外,去除其余孩子之间的关系 -
以树的 根
节点为轴心
,将整树顺时针旋转45°
树转换为二叉树(01) 树转换为二叉树(02) -
二叉树转换为树
加线: 若 p
节点是双亲节点的左孩子,则将p
的右孩子,右孩子的右孩子...沿分支找到的所有右孩子,都与p
的双亲用线连起来抹线: 抹掉原二叉树中双亲与右孩子之间的连线 将节点按层次排列,形成树结构
![]()
二叉树转换为树
森林
森林转换为二叉树(二叉树与多颗树之间的关系)
将各棵树分别转换成二叉树 将每棵树的根节点用线相连 以第一颗树根节点为二叉树的根,再以根节点为轴心,顺时针旋转,构成二叉树型结构
![]()
森林转换为二叉树
二叉树转换为森林
抹线: 将二叉树中根节点与其右孩子连线,沿右分支搜索到的所有右孩子间连线全部抹掉,使之变成孤立的二叉树 还原: 将孤立的二叉树还原成树
![]()
二叉树转换为森林
作者介绍
ㅤcoderitl
V1