第三节 二叉树的概念

第三节 二叉树的概念

一、二叉树的递归定义和基本形态
    1.二叉树是一种很重要的非线性数据结构，它的特点是每个结点最多有两个后继，且其子树有左右之分（次序不能任意颠倒）。
    2.二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件：
    ⑴ 有一个特定的结点称为根；
    ⑵ 余下的结点分为互不相交的子集L和R，其中L是根的左子树；R是根的右子树；L和R又是二叉树；
   由上述定义可以看出，二叉树和树是两个不同的概念:
    ⑴ 树的每一个结点可以有任意多个后继，而二叉树中每个结点的后继不能超过2；
    ⑵ 树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。我们称二叉树中结点的左后继为左儿子，右后继为右儿子。
    3.二叉树的五种基本形态

二、二叉树的两个特殊形态
   1.满二叉树：如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树。（例如下图(a)）可以验证具有n个叶结点的满二叉树共有2n-1个结点。
   2.完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树（例如下图(b)）
  
三、二叉树的三个主要性质
   性质1：在二叉树的第i（≥1）层上，最多有 2^i-1个结点。
   性质2：在深度为k(k≥1)的二叉树中最多有2^k-1个结点。
   性质3：在任何二叉树中，叶子结点数总比度为2的结点多1。

四、普通有序树转换成二叉树
   普通树为有序树T，将其转化成二叉树T’的规则如下：
    ⑴ T中的结点与T’中的结点一一对应，即T中每个结点的序号 和值在T’中保持不变；
    ⑵ T中某结点v的第一个儿子结点为v1，则在T’中v1为对应结点v的左儿子结点；
    ⑶ T中结点v的儿子序列，在T’中被依次链接成一条开始于v1的右链；
    由上述转化规则可以看出，一棵有序树转化成二叉树的根结点是没有右子树的，并且除保留每个结点的最左分支外，其余分支应去掉，然后从最左的儿子开始沿右儿子方向依次链接该结点的全部儿子。

五、森林转换成二叉树
    如果m棵互不相交的普遍有序树组成了森林F={T1，…Tm}。我们可以按下述规则将森林F转换成一棵二叉树b={R，LB，RB}：
    ⑴ 若F为空（m=0），则b为空树；
    ⑵ 若F非空（m≠0），则b的根R即为森林中第一棵树的根R(T1)；b的左子树LB是从T1的根结点的子树森林F1={T11，T12，…T1k}转换而成的二叉树；其右子树RB是从森林F2={T2，T3，…，Tm}转换成的二叉树。