第5章树和二叉树

i/2；结点i的左孩子为2i；结点i的右孩子为2i＋1。

5.3二叉树的逻辑结构性质5表明，在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。完全二叉树的基本性质

二叉树的抽象数据类型定义ADTBiTreeData

由一个根结点和两棵互不相交的左右子树构成，结点具有相同数据类型及层次关系Operation

5.3二叉树的逻辑结构同树类似，在不同的应用中，二叉树的基本操作不尽相同。下面给出一个二叉树抽象数据类型定义的例子，简单起见，基本操作只包含二叉树的遍历，在实际应用中，应根据具体需要重新定义其基本操作。

InitBiTree

前置条件：无输入：无功能：初始化一棵二叉树输出：无后置条件：构造一个空的二叉树DestroyBiTree

前置条件：二叉树已存在输入：无功能：销毁一棵二叉树输出：无后置条件：释放二叉树占用的存储空间

二叉树的抽象数据类型定义5.3二叉树的逻辑结构

PreOrder前置条件：二叉树已存在输入：无功能：前序遍历二叉树输出：二叉树中结点的一个线性排列后置条件：二叉树不变

InOrder

前置条件：二叉树已存在输入：无功能：中序遍历二叉树输出：二叉树中结点的一个线性排列后置条件：二叉树不变二叉树的抽象数据类型定义5.3二叉树的逻辑结构

PostOrder

前置条件：二叉树已存在输入：无功能：后序遍历二叉树输出：二叉树中结点的一个线性排列后置条件：二叉树不变

LeverOrder

前置条件：二叉树已存在输入：无功能：层序遍历二叉树输出：二叉树中结点的一个线性排列后置条件：二叉树不变endADT二叉树的抽象数据类型定义5.3二叉树的逻辑结构二叉树的遍历操作

二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。二叉树遍历操作的结果？非线性结构线性化5.3二叉树的逻辑结构抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。前序遍历中序遍历后序遍历层序遍历

二叉树的遍历方式：DLR、LDR、LRD、DRL、RDL、RLD

如果限定先左后右，则二叉树遍历方式有三种：前序：DLR中序：LDR后序：LRD层序遍历：按二叉树的层序编号的次序访问各结点。

5.3二叉树的逻辑结构考虑二叉树的组成：根结点D左子树L右子树R二叉树前序（根）遍历若二叉树为空，则空操作返回；否则：①访问根结点；②前序遍历根结点的左子树；③前序遍历根结点的右子树。5.3二叉树的逻辑结构前序遍历序列：ABDGCEFABCDEFG二叉树的遍历操作

中序（根）遍历若二叉树为空，则空操作返回；否则：①中序遍历根结点的左子树；②访问根结点；③中序遍历根结点的右子树。

5.3二叉树的逻辑结构中序遍历序列：DGBAECFABCDEFG二叉树的遍历操作

后序（根）遍历若二叉树为空，则空操作返回；否则：①后序遍历根结点的左子树；②后序遍历根结点的右子树。③访问根结点；5.3二叉树的逻辑结构后序遍历序列：GDBEFCAABCDEFG二叉树的遍历操作

层序遍历二叉树的层次遍历是指从二叉树的第一层（即根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。

5.3二叉树的逻辑结构层序遍历序列：ABCDEFGABCDEFG二叉树的遍历操作

5.3二叉树的逻辑结构-%/+*abcdef二叉树遍历操作练习前序遍历结果：-+a*b

%cd/ef中序遍历结果：a+b*c%

d-e/f后序遍历结果：abcd%*+ef/-5.3二叉树的逻辑结构若已知一棵二叉树的前序（或中序，或后序，或层序）序列，能否唯一确定这棵二叉树呢？ABC例：已知前序序列为ABC，则可能的二叉树有5种。ABC二叉树的遍历操作

5.3二叉树的逻辑结构例：已知前序遍历序列为ABC，后序遍历序列为CBA，则下列二叉树都满足条件。ABCABC若已知一棵二叉树的前序序列和后序序列，能否唯一确定这棵二叉树呢？二叉树的遍历操作

若已知一棵二叉树的前序序列和中序序列，能否唯一确定这棵二叉树呢？怎样确定？

例如：已知一棵二叉树的前序遍历序列和中序遍历序列分别为ABCDEFGHI和BCAEDGHFI，如何构造该二叉树呢?

5.3二叉树的逻辑结构二叉树的遍历操作

前序：ABCDEFG

HI中序：BCAEDGHFI前序：BC中序：BC5.3二叉树的逻辑结构

BCDEFGHIA前序：DEFGHI中序：EDGHFIABCDEFGHI前序：FG

HI中序：GHFI5.3二叉树的逻辑结构前序：DEFGHI中序：EDGHFIABCDEFGHIABCDEFIGH1.根据前序序列的第一个元素建立根结点；2.在中序序列中找到该元素，确定根结点的左右子树的中序序列；3.在前序序列中确定左右子树的前序序列；4.由左子树的前序序列和中序序列建立左子树；5.由右子树的前序序列和中序序列建立右子树。5.3二叉树的逻辑结构已知一棵二叉树的前序序列和中序序列，构造该二叉树的过程如下：

二叉树的遍历操作

顺序存储结构二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置（下标）应能体现结点之间的逻辑关系——父子关系。

如何利用数组下标来反映结点之间的逻辑关系?完全二叉树和满二叉树中结点的序号可以唯一地反映出结点之间的逻辑关系。5.4二叉树的存储结构及实现

A

B

C

D

E

F

G

H

I

J数组下标12345678910完全二叉树的顺序存储5.4二叉树的存储结构及实现CDEFGHIJ以编号为下标二叉树的顺序存储ABC∧DE∧∧∧F∧∧G数组下标123456789101112135.4二叉树的存储结构及实现ABCDEGF以编号为下标ABCDEGF123561013按照完全二叉树编号二叉树的顺序存储ABC∧DE∧∧∧F∧∧G数组下标01234567891011125.4二叉树的存储结构及实现ABCDEGFABCDEGF123561013按照完全二叉树编号注意到C++语言的数组下标从0开始，也可以将编号为i的结点存储到下标为i-1的位置。

一棵斜树的顺序存储会怎样呢？深度为k的右斜树，k个结点需分配2k－1个存储单元。

一棵二叉树改造后，变成完全二叉树形态，需增加很多空结点，造成存储空间的浪费。5.4二叉树的存储结构及实现二叉树的顺序存储结构一般仅存储完全二叉树!ABC137D15二叉链表基本思想：令二叉树的每个结点对应一个链表结点，链表结点除了存放与二叉树结点有关的数据信息外，还要设置指示左右孩子的指针。

结点结构：

lchild

data

rchild其中，data：数据域，存放该结点的数据信息；lchild：左指针域，存放指向左孩子的指针；rchild：右指针域，存放指向右孩子的指针。

5.4二叉树的存储结构及实现template<classDataType>structBiNode{DataTypedata;BiNode<T>*lchild,*rchild;};5.4二叉树的存储结构及实现lchild

datarchild左孩子结点右孩子结点二叉链表GFEDBAABCDEFG∧∧∧∧∧∧∧∧C二叉链表5.4二叉树的存储结构及实现具有n个结点的二叉链表中，有多少个空指针？GFEDBAABCDEFG∧∧∧∧∧∧∧∧C二叉链表5.4二叉树的存储结构及实现具有n个结点的二叉链表中，有n+1个空指针。template<classDataType>classBiTree{public:BiTree(){root=Creat(root);}//构造函数，建立一棵二叉树

~BiTree(){Release(root);}//析构函数

voidPreOrder(){PreOrder(root);}//前序遍历二叉树

voidInOrder(){InOrder(root);}//中序遍历二叉树

voidPostOrder(){PostOrder(root);}//后序遍历二叉树

voidLeverOrder();//层序遍历二叉树private:BiNode<DataType>*root;//指向根结点的头指针

BiNode<DataType>*Creat(BiNode<DataType>*bt);//构造函数调用

voidRelease(BiNode<DataType>*bt);//析构函数调用voidPreOrder(BiNode<DataType>*bt);//前序遍历函数调用

voidInOrder(BiNode<DataType>*bt);//中序遍历函数调用

voidPostOrder(BiNode<DataType>*bt);//后序遍历函数调用};5.4二叉树的存储结构及实现前序遍历——递归算法template<classDataType>voidBiTree<DataType>::PreOrder(BiNode<DataType>*bt){if(bt==NULL)return;//递归调用的结束条件else{cout<<bt->data;//访问根结点bt的数据域

PreOrder(bt->lchild);//前序递归遍历bt的左子树PreOrder(bt->rchild);//前序递归遍历bt的右子树}}5.4二叉树的存储结构及实现前序遍历——递归算法template<classDataType>voidBiTree<DataType>::PreOrder(BiNode<DataType>*bt){if(bt==NULL)return;else{cout<<bt->data;

PreOrder(bt->lchild);PreOrder(bt->rchild);

}}5.4二叉树的存储结构及实现ABCDEFG中序遍历——递归算法

template<classDataType>voidBiTree<DataType>::InOrder(BiNode<DataType>*bt){if(bt==NULL)return;//递归调用的结束条件else{InOrder(bt->lchild);//中序递归遍历bt的左子树

cout<<bt->data;//访问根结点bt的数据域InOrder(bt->rchild);//中序递归遍历bt的右子树}}5.4二叉树的存储结构及实现中序遍历——递归算法

template<classDataType>voidBiTree<DataType>::InOrder(BiNode<DataType>*bt){if(bt==NULL)return;else{InOrder(bt->lchild);

cout<<bt->data;InOrder(bt->rchild);}}5.4二叉树的存储结构及实现ABCDEFG后序遍历——递归算法template<classDataType>voidBiTree<DataType>::PostOrder(BiNode<DataType>*bt){if(bt==NULL)return;//递归调用的结束条件else{PostOrder(bt->lchild);//后序递归遍历bt的左子树PostOrder(bt->rchild);//后序递归遍历bt的右子树cout<<bt->data;//访问根结点bt的数据域}}5.4二叉树的存储结构及实现后序遍历——递归算法template<classDataType>voidBiTree<DataType>::PostOrder(BiNode<DataType>*bt){if(bt==NULL)return;else{PostOrder(bt->lchild);PostOrder(bt->rchild);cout<<bt->data;}}5.4二叉树的存储结构及实现ABCDEFG层序遍历5.4二叉树的存储结构及实现ABCDEFG遍历序列：AABCBDCEFGDEFG层序遍历队列Q初始化；2.如果二叉树非空，将根指针入队；3.循环直到队列Q为空3.1q=队列Q的队头元素出队；3.2访问结点q的数据域；3.3若结点q存在左孩子，则将左孩子指针入队；3.4若结点q存在右孩子，则将右孩子指针入队；5.4二叉树的存储结构及实现层序遍历template<classDataType>voidBiTree<DataType>::LeverOrder(){front=rear=-1;//采用顺序队列，并假定不会发生上溢if(root==NULL)return;//二叉树为空，算法结束Q[++rear]=root;//根指针入队while(front!=rear)//当队列非空时{q=Q[++front];//出队cout<<q->data;if(q->lchild!=NULL)Q[++rear]=q->lchild;if(q->rchild!=NULL)Q[++rear]=q->rchild;}}5.4二叉树的存储结构及实现构造函数——建立二叉树为了建立一棵二叉树，将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值如“#”，以标识其为空，把这样处理后的二叉树称为原二叉树的扩展二叉树。

为什么如此处理?5.4二叉树的存储结构及实现如何由一种遍历序列生成该二叉树？遍历是二叉树各种操作的基础，可以在遍历的过程中进行各种操作，例如建立一棵二叉树。扩展二叉树的前序遍历序列:AB#D##C##5.4二叉树的存储结构及实现DBAC#DBAC####构造函数——建立二叉树设二叉树中的结点均为一个字符。假设扩展二叉树的前序遍历序列由键盘输入，root为指向根结点的指针，二叉链表的建立过程是：首先输入根结点，若输入的是一个“#”字符，则表明该二叉树为空树，即root=NULL；否则输入的字符应该赋给root->data,，之后依次递归建立它的左子树和右子树。5.4二叉树的存储结构及实现构造函数——建立二叉树template<classDataType>BiTree::BiTree(){

root=Creat(root);

}template<classDataType>BiNode<DataType>*BiTree<DataType>::Creat(BiNode<DataType>*bt){cin>>ch;//输入结点的数据信息，假设为字符if(ch=='#')bt=NULL;//建立一棵空树else{bt=newBiNode;bt->data=ch;//生成一个结点，数据域为chbt->lchild=Creat(bt->lchild);//递归建立左子树

bt->rchild=Creat(bt->rchild);//递归建立右子树}returnbt;}5.4二叉树的存储结构及实现二叉树算法设计练习

遍历二叉树是二叉树各种操作的基础，遍历算法中对每个结点的访问操作可以是多种形式及多个操作，根据遍历算法的框架，适当修改访问操作的内容，可以派生出很多关于二叉树的应用算法。voidInOrder

(BiNode<T>*root){if(root==NULL)return;else{

InOrder(root->lchild);

cout<<root->data;

InOrder(root->rchild);}}二叉树算法设计练习设计算法求二叉树的结点个数。voidCount(BiNode*root)//count为全局量并已初始化为0{if(root==NULL)return;else{

Count(root->lchild);count++;

Count(root->rchild);}}二叉树算法设计练习设计算法按前序次序打印二叉树中的叶子结点。voidPreOrder(BiNode*root){if(root==NULL)return;else{

if(!root->lchild&&!root->rchild)cout<<root->data;PreOrder(root->lchild);PreOrder(root->rchild);}}二叉树算法设计练习设计算法求二叉树的深度。

intDepth(BiNode*root){if(root==NULL)return0;else{hl=Depth(root->lchild);hr=Depth(root->rchild);returnmax(hl,hr)+1;}}二叉树算法设计练习设计算法求树中结点x的第i个孩子。

TNode*Search(TNode*root,DataTypex,inti){if(root->data==x){j=1;p=root->firstchild;while(p!=NULL&&j<i){j++;p=p->rightsib;}if(p!=NULL)returnp;elsereturnNULL;}

Search(root->firstchild,x,i);Search(root->rightsib,x,i);}AEBCFDGABCDEFG三叉链表5.4二叉树的存储结构及实现GFEDBAABCDEFG∧∧∧∧∧∧∧∧C在二叉链表中，如何求某结点的双亲？三叉链表

lchild

dataparentrchild在二叉链表的基础上增加了一个指向双亲的指针域。结点结构其中：data、lchild和rchild三个域的含义同二叉链表的结点结构；parent域为指向该结点的双亲结点的指针。

5.4二叉树的存储结构及实现ABCDEFGA∧B∧D∧E∧F∧CG∧∧∧∧三叉链表5.4二叉树的存储结构及实现ABCDEFG三叉链表的静态链表形式5.4二叉树的存储结构及实现0123456dataparentlchildrchildABCDEFG-1001223134-1-1-1-12-156-1-1-1线索链表5.4二叉树的存储结构及实现如何保存二叉树的某种遍历序列？ABCDEFG中序遍历序列：DGBAFCF如果二叉树不改变，如何保存？顺序存储DGBAFCF线索链表5.4二叉树的存储结构及实现如何保存二叉树的某种遍历序列？ABCDEFG中序遍历序列：DGBAFCF如果二叉树改变，如何保存？链接存储DF

线索链表5.4二叉树的存储结构及实现如何保存二叉树的某种遍历序列？ABCDEFG中序遍历序列：DGBAFCF如何将二叉链表与中序链表结合？链接存储DF

线索链表线索：将二叉链表中的空指针域指向前驱结点和后继结点的指针被称为线索；线索化：使二叉链表中结点的空链域存放其前驱或后继信息的过程称为线索化；线索链表：加上线索的二叉链表称为线索链表。5.4二叉树的存储结构及实现如何保存二叉树的某种遍历序列？将二叉链表中的空指针域指向其前驱结点和后继结点

ltag

lchild

data

child

rtag0:lchild指向该结点的左孩子1:lchild指向该结点的前驱结点0:rchild指向该结点的右孩子1:rchild指向该结点的后继结点ltag=rtag=5.4二叉树的存储结构及实现结点结构线索链表enumflag{Child,Thread};template<classDataType>structThrNode{DataTypedata;ThrNode<DataType>*lchild,*rchild;

flagltag,rtag;};5.4二叉树的存储结构及实现线索链表

ltag

lchild

data

child

rtag结点结构二叉树的遍历方式有4种，故有4种意义下的前驱和后继，相应的有4种线索二叉树：⑴前序线索二叉树⑵中序线索二叉树⑶后序线索二叉树⑷层序线索二叉树5.4二叉树的存储结构及实现线索二叉树FABDCEG中序线索二叉树5.4二叉树的存储结构及实现线索二叉树中序序列：DGBAECFtemplate<classDataType>classInThrBiTree{public:InThrBiTree();//构造函数，建立中序线索链表

~InThrBiTree();//析构函数，释放各结点的存储空间

ThrNode*Next(ThrNode<DataType>*p);//查找p的后继

voidInOrder();//中序遍历线索链表private:ThrNode*root;//指向线索链表的头指针

ThrNode<DataType>*Creat(ThrNode<DataType>*bt);

voidThrBiTree(ThrNode<DataType>*bt,ThrNode<DataType>*pre);//构造函数调用};5.4二叉树的存储结构及实现中序线索链表类的声明分析：建立线索链表，实质上就是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历该二叉树时才能得到。5.4二叉树的存储结构及实现建立二叉链表遍历二叉树，将空指针改为线索中序线索链表的建立——构造函数A头指针BCDEFG∧∧∧∧∧∧00000000000000∧∧中序线索链表的建立过程5.4二叉树的存储结构及实现已经建立起二叉链表A头指针BCDEFG∧∧∧∧∧∧00000000000000∧∧中序线索链表的建立过程5.4二叉树的存储结构及实现中序遍历二叉链表p为正在访问的结点pre为刚访问的结点p1A头指针BCDEFG∧∧∧∧∧∧00000000000000∧∧中序线索链表的建立过程5.4二叉树的存储结构及实现中序遍历二叉链表p为正在访问的结点pre为刚访问的结点pre1p1A头指针BCDEFG∧∧∧∧∧∧00000000000000∧中序线索链表的建立过程5.4二叉树的存储结构及实现中序遍历二叉链表p为正在访问的结点pre为刚访问的结点pre11p1A头指针BCDEFG∧∧∧∧∧∧00000000000000中序线索链表的建立过程5.4二叉树的存储结构及实现中序遍历二叉链表p为正在访问的结点pre为刚访问的结点pre11p11A头指针BCDEFG∧∧∧∧∧00000000000000中序线索链表的建立过程5.4二叉树的存储结构及实现中序遍历二叉链表p为正在访问的结点pre为刚访问的结点pre11p111A头指针BCDEFG∧∧∧∧00000000000000中序线索链表的建立过程5.4二叉树的存储结构及实现中序遍历二叉链表p为正在访问的结点pre为刚访问的结点pre11p1111A头指针BCDEFG∧∧∧00000000000000中序线索链表的建立过程5.4二叉树的存储结构及实现中序遍历二叉链表p为正在访问的结点pre为刚访问的结点pre11p11111A头指针BCDEFG∧∧00000000000000中序线索链表的建立过程5.4二叉树的存储结构及实现中序遍历二叉链表p为正在访问的结点pre为刚访问的结点pre111111115.4二叉树的存储结构及实现中序线索链表查找后继FABDCEG⑴如果结点p的右标志为1，则表明该结点的右指针是线索；⑵如果结点p的右标志为0，则表明该结点有右孩子。根据中序遍历的操作定义，它的后继结点应该是遍历其右子树时第一个访问的结点，即右子树中的最左下结点。template<classDataType>ThrNode<DataType>*InThrBiTree<DataType>::Next(ThrNode<DataType>*p){if(p->rtag==1)q=p->rchild;//右标志为1，可直接得到后继结点

else{q=p->rchild;//工作指针q指向结点p的右孩子

while(q->ltag==0)//查找最左下结点

q=q->lchild;}returnq;}5.4二叉树的存储结构及实现中序线索链表查找后继二叉树前序遍历的非递归算法的关键：在前序遍历过某结点的整个左子树后，如何找到该结点的右子树的根指针。解决办法：在访问完该结点后，将该结点的指针保存在栈中，以便以后能通过它找到该结点的右子树。

在前序遍历中，设要遍历二叉树的根指针为root，则有两种可能：⑴若root!=NULL，则表明？如何处理？⑵若root=NULL，则表明？如何处理？前序遍历——非递归算法5.5二叉树遍历的非递归算法访问结点序列:A栈S内容:BD

A

B前序遍历的非递归实现

ADBC5.5二叉树遍历的非递归算法访问结点序列:A栈S内容:BD

A前序遍历的非递归实现

ADBC

D5.5二叉树遍历的非递归算法访问结点序列:A栈S内容:BD

C前序遍历的非递归实现

ADBCC5.5二叉树遍历的非递归算法1.栈s初始化；2.循环直到root为空且栈s为空

2.1当root不空时循环

2.1.1输出root->data;2.1.2将指针root的值保存到栈中；

2.1.3继续遍历root的左子树

2.2如果栈s不空，则

2.2.1将栈顶元素弹出至root；

2.2.2准备遍历root的右子树；前序遍历——非递归算法（伪代码）5.5二叉树遍历的非递归算法前序遍历——非递归算法（伪代码）template<classDataType>voidBiTree::PreOrder(BiNode<DataType>*root){top=-1;//采用顺序栈，并假定不会发生上溢

while(root!=NULL||top!=-1){while(root!=NULL){cout<<root->data;//先访问s[++top]=root;//再压栈root=root->lchild;}if(top!=-1){root=s[top--];root=root->rchild;}

}}5.5二叉树遍历的非递归算法ADBC中序遍历——非递归算法

在二叉树的中序遍历中，访问结点的操作发生在该结点的左子树遍历完毕并准备遍历右子树时，所以，在遍历过程中遇到某结点时并不能立即访问它，而是将它压栈，等到它的左子树遍历完毕后，再从栈中弹出并访问之。中序遍历的非递归算法只需将前序遍历的非递归算法中的输出语句cout<<bt->data移到bt=s[top--]之后即可。

5.5二叉树遍历的非递归算法中序遍历——非递归算法template<classDataType>voidBiTree::PreOrder(BiNode<DataType>*root){top=-1;//采用顺序栈，并假定不会发生上溢

while(root!=NULL||top!=-1){while(root!=NULL){s[++top]=root;root=root->lchild;}if(top!=-1){

root=s[top--];

cout<<root->data;root=root->rchild;}}}5.5二叉树遍历的非递归算法ABCDEFG后序遍历——非递归算法在后序遍历过程中，结点要入两次栈，出两次栈：⑴第一次出栈：只遍历完左子树，该结点不出栈，利用栈顶结点找到它的右子树，准备遍历它的右子树；⑵第二次出栈：遍历完右子树，将该结点出栈，并访问它。因此，为了区别同一个结点的两次出栈，设置标志flag。5.5二叉树遍历的非递归算法栈元素类型定义如下：template<classDataType>structelement{BiNode<DataType>*ptr;intflag;//1表示第1次出栈，2表示第2次出栈};后序遍历——非递归算法设根指针为bt，则可能有以下两种情况：⑴若bt不等于NULL