数据结构第六章：二叉树

Abstract：二叉树。

6.1 二叉树的定义域性质

6.1.1 二叉树的基本概念

1.二叉树Binary Tree

• 有限个元素的集合，集合或为空、或由一个称为根（root）的元素和2个不想交的、被分别称为左子树和右子树的二叉树组成
• 结点：一个元素称为一个结点
• 有序：即左右子树颠倒即成为不同的二叉树；即使树中只有一棵子树也要区分
• 5种基本形态：

2.二叉树的相关概念

• 结点的度：结点拥有的子树个数
• 叶节点：度=0的结点，或称终端结点
• 分枝结点：度不为0的结点；除叶节点外的节点都是分支结点
• 左孩子，右孩子，双亲，兄弟
• 路径，路径长度：结点到结点所要经过的边数；eg.如果一棵树的一串结点n1,n2,…,nk 有如下关系：结点ni 是ni+1的父结点（1≤i<k）,就把n1,n2,…,nk 称为一条由n1 至nk 的路径。这条路径的长度是k-1
• 祖先、子孙：在树中，如果有一条路径从结点M 到结点N，那么M 就称为N的祖先，而N 称为M 的子孙
• 结点的层数：规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。
• 树的深度。树中所有结点的最大层数称为树的深度。
• 树的度。树中各结点度的最大值称为该树的度。
• 满二叉树：所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上。
• 完全二叉树：一棵深度为k 的有n 个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i 的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。

6.1.2 二叉树的主要性质

性质1：一棵非空二叉树的第i 层上最多有2i-1 个结点（i≥1）

性质2：一棵深度为k 的二叉树中，最多具有2k－1 个结点

性质3：对于一棵非空的二叉树，如果叶子结点数为n0，度数为2 的结点数为n2，则有: n0＝n2＋1。

性质4：具有n个结点的完全二叉树的深度k = [log2n + 1]（2为下标）

性质5：对于具有n 个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1 开始顺序编号，则对于任意的序号为i 的结点，有：

• （1）如果i>1，则序号为i 的结点的双亲结点的序号为i/2(“/”表示整除)；如果i＝1，则序号为i 的结点是根结点，无双亲结点。
• （2）如果2i≤n，则序号为i 的结点的左孩子结点的序号为2i；如果2i>n，则序号为i 的结点无左孩子。
• （3）如果2i＋1≤n，则序号为i 的结点的右孩子结点的序号为2i＋1；如果2i＋1>n，则序号为i 的结点无右孩子。

性质6：若对二叉树的根结点从0 开始编号，则相应的i 号结点的双亲结点的编号为（i -1）/2，左孩子的编号为2i＋1，右孩子的编号为2i＋2。

6.2 基本操作与存储—二叉树的存储

1.顺序存储结构

顺序存储：用一组连续的存储单元存放二叉树的结点，顺序为从上至下，从左至右。

• 一般的二叉树：数组元素下标的关系不能反映二叉树结点间的逻辑关系（结点在存储位置上的前驱后继关系并不一定就是它们在逻辑上的邻接关系），只有增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储（先增加空节点，再存储）。
• 完全二叉树和满二叉树：可以反映

改造：空间浪费；最坏的情况是右单支树，如图：一棵深度为k 的右单支树，只有k 个结点，却需分配2k－1 个存储单元。

2.链式存储结构

二叉树的链式存储：链表表示二叉树，链指示元素的逻辑关系。

(1) 二叉链表存储【最常用】

结点：三个域组成，数据域+指针域（分别指向该结点左孩子和右孩子所在结点的存储地址）

data域：存放结点的数据信息；lchild 与rchild 分别存放指向左孩子和右孩子的指针，当左孩子或右孩子不存在时，相应指针域值为空（用符号∧或NULL 表示）

描述：

typedef struct BiTNode{
    elemtype data;
    struct BiTNode *lchild; *rchild;
    }BiTNode, *BiTree; // 将BiTree 定义为指向二叉链表结点结构的指针类型

(2) 三叉链表存储

每个结点四个域。

• parent 域为指向该结点双亲结点的指针
• 优点：便于寻找孩子结点和双亲
• 缺点：增加空间开销

6.2 基本操作与存储—二叉树的基本操作及实现

1.二叉树的基本操作

• initiate(bt): 建立一棵空二叉树
• create（x，lbt，rbt）：生成一棵以x为根结点的数据域信息，以二叉树lbt和rbt为左子树和右子树的二叉树
• Insert（bt，x，parent）：将数据域信息为x 的结点插入到二叉树bt 中作为结点parent 的左孩子结点。如果结点parent 原来有左孩子结点，则将结点parent 原来的左孩子结点作为结点x 的左孩子结点。
• InsertR（bt，x，parent）将数据域信息为x 的结点插入到二叉树bt 中作为结点parent 的右孩子结点。如果结点parent 原来有右孩子结点，则将结点parent 原来的右孩子结点作为结点x 的右孩子结点。
• DeleteL（bt，parent）在二叉树bt 中删除结点parent 的左子树。
• DeleteR（bt，parent）在二叉树bt 中删除结点parent 的右子树。
• Search（bt，x）在二叉树bt 中查找数据元素x。
• Traverse（bt）按某种方式遍历二叉树bt 的全部结点。

2．算法的实现——基于二叉链表

1.Initiate（bt）初始建立二叉树bt，并使bt 指向头结点。在二叉树根结点前建立头结点，就如同在单链表前建立的头结点，可以方便后边的一些操作实现。

int Initiate (BiTree *bt)
{/*初始化建立二叉树*bt 的头结点*/
if((*bt=(BiTNode *)malloc(sizeof(BiTNode)))==NULL)
    return 0;
*bt->lchild=NULL;
*bt->rchild=NULL;
return 1;
}

2.Create（x，lbt，rbt）建立一棵以x 为根结点的数据域信息，以二叉树lbt 和rbt为左右子树的二叉树。建立成功时返回所建二叉树结点的指针；建立失败时返回空指针。

BiTree Create（elemtype x，BiTree lbt，BiTree rbt）
{/*生成一棵以x 为根结点的数据域值以lbt 和rbt 为左右子树的二叉树*/
BiTree p;
if ((p=(BiTNode *)malloc(sizeof(BiTNode)))==NULL) return NULL;
    p->data=x;
    p->lchild=lbt;
    p->rchild=rbt;
return p;
}

3.InsertL（bt，x，parent）

BiTree InsertL（BiTree bt，elemtype x，BiTree parent）
{/*在二叉树bt 的结点parent 的左子树插入结点数据元素x*/
BiTree p;
if (parent==NULL)
{ printf(“\n 插入出错”)；
return NULL;
}
if ((p=(BiTNode *)malloc(sizeof(BiTNode)))==NULL) return NULL;
    p->data=x;
    p->lchild=NULL;
    p->rchild=NULL;
if (parent->lchild==NULL) parent->lchild=p;
    else {p->lchild=parent->lchild;
    parent->lchild=p;
}
return bt;
}

4.DeleteL（bt，parent）在二叉树bt 中删除结点parent 的左子树。当parent 或parent的左孩子结点为空时删除失败。删除成功时返回根结点指针；删除失败时返回空指针。

BiTree DeleteL（BiTree bt，BiTree parent）
{/*在二叉树bt 中删除结点parent 的左子树*/
BiTree p;
if (parent==NULL||parent->lchild==NULL)
{ printf(“\n 删除出错”)；
return NULL’
}
    p=parent->lchild;
    parent->lchild=NULL;
    free(p); /*当p 为非叶子结点时，这样删除仅释放了所删子树根结点的空间，*/
/*若要删除子树分支中的结点，需用后面介绍的遍历操作来实现。*/
return br;
}

6.3 二叉树的遍历—二叉树的遍历方法及递归实现

二叉树的遍历:

• 指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。
• 若以D、L、R分别访问根结点、遍历根结点的左子树、遍历根结点的右子树，则二叉树的遍历方式有六种：DLR、LDR、LRD、DRL、RDL 和RLD。如果限定先左后右，则只有前三种方式，即DLR（称为先序遍历）、LDR（称为中序遍历）和LRD（称为后序遍历）。

1.先序遍历DLR

先序遍历的递归过程：若二叉树为空，遍历结束。否则：

• 访问根结点
• 先序遍历根结点的左子树
• 先序遍历根结点的右子树

递归算法：

void PreOrder(BiTree bt)
{
if (bt == NULL) return;
    Visite (bt->data); //遍历bt二叉树的数据域
    PreOrder (bt->lchild);//preorder指先序
    PreOrder (bt->rchild);
}

对上图b先序遍历：A-B-D-G-C-E-F(从根结点开始，先左后右)

2.中序遍历LDR

递归过程：若二叉树为空，遍历结束。否则：

• 中序遍历根结点的左子树
• 访问根结点
• 中序遍历根结点的右子树

递归算法：

void InOrder (BiTree bt)
{/*中序遍历二叉树bt*/
if (bt==NULL) return; /*递归调用的结束条件*/
InOrder（bt->lchild）; /*中序递归遍历bt 的左子树*/
Visite（bt->data）; /*访问结点的数据域*/
InOrder（bt->rchild）; /*中序递归遍历bt 的右子树*/
}

对上图b中序：D-G-B-A-C-E-F（从左子树开始）

3.后序遍历LRD

递归：若二叉树为空，遍历结束。否则，

（1）后序遍历根结点的左子树；
（2）后序遍历根结点的右子树。
（3）访问根结点；

算法：

void PostOrder（BiTree bt）
{/*后序遍历二叉树bt*/
if (bt==NULL) return; /*递归调用的结束条件*/
        PostOrder（bt->lchild）; /*后序递归遍历bt 的左子树*/
        PostOrder（bt->rchild）; /*后序递归遍历bt 的右子树*/
        Visite（bt->data）; /*访问结点的数据域*/
}

对图b后序：G-D-B-E-F-C-A

4.层次遍历

从根结点出发，由上至下由左至右逐个访问结点。如图b：A-B-C-D-E-F-G

算法：

在进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从对头取出一个元素，每取一个元素，执行下面两个操作：

• （1）访问该元素所指结点；
• （2）若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。

此过程不断进行，当队列为空时，二叉树的层次遍历结束。在下面的层次遍历算法中，二叉树以二叉链表存放，一维数组Queue[MAXNODE]用以实现队列，变量front 和rear 分别表示当前对首元素和队尾元素在数组中的位置。

void LevelOrder （ BiTree bt
/*层次遍历二叉树bt*/
{ BiTree	Queue[MAXNODE];
  int		front, rear;
  if ( bt == NULL )
	  return;
  front		= -1;
  rear		= 0;
  queue[rear]	= bt;
  while ( front != rear )
  {
	  front++;
	  Visite( queue[front]->data );         /*访问队首结点的数据域*/
	  if ( queue[front]->lchild != NULL )   /*将队首结点的左孩子结点入队列*/
	  {
		  rear++;
		  queue[rear] = queue[front]->lchild;
	  }
	  if ( queue[front]->rchild != NULL )   /*将队首结点的右孩子结点入队列*/
	  {
		  rear++;
		  queue[rear] = queue[front]->rchild;
	  }
  }
}

6.3 二叉树的遍历—二叉树遍历的非递归实现

为什么要用非递归实现？

• 并非所有程序设计语言都允许递归；
• 递归程序虽然简洁，但可读性一般不好，执行效率也不高。
• 因此，就存在如何把一个递归算法转化为非递归算法的问题。解决这个问题的方法可以通过对三种遍历方法的实质过程的分析得到。

先序遍历是在深入时遇到结点就访问，中序遍历是在从左子树返回时遇到结点访问，后序遍历是在从右子树返回时遇到结点访问。

在这一过程中，返回结点的顺序与深入结点的顺序相反，即后深入先返回，正好符合栈结构后进先出的特点。因此，可以用栈来帮助实现这一遍历路线。其过程如下。在沿左子树深入时，深入一个结点入栈一个结点，若为先序遍历，则在入栈之前访问之；当沿左分支深入不下去时，则返回，即从堆栈中弹出前面压入的结点，若为中序遍历，则此时访问该结点，然后从该结点的右子树继续深入；若为后序遍历，则将此结点再次入栈，然后从该结点的右子树继续深入，与前面类同，仍为深入一个结点入栈一个结点，深入不下去再返回，直到第二次从栈里弹出该结点，才访问之。

先序遍历的非递归实现

下面算法：二叉树以二叉链表存放，一维数组stack[MAXNODE]实现栈，变量top表示当前栈顶的位置。

void NRPreOrder (BiTree bt)
BiTree stack[MAXNODE],p;
int top;
if (bt==NULL) return;
top=0;
p=bt;
while(!(p==NULL&&top==0))
{ while(p!=NULL)
{ Visite(p->data); /*访问结点的数据域*/
if (top<MAXNODE-1) /*将当前指针p 压栈*/
{ stack[top]=p;
top++;
}
else { printf(“栈溢出”)；
return；
}
p=p->lchild； /*指针指向p 的左孩子*/
}
if (top<=0) return; /*栈空时结束*/
else{ top--;
p=stack[top]; /*从栈中弹出栈顶元素*/
p=p->rchild; /*指针指向p 的右孩子结点*/
}
}
}

对图b的二叉树，用上算法遍历，栈stack 和当前指针p 的变化情况以及树中各结点的访问次序如表所示。

中序遍历的非递归实现

中序遍历的非递归算法的实现，只需将先序遍历的非递归算法中的Visite(p->data)移到p=stack[top]和p=p->rchild 之间即可。

后序遍历的非递归实现

由前面的讨论可知，后序遍历与先序遍历和中序遍历不同，在后序遍历过程中，结点在第一次出栈后，还需再次入栈，也就是说，结点要入两次栈，出两次栈，而访问结点是在第二次出栈时访问。因此，为了区别同一个结点指针的两次出栈，设置一标志flag，令：

当结点指针进、出栈时，其标志flag 也同时进、出栈。因此，可将栈中元素的数据类型定义为指针和标志flag 合并的结构体类型。定义如下：

typedef struct {
BiTree link;
int flag;
}stacktype;

后序遍历二叉树的非递归算法如下。在算法中，一维数组stack[MAXNODE]用于实现栈的结构，指针变量p 指向当前要处理的结点，整型变量top 用来表示当前栈顶的位置，整型变量sign 为结点p 的标志量。

void NRPostOrder( BiTree bt )
/*非递归后序遍历二叉树bt*/
{
	stacktype	stack[MAXNODE];
	BiTree		p;
	int		top, sign;
	if ( bt == NULL )
		return;
	top		= -1                                    /*栈顶位置初始化*/
		  p	= bt;
	while ( !(p == NULL && top == -1) )
	{
		if ( p != NULL )                                /*结点第一次进栈*/
		{
			top++;
			stack[top].link = p;
			stack[top].flag = 1;
			p		= p->lchild;            /*找该结点的左孩子*/
		}else  { p	= stack[top].link;
			 sign	= stack[top].flag;
			 top--;
			 if ( sign == 1 )                       /*结点第二次进栈*/
			 {
				 top++;
				 stack[top].link	= p;
				 stack[top].flag	= 2;    /*标记第二次出栈*/
				 p			= p->rchild;
			 }else  { Visite( p->data );            /*访问该结点数据域值*/
			 } }
	}
}

6.3 二叉树的遍历—由遍历序列恢复二叉树

1.任何二叉树的先序和中序序列唯一，则可由其先序中序序列确定唯一的二叉树。

2.由二叉树的后序序列和中序序列也可唯一地确定一棵二叉树。

因为，依据后序遍历和中序遍历的定义，后序序列的最后一个结点，就如同先序序列的第一个结点一样，可将中序序列分成两个子序列，分别为这个结点的左子树的中序序列和右子树的中序序列，再拿出后序序列的倒数第二个结点，并继续分割中序序列，如此递归下去，当倒着取取尽后序序列中的结点时，便可以得到一棵二叉树。

已知一棵二叉树的先序序列与中序序列分别为：

A B C D E F G H I
B C A E D G H F I

试恢复该二叉树。

首先，由先序序列可知，结点A 是二叉树的根结点。其次，根据中序序列，在A 之前的所有结点都是根结点左子树的结点，在A 之后的所有结点都是根结点右子树的结点，由此得到图6.10 (a)所示的状态。然后，再对左子树进行分解，得知B 是左子树的根结点，又从中序序列知道，B 的左子树为空，B 的右子树只有一个结点C。接着对A 的右子树进行分解，得知A 的右子树的根结点为D；而结点D 把其余结点分成两部分，即左子树为E，右子树为F、G、H、I，如图6.10 (b)所示。接下去的工作就是按上述原则对D 的右子树继续分解下去，最后得到如图6.10 (c)的整棵二叉树。

上述过程是一个递归过程，其递归算法的思想是：先根据先序序列的第一个元素建立根结点；然后在中序序列中找到该元素，确定根结点的左、右子树的中序序列；再在先序序列中确定左、右子树的先序序列；最后由左子树的先序序列与中序序列建立左子树，由右子树的先序序列与中序序列建立右子树。下面给出用C 语言描述的该算法。假设二叉树的先序序列和中序序列分别存放在一维数组preod[ ]与inod[ ]中，并假设二叉树各结点的数据值均不相同。

void ReBiTree（char preod[ ],char inod[ ],int n,BiTree root）
/*n 为二叉树的结点个数，root 为二叉树根结点的存储地址*/
{ if (n≤0) root=NULL;
else PreInOd(preod,inod,1,n,1,n,&root);
}

void PreInOd（char preod[ ],char inod[ ],int i,j,k,h,BiTree *t）
{* t=(BiTNode *)malloc(sizeof(BiTNode));
*t->data=preod[i];
m=k;
while (inod[m]!=preod[i]) m++;
if (m==k) *t->lchild=NULL
else PreInOd(preod,inod,i+1,i+m-k,k,m-1,&t->lchild);
if (m==h) *t->rchild=NULL
else PreInOd(preod,inod,i+m-k+1,j,m+1,h,&t->rchild);
}

注：数组preod 和inod 的元素类型可根据实际需要来设定，这里设为字符型。另外，如果只知道二叉树的先序序列和后序序列，则不能唯一地确定一棵二叉树。

6.3 二叉树的遍历—不用栈的二叉树遍历的非递归方法

二叉树的遍历算法：

• 依据二叉树结构的递归性，采用递归调用的方式来实现
• 通过堆栈或队列来辅助实现

缺点：递归调用和栈都增加额外空间。

递归调用的深度与栈的大小是动态变化的，都与二叉树的高度有关。因此，在最坏的情况下，即二叉树退化为单支树的情况下，递归的深度或栈需要的存储空间等于二叉树中的结点数。

常用的不用栈的二叉树遍历的非递归方法有以下三种：

• 用三叉链表存放二叉树：即在二叉树的每个结点中增加一个双亲域parent，这样，在遍历深入到不能再深入时，可沿着走过的路径回退到任何一棵子树的根结点，并再向另一方向走。由于这一方法的实现是在每个结点的存储上又增加一个双亲域，故其存储开销就会增加。
• 逆转链：在遍历深入时，每深入一层，就将其再深入的孩子结点的地址取出，并将其双亲结点的地址存入，当深入不下去需返回时，可逐级取出双亲结点的地址，沿原路返回。虽然此种方法是在二叉链表上实现的，没有增加过多的存储空间，但在执行遍历的过程中改变子女指针的值，这既是以时间换取空间，同时当有几个用户同时使用这个算法时将会发生问题。
• 在线索二叉树上的遍历：利用具有n 个结点的二叉树中的叶子结点和一度结点的n＋1 个空指针域，来存放线索，然后在这种具有线索的二叉树上遍历时，就可不需要栈，也不需要递归了。

6.4 线索二叉树—线索二叉树的定义及结构

1.线索二叉树的定义

线索二叉树：带了线索的二叉树。线索thread：指向直接前驱结点和指向直接后继结点的指针。

为了保留结点在某种遍历序列中直接前驱和直接后继的位置信息，可以利用二叉树的二叉链表存储结构中的那些空指针域来指示。

2.线索二叉树的结构

一个具有n 个结点的二叉树若采用二叉链表存储结构，在2n 个指针域中只有n－1 个指针域是用来存储结点孩子的地址，而另外n＋1 个指针域存放的都是NULL。因此，可以利用某结点空的左指针域（lchild）指出该结点在某种遍历序列中的直接前驱结点的存储地址，利用结点空的右指针域（rchild）指出该结点在某种遍历序列中的直接后继结点的存储地址；对于那些非空的指针域，则仍然存放指向该结点左、右孩子的指针。这样，就得到了一棵线索二叉树。

序列可由不同的遍历方法得到。线索树有先序线索二叉树、中序线索二叉树和后序线索二叉树三种。把二叉树改造成线索二叉树的过程称为线索化。

对图b进行线索化：得到先序线索二叉树、中序线索二叉树和后序线索二叉树分别如图(a)、(b)、(c)所示。图中实线表示指针，虚线表示线索。

如何区别某结点的指针域内存放的是指针还是线索？

（1）为每个结点增设两个标志位域ltag 和rtag，令：

这里我们按第一种方法来介绍线索二叉树的存储。为了将二叉树中所有空指针域都利用上，以及操作便利的需要，在存储线索二叉树时往往增设一头结点，其结构与其它线索二叉树的结点结构一样，只是其数据域不存放信息，其左指针域指向二叉树的根结点，右指针域指向自己。而原二叉树在某序遍历下的第一个结点的前驱线索和最后一个结点的后继线索都指向该头结点。

6.4 线索二叉树—线索二叉树的基本操作实现

线索二叉树的结点结构：

typedef char elemtype;
typedef struct BiThrNode {
	elemtype		data;
	struct BiThrNode	*lchild;
	struct BiThrNode	*rchild;
	unsigned		ltag : 1;
	unsigned		rtag : 1;
}BiThrNodeType, *BiThrTree;

下面以中序线索二叉树为例，讨论线索二叉树的建立、线索二叉树的遍历以及在线索二叉树上查找前驱结点、查找后继结点、插入结点和删除结点等操作的实现算法。

1.建立一棵中序线索二叉树

建立线索二叉树/线索化：

• 实质：遍历一棵二叉树
• 遍历过程中：访问结点的操作是检查当前结点的左、右指针域是否为空，若空，则将其改为指向前驱结点或后继结点的线索。为实现这一过程，设指针pre始终指向刚访问过的结点，即若指针p指向当前结点，则pre指向当前结点，则pre指向它的前驱，以便增设线索。
• 对二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的根结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。

递归算法：其中pre为全局变量

//算法1
int InOrderThr( BiThrTree *head, BiThrTree T )
{                                                       /*中序遍历二叉树T，并将其中序线索化，*head 指向头结点。*/
	if ( !(*head = (BiThrNodeType *) malloc( sizeof(BiThrNodeType) ) ) )
		return(0);
	(*head)->ltag	= 0; (*head)->rtag = 1;         /*建立头结点*/
	(*head)->rchild = *head;                        /*右指针回指*/
	if ( !T )
		(*head)->lchild = *head;                /*若二叉树为空，则左指针回指*/
	else { (*head)->lchild = T; pre = head;
	       InThreading( T );                        /*中序遍历进行中序线索化*/
	       pre->rchild	= *head; pre->rtag = 1; /*最后一个结点线索化*/
	       (*head)->rchild	= pre; }
	return(1);
}

//算法2
void InTreading( BiThrTree p )
{                                               /*中序遍历进行中序线索化*/
	if ( p )
	{
		InThreading( p->lchild );       /*左子树线索化*/
		if ( !p->lchild )               /*前驱线索*/
		{
			p->ltag = 1; p->lchild = pre;
		}
		if ( !pre->rchild )             /*后继线索*/
		{
			pre->rtag = 1; pre->rchild = p;
		}
		pre = p;
		InThreading( p->rchild );       /*右子树线索化*/
	}
}

2.在中序线索二叉树上查找任意结点的中序前驱结点

对于中序线索二叉树上的任一结点，寻找其中序的前驱结点，有以下两种情况：

（1）如果该结点的左标志为1，那么其左指针域所指向的结点便是它的前驱结点；

（2）如果该结点的左标志为0，表明该结点有左孩子，根据中序遍历的定义，它的前驱结点是以该结点的左孩子为根结点的子树的最右结点，即沿着其左子树的右指针链向下查找，当某结点的右标志为1 时，它就是所要找的前驱结点。

在中序线索二叉树上寻找结点p 的中序前驱结点的算法如下：

BiThrTree InPreNode（BiThrTree p）
{/*在中序线索二叉树上寻找结点p 的中序前驱结点*/
BiThrTree pre;
pre=p->lchild;
if (p->ltag!=1)
    while (pre->rtag==0) pre=pre->rchild;
    return(pre);
}

3.在中序线索二叉树上查找任意结点的先序后继结点

这一操作的实现依据是：若一个结点是某子树在中序下的最后一个结点，则它必是该子树在先序下的最后一个结点。该结论可以用反证法证明。

下面就依据这一结论，讨论在中序线索二叉树上查找某结点在先序下后继结点的情况。设开始时，指向此某结点的指针为p。

（1）若待确定先序后继的结点为分支结点，则又有两种情况：
① 当p->ltag=0 时，p->lchild 为p 在先序下的后继；
② 当p->ltag=1 时，p->rchild 为p 在先序下的后继。

（2）若待确定先序后继的结点为叶子结点，则也有两种情况：
① 若p->rchild 是头结点，则遍历结束；
② 若p->rchild 不是头结点，则p 结点一定是以p->rchild 结点为根的左子树中在中序遍历下的最后一个结点，因此p 结点也是在该子树中按先序遍历的最后一个结点。此时， 若p->rchild 结点有右子树， 则所找结点在先序下的后继结点的地址为p->rchild->rchild；若p->rchild 为线索，则让p＝p->rchild，反复情况（2）的判定。

在中序线索二叉树上寻找结点p 的先序后继结点的算法如下：

BiThrTree IPrePostNode（BiThrTree head,BiThrTree p）
{/*在中序线索二叉树上寻找结点p 的先序的后继结点,head 为线索树的头结点*/
BiThrTree post;
if (p->ltag==0) post=p->lchild;
else { post=p;
while (post->rtag==1&&post->rchild!=head) post=post->rchild;
post=post->rchild;
}
return(post);
}

4.在中序线索二叉树上查找值为x的结点

利用在中序线索二叉树上寻找后继结点和前驱结点的算法，就可以遍历到二叉树的所有结点。比如，先找到按某序遍历的第一个结点，然后再依次查询其后继；或先找到按某序遍历的最后一个结点，然后再依次查询其前驱。这样，既不用栈也不用递归就可以访问到二叉树的所有结点。

在中序线索二叉树上查找值为x 的结点，实质上就是在线索二叉树上进行遍历，将访问结点的操作具体写为那结点的值与x 比较的语句。下面给出其算法：

BiThrTree Search (BiThrTree head,elemtype x)
{/*在以head 为头结点的中序线索二叉树中查找值为x 的结点*/
BiThrTree p;
p=head->lchild;
while (p->ltag==0&&p!=head) p=p->lchild;
while(p!=head && p->data!=x) p=InPostNode(p);
if (p==head)
{ printf(“Not Found the data!\n”);
return(0);
}
else return(p);
}

5.在中序线索二叉树上查找任意结点在后序下的前驱

这一操作的实现依据是：若一个结点是某子树在中序下的第一个结点，则它必是该子树在后序下的第一个结点。该结论可以用反证法证明。

下面就依据这一结论，讨论在中序线索二叉树上查找某结点在后序下前驱结点的情况。设开始时，指向此某结点的指针为p。

（1）若待确定后序前驱的结点为分支结点，则又有两种情况：
① 当p->ltag=0 时，p->lchild 为p 在后序下的前驱；
② 当p->ltag=1 时，p->rchild 为p 在后序下的前驱。

（2）若待确定后序前驱的结点为叶子结点，则也有两种情况：
① 若p->lchild 是头结点，则遍历结束；
② 若p->lchild 不是头结点，则p 结点一定是以p->lchild 结点为根的右子树中在中中序遍历下的第一个结点，因此p 结点也是在该子树中按后序遍历的第一个结点。此时，若p->lchild 结点有左子树， 则所找结点在后序下的前驱结点的地址为p->lchild->lchild；若p->lchild 为线索，则让p＝p->lchild，反复情况（2）的判定。

在中序线索二叉树上寻找结点p 的后序前驱结点的算法如下：

BiThrTree IPostPretNode（BiThrTree head,BiThrTree p）
{/*在中序线索二叉树上寻找结点p 的先序的后继结点，head 为线索树的头结点*/
BiThrTree pre;
if (p->rtag==0) pre=p->rchild;
else { pre=p;
while (pre->ltag==1&& post->rchild!=head) pre=pre->lchild;
pre=pre->lchild;
}
return(pre);
}

6.在中序线索二叉树上查找值为x的结点

利用在中序线索二叉树上寻找后继结点和前驱结点的算法，就可以遍历到二叉树的所有结点。比如，先找到按某序遍历的第一个结点，然后再依次查询其后继；或先找到按某序遍历的最后一个结点，然后再依次查询其前驱。这样，既不用栈也不用递归就可以访问到二叉树的所有结点。

在中序线索二叉树上查找值为x 的结点，实质上就是在线索二叉树上进行遍历，将访问结点的操作具体写为那结点的值与x 比较的语句。下面给出其算法：

BiThrTree Search (BiThrTree head,elemtype x)
{/*在以head 为头结点的中序线索二叉树中查找值为x 的结点*/
BiThrTree p;
p=head->lchild;
while (p->ltag==0&&p!=head) p=p->lchild;
while(p!=head && p->data!=x) p=InPostNode(p);
if (p==head)
{ printf(“Not Found the data!\n”);
return(0);
}
else return(p);
}

7.在中序线索二叉树上的更新

线索二叉树的更新是指，在线索二叉树中插入一个结点或者删除一个结点。一般情况下，这些操作有可能破坏原来已有的线索，因此，在修改指针时，还需要对线索做相应的修改。一般来说，这个过程的代价几乎与重新进行线索化相同。这里仅讨论一种比较简单的情况，即在中序线索二叉树中插入一个结点p，使它成为结点s 的右孩子。

下面分两种情况来分析：

（1）若s 的右子树为空，如图6.13 (a)所示，则插入结点p 之后成为图6.13 (b)所示的情形。在这种情况中，s 的后继将成为p 的中序后继，s 成为p 的中序前驱，而p 成为s 的右孩子。二叉树中其它部分的指针和线索不发生变化。

（2）若s 的右子树非空，如图6.14 (a)所示，插入结点p 之后如图6.14 (b)所示。S 原来的右子树变成p 的右子树，由于p 没有左子树，故s 成为p 的中序前驱，p 成为s 的右孩子；又由于s 原来的后继成为p 的后继，因此还要将s 原来的本来指向s 的后继的左线索，改为指向p。

下面给出上述操作的算法。

void InsertThrRight(BiThrTree s,BiThrTree p)
{/*在中序线索二叉树中插入结点p 使其成为结点s 的右孩子*/
BiThrTree w;
p->rchild=s->rchild;
p->rtag=s->rtag;
p->lchild=s;
p->ltag=1; /*将s 变为p 的中序前驱*/
s->rchild=p;
s->rtag=0; /*p 成为s 的右孩子*/
if(p->rtag==0) /*当s 原来右子树不空时，找到s 的后继w，变w 为p 的后继，p 为w 的前驱*/
{ w=InPostNode(p);
w->lchild=p;
}
}

6.5 二叉树的应用—二叉树遍历的应用

Viste（bt->data）：访问结点的数据域信息。即根据具体问题，对bt数据进行不同操作。

几个遍历操作的典型应用：

1.查找数据元素

search (bt, x): 在bt为二叉树的根结点指针的二叉树中查找数据元素x。查找成功时返回该结点的指针；失败则返回空指针。

算法：

//注意遍历算法中的Visite(bt->data)等同于其中的一组操作步骤。

BiTree Search（BiTree bt，elemtype x）
{/*在bt 为根结点指针的二叉树中查找数据元素x*/
BiTree p;
if (bt->data==x) 
    return bt; /*查找成功返回*/
if (bt->lchild!=NULL) 
    return(Search(bt->lchild,x));
/*在bt->lchild 为根结点指针的二叉树中查找数据元素x*/
if (bt->rchild!=NULL) 
    return(Search(bt->rchild,x));
/*在bt->rchild 为根结点指针的二叉树中查找数据元素x*/
    return NULL; /*查找失败返回*/
}

2.统计出给定二叉树中叶子结点的数目

1）顺序存储结构的实现

int CountLeaf1（SqBiTree bt，int k）
{/*一维数组bt[2k-1]为二叉树存储结构，k 为二叉树深度，函数值为叶子数。*/
total=0;
for(i=1;i<=2k-1;i++)
{ if (bt[i]!=0)
{ if ((bt[2i]==0 && bt[2i+1]==0) || (i>(2k-1)/2))
total++;
}
}
return(total);
}

（2）二叉链表存储结构的实现

int CountLeaf2（BiTree bt）
{/*开始时，bt 为根结点所在链结点的指针，返回值为bt 的叶子数*/
if (bt==NULL) return(0);
if (bt->lchild==NULL && bt->rchild==NULL) return(1);
return(CountLeaf2(bt->lchild)+CountLeaf2(bt->rchild));
}

3.创建二叉树二叉链表存储，并显示

设创建时，按二叉树带空指针的先序次序输入结点值，结点值类型为字符型。输出按中序。

CreateBinTree（BinTree *bt）是以二叉链表为存储结构建立一棵二叉树T 的存储，bt为指向二叉树T 根结点指针的指针。设建立时的输入序列为：AB0D00CE00F00。建立如图6.3 (b)所示的二叉树存储。

InOrderOut（bt）为按中序输出二叉树bt 的结点。算法实现如下，注意在创建算法中，遍历算法中的Visite(bt->data)被读入结点、申请空间存储的操作所代替；在输出算法中，遍历算法中的Visite(bt->data)被c 语言中的格式输出语句所代替。

void CreateBinTree(BinTree *T)
{/*以加入结点的先序序列输入，构造二叉链表*/
char ch;
scanf("\n%c",&ch);
if (ch=='0') *T=NULL; /*读入0 时，将相应结点置空*/
else {*T=(BinTNode*)malloc(sizeof(BinTNode)); /*生成结点空间*/
(*T)->data=ch;
CreateBinTree(&(*T)->lchild); /*构造二叉树的左子树*/
CreateBinTree(&(*T)->rchild); /*构造二叉树的右子树*/
}
}
void InOrderOut(BinTree T)
{/*中序遍历输出二叉树T 的结点值*/
if (T)
{ InOrderOut(T->lchild); /*中序遍历二叉树的左子树*/
printf("%3c",T->data); /*访问结点的数据*/
InOrderOut(T->rchild); /*中序遍历二叉树的右子树*/
}
}
main()
{BiTree bt;
CreateBinTree(&bt);
InOrderOut(bt);
}

4.表达式运算

我们可以把任意一个算数表达式用一棵二叉树表示，图6.15 所示为表达式3x2+x-1/x+5的二叉树表示。在表达式二叉树中，每个叶结点都是操作数，每个非叶结点都是运算符。对于一个非叶子结点，它的左、右子树分别是它的两个操作数。

对该二叉树分别进行先序、中序和后序遍历，可以得到表达式的三种不同表示形式。

前缀表达式+-+3xxx/1x5
中缀表达式3xx+x-1/x+5
后缀表达式3xx**x+1x/-5+

6.5 二叉树的应用—最优二叉树(哈夫曼树)

1.哈夫曼树的基本概念

最优二叉树：对一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。

路径长度：根结点到所有叶结点的路径长度之和。

带权路径长度：从根结点到各个叶结点的路径长度与相应结点权值的乘积之和。

其中Wk 为第k 个叶结点的权值，Lk 为第k 个叶结点的路径长度。如图所示的二叉树，它的带权路径长度值WPL＝2×2＋4×2＋5×2＋3×2＝28。

给定一组具有确定权值的叶结点，可以构造出不同的带权二叉树。例如，给出4 个叶结点，设其权值分别为1，3，5，7，我们可以构造出形状不同的多个二叉树。这些形状不同的二叉树的带权路径长度将各不相同。

这五棵树的带权路径长度分别为：
（a）WPL＝1×2＋3×2＋5×2＋7×2＝32
（b）WPL＝1×3＋3×3＋5×2＋7×1＝29
（c）WPL＝1×2＋3×3＋5×3＋7×1＝33
（d）WPL＝7×3＋5×3＋3×2＋1×1＝43
（e）WPL＝7×1＋5×2＋3×3＋1×3＝29

由此可见，由相同权值的一组叶子结点所构成的二叉树有不同的形态和不同的带权路径长度，那么如何找到带权路径长度最小的二叉树（即哈夫曼树）呢？根据哈夫曼树的定义，一棵二叉树要使其WPL 值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。哈夫曼（Haffman）依据这一特点提出了一种方法，这种方法的基本思想是：

（1）由给定的n 个权值{W1，W2，…，Wn}构造n 棵只有一个叶结点的二叉树，从而得到一个二叉树的集合F＝{T1，T2，…，Tn}；

（2）在F 中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；

（3）在集合F 中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F 中；

（4）重复（2）（3）两步，当F 中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。

对于同一组给定叶结点所构造的哈夫曼树，树的形状可能不同，但带权路径长度值是相同的，一定是最小的。

2.哈夫曼树的构造算法

在构造哈夫曼树时，可以设置一个结构数组HuffNode 保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n 个叶子结点的哈夫曼树共有2n－1 个结点，所以数组HuffNode 的大小设置为2n －1，数组元素的结构形式如下：

为了判定一个结点是否已加入到要建立的哈夫曼树中，可通过parent 域的值来确定。初始时parent 的值为－1，当结点加入到树中时，该结点parent 的值为其双亲结点在数组HuffNode 中的序号，就不会是－1 了。

构造哈夫曼树时，首先将由n 个字符形成的n 个叶结点存放到数组HuffNode 的前n个分量中，然后根据前面介绍的哈夫曼方法的基本思想，不断将两个小子树合并为一个较大的子树，每次构成的新子树的根结点顺序放到HuffNode 数组中的前n 个分量的后面。

算法：

#define MAXVALUE	10000   /*定义最大权值*/
#define MAXLEAF		30      /*定义哈夫曼树中叶子结点个数*/
#define MAXNODE		MAXLEAF * 2 - 1
typedef struct {
	int	weight;
	int	parent;
	int	lchild;
	int	rchild;
}HNodeType;
void HaffmanTree( HNodeType HuffNode[] )
{                                               /*哈夫曼树的构造算法*/
	int i, j, m1, m2, x1, x2, n;
	scanf( “ % d ”, &n );                   /*输入叶子结点个数*/
	for ( i = 0; i < 2 * n - 1; i++ )       /*数组HuffNode[ ]初始化*/
	{
		HuffNode[i].weight	= 0;
		HuffNode[i].parent	= -1;
		HuffNode[i].lchild	= -1;
		HuffNode[i].rchild	= -1;
	}
	for ( i = 0; i < n; i++ )
		scanf( “ % d ”, &HuffNode[i].weight );  /*输入n 个叶子结点的权值*/
	for ( i = 0; i < n - 1; i++ )                   /*构造哈夫曼树*/
	{
		m1	= m2 = MAXVALUE;
		x1	= x2 = 0;
		for ( j = 0; j < n + i; j++ )
		{
			if ( HuffNode[j].weight < m1 && HuffNode[j].parent == -1 )
			{
				m2	= m1; x2 = x1;
				m1	= HuffNode[j].weight; x1 = j;
			}else if ( HuffNode[j].weight < m2 && HuffNode[j].parent == -1 )
			{
				m2	= HuffNode[j].weight;
				x2	= j;
			}
		}
/*将找出的两棵子树合并为一棵子树*/
		HuffNode[x1].parent	= n + i; HuffNode[x2].parent = n + i;
		HuffNode[n + i].weight	= HuffNode[x1].weight + HuffNode[x2].weight;
		HuffNode[n + i].lchild	= x1; HuffNode[n + i].rchild = x2;
	}
}

3.哈夫曼树在编码问题中的应用

编码：数据通讯中，将传送的文字转换成二进制符号0，1组成的二进制串。

如何使电文编码尽可能短？：让出现频率高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码，构造一种不等长编码。

哈夫曼树可用于构造使电文的编码总长最短的编码方案。具体做法如下：设需要编码的字符集合为{d1，d2，…，dn}，它们在电文中出现的次数或频率集合为{w1，w2，…，wn}，以d1，d2，…，dn 作为叶结点，w1，w2，…，wn 作为它们的权值，构造一棵哈夫曼树，规定哈夫曼树中的左分支代表0，右分支代表1，则从根结点到每个叶结点所经过的路径分支组成的0 和1 的序列便为该结点对应字符的编码，我们称之为哈夫曼编码。

树的带权路径长度——电文代码总长：各字符码长与其出现次数的乘积之和。采用哈夫曼树构造的编码是一种能使电文代码总长最短的不等长编码。

• 在建立不等长编码时，必须使任何一个字符的编码都不是另一个字符编码的前缀，这样才能保证译码的唯一性。
• 如表 (d)的编码方案，字符A 的编码01 是字符B 的编码010 的前缀部分，这样对于代码串0101001，既是AAC 的代码，也是ABD 和BDA 的代码，因此，这样的编码不能保证译码的唯一性，我们称之为具有二义性的译码。
• 采用哈夫曼树进行编码，则不会产生上述二义性问题。因为，在哈夫曼树中，每个字符结点都是叶结点，它们不可能在根结点到其它字符结点的路径上，所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀，从而保证了译码的非二义性。

实现哈夫曼编码算法：

1.构造哈夫曼树；
2.在哈夫曼树上求叶结点的编码。

求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶结点所经过的路径上各分支所组成的0，1 序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求编码的高位码。我们可以设置一结构数组HuffCode 用来存放各字符的哈夫曼编码信息，数组元素的结构如下：

其中，分量bit 为一维数组，用来保存字符的哈夫曼编码，start 表示该编码在数组bit中的开始位置。所以，对于第i 个字符，它的哈夫曼编码存放在HuffCode[i].bit 中的从HuffCode[i].start 到n 的分量上。

哈夫曼编码算法描述如下：

#define MAXBIT 10                       /*定义哈夫曼编码的最大长度*/
typedef struct {
	int	bit[MAXBIT];
	int	start;
}HCodeType;
void HaffmanCode()
{                                       /*生成哈夫曼编码*/
	HNodeType	HuffNode[MAXNODE];
	HCodeType	HuffCode[MAXLEAF], cd;
	int		i, j, c, p;
	HuffmanTree( HuffNode );        /*建立哈夫曼树*/
	for ( i = 0; i < n; i++ )       /*求每个叶子结点的哈夫曼编码*/
	{
		cd.start	= n - 1; c = i;
		p		= HuffNode[c].parent;
		while ( p != 0 )        /*由叶结点向上直到树根*/
		{
			if ( HuffNode[p].lchild == c )
				cd.bit[cd.start] = 0;
			else cd.bit[cd.start] = 1;
			cd.start--; c	= p;
			p		= HuffNode[c].parent;
		}
		for ( j = cd.start + 1; j < n; j++ )    /*保存求出的每个叶结点的哈夫曼编码和编码的起始位*/
			HuffCode[i].bit[j] = cd.bit[j];
		HuffCode[i].start = cd.start;
	}
	for ( i = 0; i < n; i++ )                       /*输出每个叶子结点的哈夫曼编码*/
	{
		for ( j = HuffCode[i].start + 1; j < n; j++ )
			printf( “ % ld ”, HuffCode[i].bit[j] );
		printf( “ \ n ” );
	}
}

3.哈夫曼在判定问题中的应用

如：编制一个百分制转五级分制的程序。条件语句即可完成：

if (a<60) b=”bad”;
else if (a<70) b=”pass”
else if (a<80) b=”general”
else if (a<90) b=”good”
else b=”excellent”;

这个判定过程可以图(a)所示的判定树来表示。如果上述程序需反复使用，而且每次的输入量很大，则应考虑上述程序的质量问题，即其操作所需要的时间。因为在实际中，学生的成绩在五个等级上的分布是不均匀的，假设其分布规律如下表所示：

则80％以上的数据需进行三次或三次以上的比较才能得出结果。假定以5，15，40，30 和10 为权构造一棵有五个叶子结点的哈夫曼树，则可得到如图(b)所示的判定过程，它可使大部分的数据经过较少的比较次数得出结果。但由于每个判定框都有两次比较，将这两次比较分开，得到如图6.19 (c)所示的判定树，按此判定树可写出相应的程序。假设有10000 个输入数据，若按图(a)的判定过程进行操作，则总共需进行31500 次比较；而若按图6.19 (c)的判定过程进行操作，则总共仅需进行22000 次比较。