数据结构与算法学习笔记(第五章 树与二叉树)(1)树
树
定义:
-
n个结点的有限集
-
n=0,树是空树
-
n>0
- 有且仅有一个处于顶端的结点我们把它称作根结点
- 其余结点分为m个互不相交的有限集T1,T2,T3…,TM
- 每个集合本身又是一棵树,称为根结点的子树
-
树的定义是递归的定义
应用于计算机领域
-
编译
-
数据库系统
-
算法分析
表示方式
-
倒树表示(最常见)
-
嵌套集合
-
凹入表示
- 凹入越深的结点,其层次越低
-
广义表
一堆术语
孩子
- 一个结点的子树的根结点称为该结点的孩子
双亲
- 对应的,这个结点称为孩子的双亲
祖先
- 从根到某个结点经过的分支上所有的结点
子孙
- 以某结点为根的子树中任意结点
兄弟
- 双亲都同一个的两个结点称为兄弟
堂兄弟
- 双亲都在同一层的两个结点称为堂兄弟
根结点
- 非空树中无前驱结点的结点
结点的度
- 结点拥有的子树数
树的度
- 树内各结点的的度的最大值
结点的层
- 根结点第一层,往下的分支结点叫第二层,再往下第三层,以此类推,叶子结点的层数最大
树的深度
- 树中结点的最大层次
分支结点
- 结点的度不为0的结点,也叫非终端结点
- 根结点以外的分支结点称为内部结点
叶子节点
- 结点的度为0的结点,也叫终端结点
有序树、无序树
森林
- m(m>=0)棵互不相交的树的集合
- 找一棵树,把根结点删除,剩下的那堆子树就成了森林
- 一棵树也是森林,因为m>=0,你可以认为是特殊的森林
- 给森林的各子树加上一个双亲结点,森林就变成树
- so 森林不一定是树,但树一定是森林
树的结构
- 一对多
注意!
-
树的术语也可以用于二叉树上
-
但是二叉树不属于树,二叉树和树属于两个东西,不要混为一谈