4.3 二叉树★2◎4

4.3 二叉树★2◎4

　　1．二叉树的定义
　　二叉树是n(n≥0)个结点的集合，当n=0时，它是一棵空二叉树；当n>0时，它由一个根结点和两棵互不相交的二叉树（分别称为左子树和右子树）组成。和树相同，二叉树的定义也是递归的。
　　二叉树有5种基本形态，如图4-1所示，任何复杂的二叉树都是这5种基本形态的复合。

　　2．特殊二叉树
　　（1）满二叉树
　　在一棵二叉树中，如果所有分支结点都有左孩子结点和右孩子结点，并且叶子结点都集中在二叉树的最下一层，这样的二叉树称为满二叉树，如图4-2所示，可以对满二叉树结点进行连续编号，树根的编号为1，按照层数从小到大、同一层从左到右的次序进行，图4-2中结点右上方的数字是对该结点的编号。

　　（2）完全二叉树
　　若二叉树中最多只有最下面两层的结点度数可以小于2，并且最下面一层的叶子结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树，如图4-3所示。同样可以对完全二叉树中每个结点进行连续编号，编号的方法与满二叉树相同，图4-3中结点外边的数字为对该结点的编号。
　　其中，满二叉树是完全二叉树的一种特例，并且完全二叉树与高度相同的满二叉树对应位置结点有同一编号。
　　3．二叉树的性质
　　（1）对任何一棵二叉树而言，若叶子节点个数为，度为2的结点数为，则有：。
　　（2）在非空二叉树的第i层上至多有个结点（i≥1）。
　　（3）高度为h的二叉树至多有个结点（h≥1）。
　　（4）对完全二叉树中编号为i的结点（1≤i≤n，n≥1，其中n为结点数）而言：
　　若i=1，则结点i是二叉树的根，无双亲。
　　若i>1，则结点i的双亲是结点。
　　若2i>n，则结点i没有左孩子，否则左孩子是结点2i。
　　若2i+1>n，则节点i没有右孩子，否则右孩子是结点2i+1。
　　（5）具有n个结点（n>0）的完全二叉树的高度为。

　　4．二叉树的存储结构
　　（1）顺序存储结构
　　顺序存储结构就是用一组地址连续的存储单元来存放二叉树的数据元素。其中，结点的存放次序是：对该树中的每个结点进行编号，其编号从小到大的顺序就是结点存放在连续存储单元的先后次序。若把二叉树存储在一维数组中，其中数组的下标从1开始，对完全二叉树，只要按点编号i存储到相应位置即可；对于一般二叉树，需按完全二叉树的形式来存储，必须处理不存在的结点。
　　二叉树顺序存储结构的类型定义如下：
　　
　　根据二叉树的性质（4），二叉树顺序存储中各结点之间的关系可通过编号（存储位置）来确定。对于编号为i的结点（即第i个存储单元），其双亲结点的编号为；若存在左孩子结点，则左孩子结点的编号（下标）为2i；若存在右孩子结点，则右孩子结点的编号（下标）为2i+1。因此，访问每一个结点的双亲和左、右孩子结点（若有的话），都非常方便。
　　（2）链式存储结构
　　用二叉链表来表示二叉树称为链式存储结构，其中，每个结点包含三个域：数据域及左右指针域，结点结构如图4-4所示。

　　其中，data称为数据域，用于存储对应的数据元素；lchild与rchild分别称为左指针域和右指针域，分别用于存储左孩子结点和右孩子结点的位置，对应的节点类型定义如下：
　　
　　5．遍历二叉树
　　遍历一棵二叉树就是按某种次序系统地访问二叉树上所有结点，使每个结点恰好被访问一次。遍历运算的关键在于访问结点的次序，这种次序应保证二叉树上的每个结点均被访问一次且仅一次。
　　二叉树的遍历方法有以下3种：
　　（1）前序遍历（先根遍历，先序遍历）：首先访问根结点，然后按前序遍历根结点的左子树，再按前序遍历根结点的右子树。
　　（2）中序遍历（中根遍历）：首先按中序遍历根结点的左子树，然后访问根结点，再按中序遍历根结点的右子树。
　　（3）后序遍历（后根遍历，后序遍历）：首先按后序遍历根结点的左子树，然后按后序遍历根结点的右子树，再访问根结点。
　　对于一个表达式，可用一棵二叉树来表示。例如，表达式a*(b+c)-d/(e+f)的二叉树如图4-5所示。

　　对该二叉树分别按照先序、中序、后序访问，得到的序列分别为-*a+bc/d+ef（先序）、a*(b+c)-d/(e+f)（中序）、abc+*def+/-（后序）。
　　其中，先序序列称为表达式的前缀表示（波兰式），中序序列称为表达式的中缀表示，后序序列称为表达式的后缀表示（逆波兰式）。
　　6．线索二叉树
　　在二叉树中，并不是所有结点都有左右孩子，因此存在大量空指针。遍历二叉树的结果是一个结点的线性序列，所以可利用结点的空链域存放指向结点前驱和后继结点的指针，这种空链域称为线索。
　　由于遍历方式不同，产生的遍历序列也不相同，因此有以下规定：当某结点的左指针为空时，令该指针指向该结点的前驱结点，否则指向左子树；当某结点的右指针为空时，令该指针指向该结点的后继结点，否则指向右子树。为了区分指针指向的是孩子结点还是前驱和后继结点，需要改变结点的结构，加上两个标志域ltag与rtag，结点结构如图4-6所示。

　　
　　按照上述原则在二叉树的每个结点上加上线索的二叉树称做线索二叉树。对二叉树以某种方式遍历使其变成线索二叉树的过程称做线索化。
　　为便于设计，在线索二叉树中再增加一个头结点，该结点的data域为空，lchild指向无线索时的根结点，ltag为0；rchild指向按某种方式遍历二叉树时的最后一个结点，rtag为1。
　　同一棵二叉树的遍历方式不同，所得到的线索树也不同，二叉树有先序、中序和后序三种遍历方式，所以线索树也有先序线索二叉树、中序线索二叉树和后序线索二叉树三种。
　　线索二叉树的存储结构如下：
　　
　　在线索二叉树中，指针p所指结点前驱、后继算法求法如下：
　　（1）先序遍历线索二叉树
　　p所指结点前驱的求法：
　　 当p->ltag==THREAD时，前驱为p->lchild；
　　 当p->ltag==LINK时，需遍历才能求得前驱。
　　p所指结点后继的求法：
　　 当p->rtag==THREAD时，后继为p->rchild；
　　 当p->rtag==LINK时，若p->ltag==LINK，则后继为p->lchild；若p->ltag=THREAD，则后继为p->rchild。
　　（2）中序遍历线索二叉树
　　p所指结点前驱的求法：
　　 当p->ltag==THREAD时，前驱为p->lchild；
　　 当p->ltag==LINK时，前驱为p->lchild的最右下方结点。
　　p所指结点后继的求法：
　　 当p->rtag==THREAD时，后继为p->rchild；
　　 当p->rtag==LINK时，后继为p->rchild的最左下方结点。
　　（3）后序遍历线索二叉树
　　p所指结点前驱的求法：
　　 当p->ltag==THREAD时，前驱为p->lchild；
　　 当p->ltag==LINK时，若p->rtag==LINK，前驱为p->rchild；若p->rtag==THREAD，前驱为p->rchild。
　　p所指结点后继的求法：
　　 当p->rtag==THREAD时，后继为p->rchild；
　　 当p->rtag==LINK时，需遍历才能求得后继。