第4章树结构介绍

第4章树结构第2页2020年6月10日1．教学内容二叉树和树的概念、二叉树的遍历及其应用、线索二叉树、哈夫曼树及哈夫曼编码、树和森林与二叉树之间的转换、树或森林的遍历。⒉教学目的深刻理解二叉树的定义、性质及其存储方法；熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义；掌握二叉树的三种遍历算法；了解二叉树的线索化方法；灵活运用二叉树的遍历方法解决相关的应用问题;掌握森林与二叉树间的相互转换；掌握树和森林的遍历方法。第3页2020年6月10日⒊教学重点：二叉树的定义、逻辑特点及性质；二叉树的存储结构；二叉树的遍历方法及其算法；以遍历为基础在二叉树上实现的几种运算；哈夫曼树和哈夫曼算法；树的存储结构；森林与二叉树的转换。⒋教学难点：二叉树的递归定义；二叉树链式存储结构的组织方式；三种遍历的算法；二叉树上的复杂运算；哈夫曼算法及其应用；第4页2020年6月10日4.1引言4.1.1问题提出问题1：组织结构层次关系的存储与查找。问题2：家族族谱中家族成员之间的关系表示与查找。问题3：图书馆中图书的分类关系的建立。。。。。。。第5页2020年6月10日1．树的定义树（Tree）是n（n≥0）个有限数据元素的集合。当n＝0时，称这棵树为空树。在一棵非空树T中：(1)有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。(2)若n1，除根结点之外的其余数据元素被分成m（m0）个互不相交的集合T1,T2,…,Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1,T2,…,Tm称为这个根结点的子树。4.1.2相关概念第6页2020年6月10日第7页2020年6月10日树具有下面两个特点：⑴树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。⑵树中所有结点可以有零个或多个后继结点。由此特点可知，下图所示的都不是树结构。第8页2020年6月10日3．相关术语(1)结点的度(2)叶结点(3)分支结点(4)左孩子、右孩子、双亲、兄弟(5)路径、路径长度(6)祖先、子孙(7)结点的层数(8)树的深度第9页2020年6月10日（9）树的度（10）有序树和无序树（11）森林第10页2020年6月10日1．二叉树的定义4.2.1二叉树的概念4.2二叉树第11页2020年6月10日2．二叉树的相关术语(1)满二叉树。第12页2020年6月10日(2)完全二叉树。第13页2020年6月10日3.二叉树的基本操作(1)Initiate(bt)(2)Create(x,lbt,rbt)(3)InsertL(bt,x,parent)(4)InsertR(bt,x,parent)(5)DeleteL(bt,parent)(6)DeleteR(bt,parent)(7)Search(bt,x)(8)Traverse(bt)第14页2020年6月10日4.2.2二叉树的主要性质性质1一棵非空二叉树的第i层上最多有2i-1个结点（i≥1）。性质2一棵深度为k的二叉树中，最多具有2k－1个结点。性质3对于一棵非空的二叉树，若叶子结点数为n0，度数为2的结点数为n2，则有：n0＝n21。性质4具有n个结点的完全二叉树的深度k为：log2n+1第15页2020年6月10日性质5:对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有：⑴如果i1，则序号为i的结点的双亲结点的序号为i/2；如果i＝1，则序号为i的结点是根结点，无双亲结点。⑵如果2i≤n，则序号为i的结点的左孩子结点的序号为2i；如果2in，则序号为i的结点无左孩子。⑶如果2i＋1≤n，则序号为i的结点的右孩子结点的序号为2i＋1；如果2i＋1n，则序号为i的结点无右孩子。此外，若对二叉树的根结点从0开始编号，则相应的i号结点的双亲结点的编号为(i－1)/2，左孩子的编号为2i＋1，右孩子的编号为2i＋2。第16页2020年6月10日4.2.3二叉树的存储1．顺序存储结构所谓二叉树的顺序存储，是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。第17页2020年6月10日•下面给出一棵完全二叉树的顺序存储示意。第18页2020年6月10日•对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，只有增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。第19页2020年6月10日极端情况是单支树，如一棵深度为k的右单支树，只有k个结点，却需分配2k－1个存储单元。显然，对于需增加许多空结点才能将一棵二叉树改造成为一棵完全二叉树的存储时，会造成空间的大量浪费，不宜用顺序存储结构。第20页2020年6月10日二叉树的顺序存储结构可描述为：#defineMAXNODE1024//二叉树的最大结点数，可根据实际情况进行修改typedefdatatypeSqBiTree[MAXNODE];//0号单元存放根结点定义一个顺序存储的二叉树变量：SqBiTreebt;即将bt为含有MAXNODE个datatype类型元素的一维数组。第21页2020年6月10日2．链式存储结构(1)二叉链表存储第22页2020年6月10日下图(a)给出一棵二叉树的二叉链表存储表示。二叉链表也可以带头结点的方式存放，如图(b)所示。第23页2020年6月10日二叉树的二叉链表存储结构可描述为：typedefstructbitnode{datatypedata;structbitnode*lchild;*rchild;//左右孩子指针}BiTNode,*BiTree;定义一个指向二叉树的指针变量：BiTreet;第24页2020年6月10日(2)三叉链表存储每个结点由四个域组成，具体结构为：第25页2020年6月10日下图给出一棵二叉树的三叉链表存储示意图。第26页2020年6月10日4.2.4二叉树基本运算的实现算法的实现依赖于具体的存储结构，当二叉树采用不同的存储结构时，上述各种操作的实现算法是不同的。下面讨论基于二叉链表存储结构的上述操作的实现算法。第27页2020年6月10日(1)Initiate(bt)：建立一棵空的二叉树bt，并返回bt。【算法4-1(a)】建立一棵空的带头结点的二叉树BiTreeInitiate()//初始建立一棵带头结点的二叉树{BiTNode*bt;bt=(BiTNode*)malloc(sizeof(BiTNode));bt-lchild=NULL;bt-rchild=NULL;returnbt;}若要建立不带头结点的二叉树，可描述如下：【算法4-1(b)】建立一棵空的不带头结点的二叉树BiTreeInitiate()//初始建立一棵不带头结点的二叉树{BiTNode*bt;bt=NULL;returnbt;}第28页2020年6月10日(2)Create(x，lbt，rbt)：生成一棵以x为根结点的数据域值以lbt和rbt为左右子树的二叉树。【算法4-2】生成一棵以x为根结点的数据域值以lbt和rbt为左右子树的二叉树BiTreeCreate(elemtypex,BiTreelbt,BiTreerbt){BiTreep;if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)returnNULL;p-data=x;p-lchild=lbt;p-rchild=rbt;returnp;}第29页2020年6月10日(3)InsertL(bt,x,parent)：在二叉树bt中的parent所指结点和其左子树之间插入数据元素为x的结点(4)InsertR(bt，x，parent)：功能类同于(3)，算法略。【算法4-3】在二叉树bt中的parent所指结点和其左子树之间插入数据元素为x的结点BiTreeInsertL(BiTreebt，elemtypex，BiTreeparent){BiTreep;if(parent==NULL){printf(\n插入出错)；returnNULL;}if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)returnNULL;p-data=x;p-lchild=NULL;p-rchild=NULL;if(parent-lchild==NULL)parent-lchild=p;else{p-lchild=parent-lchild;parent-lchild=p;}第30页2020年6月10日(5)DeleteL(bt，parent)：在二叉树bt中删除parent的左子树(6)DeleteR(bt，parent)：算法略。【算法4-4】在二叉树bt中删除parent的左子树BiTreeDeleteL(BiTreebt，BiTreeparent){BiTreep;if(parent==NULL||parent-lchild==NULL){printf(\n删除出错)；returnNULL;}p=parent-lchild;parent-lchild=NULL;free(p);//当*p为非叶子结点时，这样删除仅释放了所删子树根结点的空间，//若要删除子树分支中的结点，需用后面介绍的遍历操作来实现。returnbt;}第31页2020年6月10日4.3二叉树的遍历二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。二叉树遍历是二叉树中最重要最基本的运算。第32页2020年6月10日4.3.1递归方法实现二叉树的三种遍历若以D、L、R分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树，如果限定先左后右，则有三种方式，即：DLR（称为先序遍历)LDR（称为中序遍历)LRD（称为后序遍历)。第33页2020年6月10日1．先序遍历先序遍历的递归过程为：若二叉树为空，遍历结束。否则，(1)访问根结点；(2)先序遍历根结点的左子树；(3)先序遍历根结点的右子树。【算法4-5】先序遍历二叉树的递归算法voidPreOrder(BiTreebt){if(bt==NULL)return;//递归调用的结束条件Visit(bt);//访问根结点PreOrder(bt-lchild);//先序递归遍历bt的左子树PreOrder(bt-rchild);//先序递归遍历bt的右子树}第34页2020年6月10日对于上图所示的二叉树，按先序遍历所得到的结点序列为：ABDGCEF第35页2020年6月10日2．中序遍历中序遍历的递归过程为：若二叉树为空，遍历结束。否则，(1)中序遍历根结点的左子树；(2)访问根结点；(3)中序遍历根结点的右子树。【算法4-6】中序遍历二叉树的递归算法voidInOrder(BiTreebt){if(bt==NULL)return;//递归调用的结束条件InOrder(bt-lchild);//中序递归遍历bt的左子树Visit(bt);//访问根结点InOrder(bt-rchild);//中序递归遍历bt的右子树}第36页2020年6月10日对于上图所示的二叉树，按中序遍历所得到的结点序列为：DGBAECF第37页2020年6月10日3．后序遍历后序遍历的递归过程为：若二叉树为空，遍历结束。否则，(1)后序遍历根结点的左子树；(2)后序遍历根结点的右子树；(3)访问根结点。【算法4-7】后序遍历二叉树的递归算法voidPostOrder(BiTreebt){if(bt==NULL)return;//递归调用的结束条件PostOrder(bt-lchild);//后序递归遍历bt的左子树PostOrder(bt-rchild);//后序递归遍历bt的右子树Visite(bt);//访问根结点}第38页2020年6月10日对于上图所示的