7.树和二叉树
7.1树的定义
树(Tree)是n(n>=0)个结点的 有限集
- 若n = 0 称为空树
- 若n > 0，则它满足如下两个条件
- 有且仅有一个特定的称为 根的结点
- 其余结点可分为m(m>=0)个互不相交的有限集 T1,T2,T3…Tm，其中每一个集合本身又是一棵树，并称为根的 子树(SubTree)。
树的结构：
1.结点之间又分支
2.具有层次关系
树的定义是一个递归的定义
7.1.1树的基本术语
结点：数据元素以及指向子树的分支
根结点：非空树中无前驱结点的结点
结点的度：结点拥有的子树数
树的度：树内各结点的度的最大值
叶子：终端结点，无子树，度=0；
分支结点：非终端结点，根节点以外的分支结点称为内部节点
兄弟结点：拥有共同双亲的结点为兄弟结点，无同双亲的结点，但是在同一层上结点的称为堂兄弟
结点的祖先：从根到该结点所经分支上的所有结点。
结点的子孙：从某结点为根的子树中的任一结点。
树的深度：树中结点的最大层次。
有序树：树中结点的各子树从左至右有次序(最左边的为第一个孩子)
无序树：树中结点的各子树无次序
森林：是m(>=0)课互不相交的树的集合，把根结点删除了就变成了森林。
一棵树可以看成是一个特殊的森林，给森林中各子树加上一个双亲结点，森林就变成了树。
树一定是森林 森林不一定是树
结点的子树的根称为该结点的 孩子，该结点称为孩子的双亲。
树结构和线性结构的比较
线性结构 树结构 第
一
个数据元素： 无前驱
根节点(只有一个)： 无双亲
最后
一
个数据元素： 无后继
叶子结点(可以有
多
个)： 无孩子
其他数据元素： 一个前驱一个后继
其他节点(中间节点)： 一个双亲，多个孩子 一对一 一对多
7.1.2二叉树的定义
二叉树是n(n>=0)个结点的有限集，它或者是空集(n=0),或者由一个 根节点及 两颗互不相交的分别称作这个根的 左子树和右子树的二叉树组成。
特点：
- 每个结点最多有俩孩子(二叉树中不存在度大于2的结点)
- 子树有左右之分，其次序不能颠倒
- 二叉树可以是空集合，根可以有空的左子树或空的右子树
注意：二叉树不是树的特殊情况，他们是两个概念
二叉树结点的子树要区分左子树和右子树，即使只有一颗子树也应该说明是左还是右。
树当结点只有一个孩子时，就不需要区分左右次序。
二叉树的每个结点位置都是固定的，可以是空，但是不能说它没有位置。
树的结点位置是相对于别的结点来说的，没有别的结点时，顺序就无所谓。
二叉树的5种基本形态：
7.2树和二叉树的抽象数据类型定义
因为树的操作很多，下面只介绍重要的几个操作
CreateBiTree(&T,definition){
初始条件: definition给出二叉树T的定义
操作结果: 按definition构造二叉树
}
PreOrderTraverse(T){
初始条件: 二叉树T存在
操作结果: 先序遍历T，对每个节点访问一次。
}
InOrderTraverse(T){
初始条件: 二叉树T存在
操作结果: 中序遍历T，对每个节点访问一次。
}
PostOrderTraverse(T){
初始条件: 二叉树T存在
操作结果: 后序遍历T，对每个节点访问一次。
}
Assign(T,cur_e){
初始条件: 树T存在，cur_e是T中某个结点
操作结果: 结点cur_e赋值为value
}
7.3二叉树的性质
性质1： 在二叉树的第i层上至多有2i-1个结点(i>=1)，第i层上最少有1个结点；
性质2： 深度为k的二叉树至多有2k-1个结点(k>=1)，最少有k个结点；
性质3： 对任何一颗二叉树T，如果其叶子数为n0，度为2的结点为n2，则n0 = n2+1；
两种特殊形式的二叉树
满二叉树：
一颗深度为k且有2k-1个结点的二叉树称为满二叉树；
特点：
1.每一层上的结点数都是最大结点数(即 每层都满)
2. 叶子节点全部都在最底层
对满二叉树结点位置进行编号
- 编号规则：从根节点开始，自上而下，自左而右
- 每一结点位置都有元素
满二叉树在同样深度的二叉树中 结点个数最多
满二叉树在同样深度的二叉树中 叶子结点个数最多
完全二叉树
深度为k的具有n个结点的二叉树，当且仅当其每一个结点都与深度为k的 满二叉树中 编号为1~n的结点 一一对应时，称为完全二叉树
注：在满二叉树中，从最后一个结点开始， 连续去掉 任意个结点，即使一颗完全二叉树.
特点：
- 叶子只可能分布在层次最大的两层上。
- 对任一结点，如果其右子树的最大层次为i，则其左子树的最大层次必为 i 或 i + 1 .
满二叉树一定是完全二叉树
完全二叉树不一定是满二叉树
性质4： 具有n个结点的完全二叉树的深度为⌊ log2n ⌋ + 1
注：⌊ x ⌋：称为x的底，表示小于x的最大整数，也叫 向下取整。 ⌊ 3.5 ⌋ = 3
⌈ x ⌉ 表示大于x的最小整数， 向上取整（取顶） ⌈ 3.5 ⌉ = 4
性质5：如果有一棵有n个结点的 完全二叉树(深度为⌊ log2n ⌋ + 1)的结点按层序编号(从第1层到第⌊ log2n ⌋ + 1层，每层从左到右)，则对 任一结点 i (1
Original: https://www.cnblogs.com/gaoqinghui/p/16257304.html
Author: 忧愁小松鼠
Title: 数据结构与算法—树的学习
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/569643/
转载文章受原作者版权保护。转载请注明原作者出处！