4.1二叉树的概念4.2二叉树的主要性质4.3二叉树的抽象数据类型4.4周游二叉树4.5二叉树的实现4.6二叉搜索树4.7堆与优先队列4.8哈夫曼编码树基本术语结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM(从根到结点的)路径：结点的层次:树的深度：由从根到该结点所经分支和结点构成.若树中存在结点序列k0，k1，…，ks，使得，，…，都是树中的边，则称从结点k0到结点ks存在一条路径。该路径所经历的边的个数称为这条路径的路径长度。ABCDEFGHIJMKL假设根结点的层次为0,第l层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次孩子结点、双亲结点、兄弟结点、堂兄弟祖先结点、子孙结点•在一棵树中，若存在结点k指向结点k’的连线，则称k是k’的父(双亲)结点，而k’则是k的子(孩子)结点，有向连线称作边。•同一个父结点的子结点之间互称兄弟。树中没有父结点的结点称为根。没有子结点的结点称为树叶。•如果结点的双亲结点之间互为兄弟，则这些结点互称堂兄弟。•若有一条由k到达ks的路径，则称k是ks的祖先，ks是k的子孙。任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点，F被称为子树森林森林：是m（m≥0）棵互不相交的树的集合ArootBEFKLCGDHIJMF对比树型结构和线性结构的结构特点线性结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)4.1二叉树的概念4.1.1二叉树的定义及相关概念4.1.2满二叉树、完全二叉树、扩充二叉树二叉树的定义二叉树由结点的有限集合构成:或者为空集或者由一个根结点及两棵不相交的分别称作这个根的左子树和右子树的二叉树(它们也是结点的集合)组成这是个递归的定义。二叉树可以是空集合，因此根可以有空的左子树或右子树，或者左右子树皆为空二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。ABCDEFGHK根结点左子树右子树EF二叉树的五种基本形态：N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子树均不为空树左右子树均不为空树满二叉树如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树123456789101112131415完全二叉树若一颗二叉树最多只有最下面的两层结点度数可以小于2最下面一层的结点都集中在该层最左边的连续位置上，则称此二叉树为完全二叉树。abcdefghij完全二叉树完全二叉树的特点是：其叶结点只可能在层次最大的两层出现完全二叉树中由根结点到各个结点的路径长度总和在具有同样结点个数的二叉树中达到了最小，即任意一棵二叉树中根结点到各结点的最长路径一定不短于结点数目相同的完全二叉树中的路径长度扩充二叉树当二叉树里出现空的子树时，就增加新的、特殊的结点——空树叶对于原来二叉树里度数为1的分支结点，在它下面增加一个空树叶对于原来二叉树的树叶，在它下面增加两个空树叶扩充的二叉树是满二叉树，新增加的空树叶(外部结点)的个数等于原来二叉树的结点(内部结点)个数加1扩充二叉树外部路径长度E从扩充的二叉树的根到每个外部结点的路径长度之和内部路径长度I扩充的二叉树里从根到每个内部结点的路径长度之和E和I两个量之间的关系为E=I+2n扩充二叉树63124971058例如，在图5.3这个有10个内部结点的扩充二叉树里E=3+4+4+3+4+4+3+4+4+3+3=39I=0+1+2+3+2+3+1+2+3+2=19E和I两个量之间的关系为E=I+2n。扩充二叉树证明：对内部结点数目进行归纳。当n=1时，I=0且E=2，故E=I+2n成立。对于有n个内部结点的扩充二叉树此等式已成立，即En=In+2n，现在考虑有n+1个内部结点的扩充二叉树删去一个有两个空树叶的分支结点，该分支结点与根结点的路径长度是K，使之成为有n个内部结点的扩充二叉树。由于删去了一个路径长度为K的内部结点，内部路径长度变为In=In+1-K；由于减少了两个路径长度为K+1的...
