线性结构之——二叉树

1.定义
二叉树的每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点),并且二叉树的子树有左右之分,其次序不能颠倒. 二叉树以递归的形式定义,二叉树是n(n>=0)个结点的有限集合:

1. 或者为空二叉树,即n=0,
2. 或者由一个根节点和两个互不相交的被称为根的左子树和右子树组成,左子树和右子树分别是一棵二叉树.

二叉树和度为2的有序树的区别:
(1)度为2的树至少有3个结点,而二叉树可以为空
(2)度为2的有序树的孩子节点的左右次序是相对于另一孩子结点而言的,如果某个结点只有一个孩子结点,这个孩子结点就无须区分其左右次序,而二叉树无论其孩子树是否为2,均需要确定其左右次序,也就是说二叉树的结点不是相对于另一个结点而言的,而是确定的.

2.几个特殊的二叉树

(1) 满二叉树:每一层结点都达到了当层能达到的最大结点数,满二叉树的叶子结点都在最下一层,除叶子结点外,每个结点的度数均为 2.
(2) 完全二叉树:除最下面的一层外,其余层的结点个数都达到了当层能达到的最大结点数:每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时,称之为完全二叉树.
(3) 排序二叉树: 一棵二叉树或者是空二叉树,或者是具有如下性质的二叉树:
左子树上所有结点的关键字均小于根结点的关键字,右子树上所有结点的关键字都大于根结点的关键字.左子树和右子树又各是一棵排序树.
(4)平衡二叉树: 树上任意结点的左子树和右子树的深度之差不超过1.

3.二叉树的存储结构

二叉树的顺序存储结构就是用一组地址连续的存储单元依次从上而下、自左向右存储完全二叉树的结点元素，即将完全二叉树上编号为i的结点元素存储在某个数组下标为i-1的分量中，完全二叉树和满二叉树采用顺序存储比较合适，树种结点的序号可以唯一地反映出结点之间的逻辑 关系，这样既能最大可能节省存储空间，又可以利用数组元素的下标确定结点