1,什么是树?
2,什么是树的度?
3,结点的层次
4 线性结构和树结构的比较
5 树的三种存储结构(双亲表示法,孩子表示法,孩子兄弟表示法)
6,二叉树的定义
7,满二叉树 和 完全二叉树
8 ,二叉树的性质
9, 二叉树的存储结构
1,什么是树?
树是n个结点的有序集合,n = 0 时为空树,
1,在非空树中,有且仅有一个可以称为根的结点。
2,n>1时,其余结点可分为m个互不相交的有限集,其中每一个集合本身是一颗树,并且称为根的子树。
注意子树一定是不可以相交的
2,什么是树的度?
1,树内各结点的度的最大值
2,结点拥有的子树数称为结点的度
3,结点的层次
从根开始定义,根为第一层。根的孩子为第二层,依次类推。
树中结点的最大层次称为树的深度或高度。
4 线性结构和树结构的比较
- 线性结构
第一个数据元素无前驱
最后一个数据元素无后继
中间元素,一个前驱一个后继 - 树结构
根结点,无双亲,唯一
叶结点,无孩子,可以有多个
中间结点,一个双亲,多个孩子。
5 树的三种存储结构(双亲表示法,孩子表示法,孩子兄弟表示法)
- 双亲表示法
1,连续的空间地址作储存结点
2,data 数据域 指针域指向双亲
缺点是找不到孩子结点
改进方式是再增加一个指针域指向孩子结点 - 孩子表示法
设计思想:每个结点有多个指针域,每个指针指向一棵子树的根结点。这种方法叫多重链表表示法
方案一:每个结点指针域的个数等于树的度
当所有的结点度数大致相等时才会高效
方案二:每个结点有三部分构成data 数据域,degree度域,指针域
但是需要维护每个结点的度的数值,运算上带来时间上的损耗。
孩子表示法:有2部分构成
1,顺序存储结构存储一个一维数组,数据域放data,指针域指向该结点的孩子链表
2,线性表中的元素,数据域放的是指向该元素在数组中的下标。指针域指向下一个孩子结点的指针
缺点:找不到双亲 ,在表头结点里再加一个指针域,指向父母结点。 - 孩子兄弟表示法
听名字就知道它的指针域要指向孩子和兄弟
孩子指针域:指向第一个孩子结点
兄弟指针域:指向此结点右边的兄弟结点
6,二叉树的定义
二叉树是n个结点的有限集合,该集合或者为空集(空二叉树)或者由一个根结点和两颗互不相交的,分别称为根结点的左子树和右子树的二叉树组成。
左子树和右子树是有顺序的,次序不能颠倒。
7,满二叉树 和 完全二叉树
所有的分支结点都存在左子树和右子树。
对于一个n个结点的二叉树,如果编号为i的结点与同样深度的满二叉树中编号为i的结点位置完全一致。
给每个结点按照满二叉树的结构逐层顺序编号,如果编号出现空档,说明不是完全二叉树。否则就是。
8 二叉树的性质
1在二叉树的第i层上最多有2^(i-1) 个结点
2深度为k的二叉树,至多有(2^k) - 1个结点
3n0 = n2 + 1
假设终端结点个数为n0,度为2的结点个数为n2,度为1的结点个数为n1
2个等式
n = n1 + n2 + n0
总线数 = n-1 = n1 + 2n2
4二叉树的深度为|log 2 n| + 1
|x|代表不大于x的最大整数
5对一颗有n个结点的完全二叉树,对任一结点i
5.1i = 1 ,结点i 是二叉树的根,无双亲。若i > 1则其双亲是结点|i / 2|
5.2如果2i > n 则结点i 无左孩子(结点i 为叶子结点)。否则其左孩子为结点2i
5.3如果2i + 1 > n 则结点i无右孩子
(5,1先推导完全二叉树的左侧左孩子的特点,2,再推导中间结点和左孩子的特点关系)
否则其右孩子是结点2i+ 1
9 二叉树的存储结构
- 二叉树的顺序存储结构
用一维数组存储二叉树中的结点
把不存在的结点设为^
一般用于完全二叉树 - 二叉链表
结点 一个数据域,2个指针域
如果有需要还可以增加一个指向双亲的指针域,那么就成三叉链表了