数据结构-树和二叉树课件

二叉树三．二叉树存贮结构

1二叉树的顺序结构

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

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

1二叉树的346.2

二叉树完全二叉树的顺序存储CDEFGHIJ以编号为下标ABCDEFGHIJ数组下标123456789106.2二叉树完全二叉树的顺序存储2

二叉树二叉树的顺序存储ABCDFGE按照完全二叉树编号ABCDFGE123561013ABC∧DE∧∧∧F∧∧G数组下标12345678910111213以编号为下标6.2二叉树二叉树的顺序存储ABCDFGE按照完全366.2

二叉树二叉树的顺序存储结构一般仅存储完全二叉树和满二叉树。6.2二叉树二叉树的顺序存储结构一376.2

二叉树2二叉树的链式存储结构 1）基本思想：令二叉树的每个结点对应一个链表结点，链表结点除了存放与二叉树结点有关的数据信息外，还要设置指示左右孩子的指针。

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

6.2二叉树2二叉树的链式存储结构 1）基本386.2

二叉树二叉树的二叉链表存储表示：TypedefstructBiNode{TElemTypedata;structBiNode*lchild,*rchild;//左右孩子指针}BiNode,*BiTree;6.2二叉树二叉树的二叉链表存储表示：396.2

二叉树

2）二叉链表二叉链表中每个结点至少包含三个域：数据域、左指针域、右指针域

ABCDEFGGFEDBA∧∧∧∧∧∧∧∧C在n个结点的二叉树中，有n+1个空链域。6.2二叉树2）二叉链表ABCDEFGGFED406.2

二叉树3）三叉链表三叉链表中每个结点至少包含四个域：数据域、双亲指针域、左指针域、右指针域结点结构：lchilddataparent其中，data：数据域，存放该结点的数据信息；parent:双亲指针域，存放指向指向双亲节点的指针；lchild：左指针域，存放指向左孩子的指针；rchild：右指针域，存放指向右孩子的指针。

rchild6.2二叉树3）三叉链表结点结构：lchild416.2

二叉树ABCDEFGA∧B∧D∧E∧F∧CG∧∧∧∧6.2二叉树ABCDEFGA∧B∧D∧E∧F∧CG42第六章树和二叉树

6.3二叉树的遍历一.二叉树的遍历方法二.遍历的递归算法第六章树和二叉树6.3二叉树的遍历436.3二叉树的遍历一、二叉树的遍历方法

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

对于线性结构由于每个结点只有一个直接后继，遍历是很容易的事。

二叉树是非线性结构，每个结点可能有两个后继，如何访问二叉树的每个结点，而且每个结点仅被访问一次？6.3二叉树的遍历一、二叉树的遍历方法二44二叉树的遍历方式：DLR、LDR、LRD、DRL、RDL、RLD

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

考虑二叉树的组成：根结点D左子树L右子树R二叉树6.3二叉树的遍历二叉树的遍历方式：如果限定先左后右，则二叉树遍历方式有三种：451、先序（根）遍历若二叉树为空，则空操作返回；否则：①访问根结点；②先序遍历根结点的左子树；③先序遍历根结点的右子树。先序遍历序列：ABDGCEFABCDEFG6.3二叉树的遍历1、先序（根）遍历先序遍历序列：ABDGCEFA466.3二叉树的遍历2、中序（根）遍历若二叉树为空，则空操作返回；否则：①中序遍历根结点的左子树；②访问根结点；③中序遍历根结点的右子树。

中序遍历序列：DGBAECFABCDEFG6.3二叉树的遍历2、中序（根）遍历中序遍历序列：DG476.3二叉树的遍历3、后序（根）遍历若二叉树为空，则空操作返回；否则：①后序遍历根结点的左子树；②后序遍历根结点的右子树；③访问根结点。后序遍历序列：GDBEFCAABCDEFG6.3二叉树的遍历3、后序（根）遍历后序遍历序列：GD484、层序遍历二叉树的层次遍历是指从二叉树的第一层（即根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。

层序遍历序列：ABCDEFGABCDEFG6.3二叉树的遍历4、层序遍历层序遍历序列：ABCDEFGABCD496.3二叉树的遍历ABCDEFGHK例如：先序序列：中序序列：后序序列：A

BCD

EFGHKBDC

A

EHGKFDCBHKGFE

A6.3二叉树的遍历ABCDEFGHK例如：先序序列：中序506.3二叉树的遍历二.遍历的递归算法voidPreorder(BiTreeT,void(*visit)(TElemType&e)){//先序遍历二叉树

if(T!==NULL){

visit(T->data);//访问结点

Preorder(T->lchild,visit);//遍历左子树

Preorder(T->rchild,visit);//遍历右子树}}先序遍历递归算法6.3二叉树的遍历二.遍历的递归算法voidPreo516.3二叉树的遍历二叉树前序遍历的非递归算法的关键：在前序遍历过某结点的整个左子树后，如何找到该结点的右子树的根指针。解决办法：在访问完该结点后，将该结点的指针保存在栈中，以便以后能通过它找到该结点的右子树。

先序遍历——非递归算法6.3二叉树的遍历二叉树前序遍历的非递归算法的关键：在前52AGBCDFE先序遍历算法的执行轨迹ABDGCEFA栈内容BDGCEFAGBCDFE先序遍历算法的执行轨迹ABDGCEFA栈内容B531.栈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的右子树；步骤：1.栈s初始化；步骤：546.3二叉树的遍历voidPreorder(BiTreeT,void(*visit)(TElemType&e)){InitStack(&S);p=T;while(p!==NULL||!StackEmpty(S)){if(p!==NULL){

visit(p->data);//访问结点Push(&S,p);p=p->lchild}else{Pop(&S,&p);p=p->rchild}}先序遍历非递归算法（伪代码）6.3二叉树的遍历voidPreorder(BiTr556.3二叉树的遍历2中序遍历递归算法voidInorder(BiTreeT,void(*visit)(TElemType&e)){//中序遍历二叉树

if(T!==NULL){Preorder(T->lchild,visit);//遍历左子树

visit(T->data);//访问结点

Preorder(T->rchild,visit);//遍历右子树}}6.3二叉树的遍历2中序遍历递归算法voidIno566.3二叉树的遍历中序遍历非递归算法：voidInorder(BiTreeT,void(*visit)(TElemType&e)){InitStack(&S);p=T;while(p!==NULL||!StackEmpty(S)){if(p!==NULL){Push(&S,p);p=p->lchild}else{Pop(&S,&p);

visit(T->data);//访问结点p=p->rchild}}6.3二叉树的遍历中序遍历非递归算法：voidInor576.3二叉树的遍历3后序遍历递归算法voidPostorder(BiTreeT,void(*visit)(TElemType&e)){//后序遍历二叉树

if(T!==NULL){Preorder(T->lchild,visit);//遍历左子树Preorder(T->rchild,visit);//遍历右子树visit(T->data);//访问结点}}6.3二叉树的遍历3后序遍历递归算法voidPos58若已知一棵二叉树的前序序列和中序序列，能否唯一确定这棵二叉树呢？怎样确定？

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

6.3二叉树的遍历若已知一棵二叉树的前序序列和中序序列，能否唯一确定这棵二叉树59先序：ABCDEFG

HI中序：BCAEDGHFI先序：BC中序：BC

BCDEFGHIA先序：DEFGHI中序：EDGHFIABCDEFGHI6.3二叉树的遍历先序：ABCDEFGHI先序：BCD60先序：FG

HI中序：GHFI先序：DEFGHI中序：EDGHFIABCDEFGHIABCDEFIGH6.3二叉树的遍历先序：FGHI先序：DEFGHIABCDE61第六章树和二叉树

6.4遍历的应用1.二叉树的基本应用2.建立二叉存储链表

第六章树和二叉树6.4遍历的应用626.4遍历的应用遍历二叉树是二叉树各种操作的基础，遍历算法中对每个结点的访问操作可以是多种形式及多个操作，根据遍历算法的框架，适当修改访问操作的内容，可以派生出很多关于二叉树的应用算法。6.4遍历的应用遍历二叉树是二叉树各种操作的基636.4遍历的应用例1编写求二叉树的叶子结点个数的算法

输入：二叉树的二叉链表

结果：二叉树的叶子结点个数基本思想：遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。所以可在二叉树遍历的过程中，统计叶子结点的个数。voidleaf(BiTreeT){//n计数二叉树的叶子结点的个数，初值n=0if(T){

if(T->lchild==null&&T->rchild==null)n=n+1;

leaf(T->lchild);leaf(T->rchild);}//if}//leafABCDEFG6.4遍历的应用例1编写求二叉树的叶子结点个数的64例2

求二叉树的结点个数。

voidCount(BiNode*root)//n为全局量并已初始化为0{if(root){Count(root->lchild);

n++;Count(root->rchild);}}6.4遍历的应用例2求二叉树的结点个数。voidCount(BiNod65例3、求二叉树的深度。

intDepth(BiNode*root){if(root==NULL)return0;else{hl=Depth(root->lchild);hr=Depth(root->rchild);

returnmax(hl,hr)+1;}}6.4遍历的应用二叉树的深度应为其左、右子树深度的最大值加1。例3、求二叉树的深度。intDepth(BiNode666.4遍历的应用

例4为二叉树建立二叉存储链表输入：二叉树的先序序列结果：建立二叉树的二叉存储链表

按先序编历的顺序输入先序序列（设每个元素是一个字符），建立二叉链表的所有结点并完成相应结点的链接。为了建立一棵二叉树，将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值如“#”，以标识其为空，把这样处理后的二叉树称为原二叉树的扩展二叉树。6.4遍历的应用例4为二叉树建立二叉存储链表67扩展二叉树的先序遍历序列:AB#D##C##DBAC#DBAC####6.4遍历的应用扩展二叉树的先序遍历序列:AB#D##C##686.4遍历的应用StatusCreateBiTree(BiTree&T){//假设扩展二叉树的先序遍历序列由键盘输入，T为指向根结点的指针scanf(&ch);if(ch==‘#’)T=NULL;//若ch==‘#’则T=NULL返回else{//若ch!=‘’

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch;//建立（根）结点CreateBiTree(T->lchild);//构造左子树，并将左子树根结点指针//赋给（根）结点的左孩子域CreateBiTree(T->rchild);//构造右子树，并将右子树根结点指针//赋给（根）结点的右孩子域}returnOK;}//CreateBiTree6.4遍历的应用StatusCreateBiTree69

小结1二叉树：或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树本身也是二叉树；2二叉树即可以用顺序结构存储，也可用链式结构存储；3遍历：按某种搜索路径访问二叉树的每个结点，每个结点仅被访问一次。二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树，本课程介绍了三种遍历算法：先序遍历、中序遍历、后序遍历；

70第六章树和二叉树

6.5线索二叉树

1.线索二叉树的概念2线索链表3.*线索二叉树的遍历第六章树和二叉树6.5线索二叉树716.5线索二叉树一、线索二叉树遍历的目的：

将二叉树中的结点按一定规律（先、中、后序）线性化的过程。问题：当以二叉链表作为存储结构时，只能找到某结点的左、右孩子信息，不能得到结点在某种遍历序列中的前驱和后继信息。解决办法：◆重新遍历，在遍历过程中得到前驱、后继信息。但这种动态访问浪费时间。◆充分利用二叉链表的空链域，将遍历过程中结点的前驱、后继信息保留下来。6.5线索二叉树一、线索二叉树遍历的目的：问题：当以72ltaglchilddatarchildrtag0:lchild指向该结点的左孩子1:lchild指向该结点的前驱结点0:rchild指向该结点的右孩子1:rchild指向该结点的后继结点ltag=rtag=结点结构6.5线索二叉树线索：将二叉链表中的空指针域指向前驱结点和后继结点的指针被称为线索；线索化：使二叉链表中结点的空链域存放其前驱或后继信息的过程称为线索化；线索二叉树：加上线索的二叉树称为线索二叉树。ltaglchilddatarchildrtag73ABCDEFGABCDEFGABCDEFGABCDEFGABDGCEFDGBAECFGDBEFCANULLNULLNULLNULL先序中序后序ABCDEFGABCDEFGABCDEFGABCDEFGAB74ABCDEFGDGBAECFNULLNULL中序找前驱结点1、P↑Ltag=1,P↑Lchild为前驱2、“根”P的前驱结点是中序遍历P的左子树时访问的最后一个结点找后继结点1、P↑Rtag=1,P↑Rchild为后继驱2、“根”P的后继结点是其右子树的“最左下端”的结点ABCDEFGDGBAECFNULLNULL中序找前驱结点找75A头指针BCDEFG∧∧∧∧∧∧00000000000000∧∧中序线索链表的建立过程已经建立起二叉链表DGBAECFA头指针BCDEFG∧∧∧∧∧∧0000000000000076A头指针BCDEFG∧∧∧∧∧∧00000000000000∧∧中序线索链表的建立过程中序遍历二叉链表p为正在访问的结点pre为刚访问的结点p1DDGBAECFA头指针BCDEFG∧∧∧∧∧∧0000000000000077A头指针BCDEFG∧∧∧∧∧∧00000000000000∧∧中序线索链表的建立过程中序遍历二叉链表p为正在访问的结点pre为刚访问的结点pre1p1DGDGBAECFA头指针BCDEFG∧∧∧∧∧∧0000000000000078A头指针BCDEFG∧∧∧∧∧∧00000000000000∧中序遍历二叉链表p为正在访问的结点pre为刚访问的结点pre11p1中序线索链表的建立过程DGBDGBAECFA头指针BCDEFG∧∧∧∧∧∧0000000000000079A头指针BCDEFG∧∧∧∧∧∧00000000000000中序遍历二叉链表p为正在访问的结点pre为刚访问的结点pre11p11中序线索链表的建立过程DGBADGBAECFA头指针BCDEFG∧∧∧∧∧∧0000000000000080A头指针BCDEFG∧∧∧∧∧00000000000000中序遍历二叉链表p为正在访问的结点pre为刚访问的结点pre11p111中序线索链表的建立过程DGBAEDGBAECFA头指针BCDEFG∧∧∧∧∧00000000000000中81A头指针BCDEFG∧∧∧∧00000000000000中序遍历二叉链表p为正在访问的结点pre为刚访问的结点pre11p1111中序线索链表的建立过程DGBAECDGBAECFA头指针BCDEFG∧∧∧∧00000000000000中序82A头指针BCDEFG∧∧∧00000000000000中序遍历二叉链表p为正在访问的结点pre为刚访问的结点pre11p11111中序线索链表的建立过程DGBAECFDGBAECFA头指针BCDEFG∧∧∧00000000000000中序遍83A头指针BCDEFG∧∧00000000000000中序遍历二叉链表p为正在访问的结点pre为刚访问的结点pre11111111中序线索链表的建立过程DGBAECFDGBAECFA头指针BCDEFG∧∧00000000000000中序遍历84第六章树和二叉树

6.6树和森林一.树的存储结构二.树和二叉树的转换三.

树的遍历四.森林

第六章树和二叉树6.6树和森林856.6树和森林

一．树的存贮结构1、双亲表示法基本思想：用一维数组来存储树的各个结点（一般按层序存储），数组中的一个元素对应树中的一个结点，包括结点的数据信息以及该结点的双亲在数组中的下标。

data

parentdata：存储树中结点的数据信息parent：存储该结点的双亲在数组中的下标6.6树和森林一．树的存贮结构基本思想：用一维数组来存866.6树和森林#defineMAX_TREE_SIZE100typestructPTNode//结点结构{TEleTypedata;//数据域intparent;//双亲在数组中的下标}PTNode;Typedefstruct{//树结构PTNodenodes[MAX_TREE_SIZE]intr,n//根的位置和结点数}PTree树的双亲表示法实质上是一个静态链表。6.6树和森林#defineMAX_TREE_SIZE876.6树和森林012345678

A-1B0C0D1E1F1G2H2I

4ACBHFEDGI找某一结点的双亲，按照该结点的双亲下表即可找到。但求某一结点的孩子，要遍历整个结构。6.6树和森林0A-1AC886.6树和森林2、孩子表示法链表中的每个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。方案一：指针域的个数等于树的度datachild1child2……childd其中：data：数据域，存放该结点的数据信息；child1~childd：指针域，指向该结点的孩子。

6.6树和森林2、孩子表示法链表中的每个896.6树和森林∧缺点：浪费空间ACBHFEDGIA∧B∧C∧D∧E∧F∧G∧H∧I∧∧∧∧∧∧∧∧∧∧∧6.6树和森林∧缺点：浪费空间ACBHFEDGIA∧B∧906.6树和森林方案二：

指针域的个数等于该结点的度data

degree

child1

child2

……

childd其中：data：数据域，存放该结点的数据信息；degree：度域，存放该结点的度；child1~childd：指针域，指向该结点的孩子。

6.6树和森林方案二：指针域的个数等于该结点的度da91缺点：结点结构不一致ACBHFEDGIA2B3C2E1I0G0H0F0D06.6树和森林缺点：结点结构不一致ACBHFEDGIA2B3C926.6树和森林方案三：将结点的所有孩子放在一起，构成线性表。基本思想：

把每个结点的孩子排列起来，看成是一个线性表，且以单链表存储，则n个结点共有n个孩子链表。这n个单链表共有n个头指针，这n个头指针又组成了一个线性表，构成孩子链表的表头数组。

6.6树和森林方案三：将结点的所有孩子放在一起，构成线性93

6.6树和森林childnext孩子结点typedefstructCTNode{intchild;structCTNode*next;};Typedefstruct{