数据结构：二叉树的定义与特性
数据结构：二叉树的定义与特性
二叉树是数据结构中一种重要的树形结构，其特点是每个节点至多只有两棵子树，并且子树有左右之分。本文将详细介绍二叉树的定义、特殊类型、性质以及存储结构，帮助读者全面理解这一基础数据结构。
1. 二叉树的定义
二叉树是一种特殊的树形结构，其特点是每个节点至多只有两棵子树（即二叉树中不存在度大于2的节点），并且二叉树的子树有左右之分，其次序不能任意颠倒。二叉树是n(n>0)个节点的有限集合：
- n=0，为空二叉树。
- 或者由一个根节点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。
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。