数据结构—《二叉树的定义与特性》

目录

1.二叉树的定义

2.特殊的二叉树

1）满二叉树

2）完全二叉树

3）二叉排序树。

4）平衡二又树。

5）正则二文树

3.二叉树的性质

4.二叉树的存储结构

1）顺序存储结构

2）链式存储结构

1.二叉树的定义

二叉树是一种特殊的树形结构，其特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点)，并且二叉树的子树有左右之分，其次序不能任意颠倒。二叉树是n(n>0)个结点的有限集合：（1）n=0，为空二叉树。（2）或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

2.特殊的二叉树

1）满二叉树

一棵高度为h，且有 2^h-1个结点的二叉树称为满二叉树，即二叉树中的每层都含有最多的结点。满二叉树的叶结点都集中在二叉树的最下一层,并且除叶结点之外的每个结点度数均为2。

可以对满二叉树按层序编号：约定编号从根结点（根结点编号为1）起，自上而下，自左向右。这样，每个结点对应一个编号，对于编号为i的结点，若有双亲，则其双亲为[i/2]（向下取整）若有左孩子，则左孩子为2i；若有右孩子，则右孩子为2i+1。

即给出高度h后，每层必须填满，一棵满二叉树如下图：

2）完全二叉树

高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1~n 的结点一一对应时，称为完全二又树。

① 若 i≤[n/2]（向下取整），则结点i为分支结点，否则为叶结点。

②叶结点只可能在层次最大的两层上出现。对于最大层次中的叶结点，都依次排列在该层最左边的位置上。

③ 若有度为1的结点，则最多只可能有一个，且该结点只有左孩子而无右孩子。

④按层序编号后，一旦出现某结点(编号为i)为叶结点或只有左孩子，则编号大于i的结点均为叶结点。

⑤ 若n为奇数，则每个分支结点都有左孩子和右孩子；若n为偶数，则编号最大的分支结点(编号为n/2)只有左孩子，没有右孩子，其余分支结点左、右孩子都有。

即每层不需必须填满，但前面的序号结点结构必需与满二叉树的相同。

3）二叉排序树。

左子树上所有结点的关键字均小于根结点的关键字，右子树上所有结点的关键字均大于根结点的关键字；左子树和右子树又各是一棵二叉排序树。

给出一组数据50 54 21 84 10 31 16 32 9 51 ，挨个插入，这时候没有树满不满之分，得到二叉排序树：

也可以得到这么一棵二叉排序树，只有右子树，没有左子树：

4）平衡二又树。

树中任意一个结点的左子树和右子树的高度之差的绝对值不超过1。

下面是一棵平衡二叉树：

当把6结点删除，3结点左右子树高度之差绝对值为2，破环了平衡，不再是一棵平衡二叉树。

5）正则二文树

树中每个分支结点都有2个孩子，即树中只有度为0或2的结点。

3.二叉树的性质

1）非空二叉树上的叶结点数等于度为2的结点数加1，即n0=n+1。

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

3）高度为h的二叉树至多有 2^h-1个结点(h≥1)。

4.二叉树的存储结构

1）顺序存储结构

二叉树的顺序存储是指用一组连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在一维数组下标为i-1的分量中。

依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映结点之间的逻辑关系，这样既能最大可能地节省存储空间，又能利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。

完全二叉树顺序存储结构：

一般二叉树的顺序存储结构：

2）链式存储结构

由于顺序存储的空间利用率较低，因此二叉树一般都采用链式存储结构，用链表结点来存储二叉树中的每个结点。在二叉树中，结点结构通常包括若干数据域和若干指针域，二叉链表至少包含3个域:数据域 data、左指针域 1child 和右指针域rchild。