数据结构第07章-树和二叉树课件.ppt

1、数据结构（数据结构（C+版）版）n 第1章 绪论 第2章 线性表 第3章 排序 第4章 串 第5章 栈与队列 第6章 数组和广义表 第7章 树和二叉树 第8章 查找 第9章 图 第10章 综合应用设计第7章 树和二叉树 7.1 树 7.2 二叉树 7.3 二叉树类 7.4 线索二叉树 7.5 堆排序数据结构（C+版）叶核亚7.1 树7.1.1 树的定义7.1.2 树的术语7.1.3 树的表示方法数据结构（C+版）叶核亚7.1.1 树的定义树（tree）是由n（n0）个结点组成的有限集合。n=0的树称为空树；对n0的树T，有：有一个特殊的结点称为根结点（root），它只有直接后继结点，没有直接前

2、驱结点。当n1时，除根结点之外的其他结点分为m（m0）个互不相交的集合T1,T2,Tm，其中每个集合Tm（1im）本身又是一棵结构与树类同的子树（subtree）。每棵子树的根结点有且仅有一个直接前驱结点，但可以有零或多个直接后继结点。AGHDEJCBIF(a)n=0空树(b)n=1树中只有一个根结点Arootrootlevel=1level=2level=3depth=3(c)n=10,度为3的树数据结构（C+版）叶核亚7.1.2 树的术语1结点2孩子结点与双亲结点3兄弟结点4祖先结点与后代结点5结点的度6叶子结点与分支结点7树的度8边9路径与路径长度10结点的层次11树的深度或高度12无序

3、树与有序树13森林数据结构（C+版）叶核亚7.1.3 树的表示方法1.图示法2.树的广义表形式表示图7-2c所示树的广义表表示形式为：A（B（E，F），C（G），D）H，I，J）数据结构（C+版）叶核亚7.2 二叉树7.2.1 二叉树的定义7.2.2 二叉树的性质7.2.3 二叉树的抽象数据类型 7.2.4 二叉树的遍历7.2.5 二叉树的存储结构7.2.6 树与二叉树的转换数据结构（C+版）叶核亚7.2.1 二叉树的定义1二叉树的递归定义二叉树（binary tree）是n（n0）个结点组成的有限集合。n=0时称为空二叉树；n0的二叉树由一个根结点和两棵互不相交的、分别称为左子树和右子树的子

4、二叉树构成。数据结构（C+版）叶核亚2二叉树的基本形态图7-5 3个结点树与二叉树的基本形态数据结构（C+版）叶核亚7.2.2 二叉树的性质1性质1若根结点的层次为1，则二叉树第i层的结点数目最多为2i-1（i1）。2性质2在深度为k的二叉树中，至多有2k-1个结点（k0）。3性质3二叉树中，若叶子结点数为n0，2度结点数为n2，则有n0=n2+1。数据结构（C+版）叶核亚4满二叉树与完全二叉树5性质4如果一棵完全二叉树有n个结点，则其深度。6性质5若将一棵具有n个结点的完全二叉树按顺序表示，对于编号为i（1in）的结点，有如下特点：若i=1，则i为根结点，无双亲；若i1，则i的双亲是编号为i

5、/2的结点。若2in，则i的左孩子是编号为2i的结点；若2in，则i无左孩子。若2i+1n，则i的右孩子是编号为2i+1的结点；若2i+1n，则i无右孩子。数据结构（C+版）叶核亚7.2.3 二叉树的抽象数据类型 1.二叉树的数据元素 二叉树的结点集合，每个结点由数据元素和构造数据元素之间关系的指针组成。1.二叉树的基本操作创建一棵二叉树。撤销二叉树。遍历二叉树。查找：在一棵二叉树中查找关键字满足给定条件的结点。插入结点：若当前结点非空，插入新结点作为当前结点的左（或右）孩子结点，当前结点的原左（或右）孩子结点成为新结点的左（或右）孩子结点。删除子树：若当前结点非空，删除当前结点的左（或右）子

6、树。数据结构（C+版）叶核亚7.2.4 二叉树的遍历1.遍历（traversal）二叉树就是按照一定规则和次序访问二叉树中的所有结点，并且每个结点仅被访问一次。所谓访问，是指对每一个结点的数据元素进行查阅、修改等操作。一次完整的遍历按照一种规则对二叉树中的结点产生一种线性次序。2.若规定对子树的访问按“先左后右”的次序进行，则遍历二叉树有3种次序：先根次序：访问根结点，遍历左子树，遍历右子树。中根次序：遍历左子树，访问根结点，遍历右子树。后根次序：遍历左子树，遍历右子树，访问根结点。数据结构（C+版）叶核亚按先根次序遍历二叉树的过程数据结构（C+版）叶核亚7.2.5 二叉树的存储结构1.二叉树

7、的顺序存储结构数据结构（C+版）叶核亚2二叉树的链式存储结构 CAB E G D leftrightdataroot(a)二叉树(b)链式存储结构ABCDEG数据结构（C+版）叶核亚7.2.6 树与二叉树的转换1树转化为二叉树2二叉树还原为树数据结构（C+版）叶核亚7.3 二叉树类7.3.1 二叉树的结点类 7.3.2 二叉树类的设计与实现 7.3.3 建立二叉树的算法设计 7.3.4 二叉树遍历的非递归算法7.3.5 按层次遍历二叉树数据结构（C+版）叶核亚7.3.1 二叉树的结点类 class TreeNode1 /二叉树的结点类 public:char data;/数据元素域 TreeN

8、ode1*left,*right;/指向左、右孩子结点的指针域 TreeNode1(char ch=?);/构造二叉树的结点 TreeNode1()/析构函数为空 void preorderChild(TreeNode1*p);/先序遍历以p为根的子树 void inorderChild(TreeNode1*p);/中序遍历以p为根的子树 void postorderChild(TreeNode1*p);/后序遍历以p为根的子树;数据结构（C+版）叶核亚3按先根次序遍历二叉树的递归算法若二叉树为空，返回；否则，继续。从根结点开始，访问当前结点。按先根次序遍历当前结点的左子树。按先根次序遍历当前

9、结点的右子树。void TreeNode1:preorderChild(TreeNode1*p)/先序遍历以p为根的子树 if(p!=NULL)coutdataleft);preorderChild(p-right);数据结构（C+版）叶核亚4按中根次序遍历二叉树的递归算法 void TreeNode1:inorderChild(TreeNode1*p)/中序遍历以p为根的子树 if(p!=NULL)inorderChild(p-left);coutdataright);数据结构（C+版）叶核亚5按后根次序遍历二叉树的递归算法 void TreeNode1:postorderChild(Tre

10、eNode1*p)/后序遍历以p为根的子树 if(p!=NULL)postorderChild(p-left);postorderChild(p-right);coutdata;数据结构（C+版）叶核亚7.3.2 二叉树类的设计与实现 1二叉树类的声明类#include TreeNode1.h /二叉树的结点类class Tree1 /二叉树类 public:TreeNode1*root;/指向根结点的指针 Tree1(char*str=);Tree1();TreeNode1*create(char*str);/以标明空子树的先序遍历序列构建二叉树 void destroy(TreeNode1

11、*p);/撤销二叉树 void preorder();/先序遍历二叉树 void inorder();/中序遍历二叉树 void postorder();/后序遍历二叉树;数据结构（C+版）叶核亚2按3种次序遍历二叉树的成员函数 void Tree1:preorder()/先序遍历二叉树 coutpreorderChild(root);/调用TreeNode1类先序遍历二叉树的递归函数 coutendl;void Tree1:inorder()/中序遍历二叉树 coutinorderChild(root);/调用TreeNode1类中序遍历二叉树的递归函数 coutendl;void Tree

12、1:postorder()/后序遍历二叉树数据结构（C+版）叶核亚3.以标明空子树的先根次序遍历序列建立二叉树建立一棵二叉树必须明确以下两点：结点与双亲结点及孩子结点间的层次关系。兄弟结点间的左右子树的顺序关系。AB.(a)AB.AFDBCHEG.(d)ABD.G.CE.FH.AB.ABC.(b)A.B.(c)AB.C.数据结构（C+版）叶核亚以标明空子树的先根次序遍历序列建立二叉树算法 Tree1:Tree1(char*str)/构造函数 root=NULL;if(str!=)cout创建二叉树:endl;root=create(str);coutleft=NULL&p-right=NULL

13、)/叶子结点 n0+;if(p-left!=NULL&p-right!=NULL)/2度结点 n2+;property3(p-left,n0,n2);property3(p-right,n0,n2);数据结构（C+版）叶核亚7.3.3 建立二叉树的算法设计 以标明空子树的先根次序遍历序列建立二叉树1.建立链式存储结构的完全二叉树2.按先根和中根次序遍历序列建立二叉树3.以广义表表示建立二叉树数据结构（C+版）叶核亚7.3.4 二叉树遍历的非递归算法1.二叉树中根次序遍历的非递归算法描述如下：设置一个栈状态为空。从二叉树的根结点p开始，如果p不空或栈不空时，循环执行以下操作，直到走完二叉树且栈为

14、空状态。如果p不空，表示刚刚到达一个结点，将p结点入栈，进入左子树。如果p为空并且栈不空，表示已走出一条路径，此时必须返回寻找另一条路径。而返回的结点就是刚才经过的最后一个结点，它已保存在栈顶，所以由p指向出栈的结点，访问p结点，再进入p的右子树。数据结构（C+版）叶核亚0123top=-1AFDBCEG（a）二叉树及空栈，p指针从根结点开始root&D&B&AAFDBCEG（b）p指针沿着left链进入左子树，当p=NULL时,p返回栈顶元素结点root&B&AAFDBCEG（c）从D结点的左子树返回后，访问D结点rootp=NULL&G&B&AAFDBCEG（d）进入D的右子树,访问G结点

15、rootp&AAFDBCEG（e）从B结点的左子树返回后，访问B结点rootpAFDBCEG（f）从A结点的左子树返回后，访问A结点，此时栈又为空rootp&E&CAFDBCEG（g）进入A的右子树,最先访问E结点rootp&FAFDBCEG（h）访问C结点之后，进入C的右子树，访问F结点rootppAFDBCEG（i）访问完所有结点之后，p指针为空，栈为空rootp=NULLp数据结构（C+版）叶核亚二叉树中根次序遍历的非递归算法#include Tree1.h#include Stack2.h /链式栈类，模板void inorderT(Tree1&t1)/二叉树中根次序遍历的非递归算法

16、cout中序遍历二叉树:;Stack2 s2;/创建空栈，数据元素是指向二叉树结点的指针 TreeNode1*p=t1.root;while(p!=NULL|!s2.isEmpty()/p非空或栈非空时 if(p!=NULL)s2.push(p);/p结点入栈 p=p-left;/进入左子树 else /p为空且栈非空时数据结构（C+版）叶核亚7.3.5 按层次遍历二叉树1.按层次遍历二叉树的非递归算法描述如下：设置一个队列状态为空。从二叉树的根结点p开始，当p不空时，循环顺序执行以下操作：访问p结点。如果p的left链不空，将p结点的左孩子入队。如果p的right链不空，将p结点的右孩子入队

17、。由p指向出队的结点，继续。当队列为空时，出队方法返回null，循环停止。数据结构（C+版）叶核亚1&AAFDBCEG（a）二叉树的根结点入队root1&B&CAFDBCEG（b）p指针指向出队的结点,访问p结点，p的左右孩子结点入队rootp21&C&DAFDBCEG（c）p指针指向出队的结点,访问p结点，p的左右孩子结点入队rootp21&D&E&FAFDBCEG（c）p指针指向出队的结点,访问p结点，p的左右孩子结点入队rootp321&E&F&GAFDBCEG（c）p指针指向出队的结点,访问p结点，p的左右孩子结点入队rootp321AFDBCEG（c）队列空时,表示全部结点已访问过r

18、oot344567数据结构（C+版）叶核亚层次遍历二叉树算法#include Tree1.h /二叉树类#include Queue2.h /链式队列类，模板void level(Tree1&t1)/按层次遍历二叉树 cout按层次遍历二叉树:;Queue2 q2;/创建空队列，数据元素是指向二叉树结点的指针 TreeNode1*p=t1.root;q2.enQueue(p);/根结点入队 while(!q2.isEmpty()/队列不空时 p=q2.deQueue();/p指向出队的结点 coutdataleft!=NULL)q2.enQueue(p-left);/p的左孩子结点入队数据结构

19、（C+版）叶核亚7.4 线索二叉树7.4.1 线索二叉树的定义7.4.2 线索二叉树的结点类7.4.3 中序线索二叉树类数据结构（C+版）叶核亚7.4.1 线索二叉树的定义每个结点由5个域构成：data,left,right,ltag和rtag。指向前趋结点为线索指向左孩子,left 1left 0 ltag指向后继结点为线索指向右孩子,right 1right 0 rtag数据结构（C+版）叶核亚数据结构（C+版）叶核亚7.4.2 线索二叉树的结点类class ThreadTreeNode1 /线索二叉树的结点类 public:char data;/数据元素域 ThreadTreeNode1

20、*left,*right;/指向左、右孩子结点的指针域 int ltag,rtag;/左、右线索标志 ThreadTreeNode1(char ch=?)/构造函数，构造线索二叉树的结点 data=ch;left=right=NULL;ltag=rtag=0;ThreadTreeNode1()/析构函数为空;数据结构（C+版）叶核亚7.4.3 中序线索二叉树类1.中序线索二叉树类的声明下面声明的ThreadTree1类表示中序线索二叉树。文件名为ThreadTree1.h。声明如下：#include#include ThreadTreeNode1.h /线索二叉树的结点类class Threa

21、dTree1 /线索二叉树类 public:ThreadTreeNode1*root;/指向根结点的指针 ThreadTree1(char*str=);/构造函数 ThreadTreeNode1*create(char*str);/创建二叉树 void inThreadTree();/中序线索化二叉树 void inThreadTree(ThreadTreeNode1*p);/中序线索化以p结点为数据结构（C+版）叶核亚2二叉树的中序线索化void ThreadTree1:inThreadTree()/中序线索化二叉树 inThreadTree(root);void ThreadTree1:i

22、nThreadTree(ThreadTreeNode1*p)/中序线索化以p结点为根的子树 static ThreadTreeNode1*front=NULL;/front指向p的前驱结点 if(p!=NULL)inThreadTree(p-left);/中序线索化p的左子树 if(p-left=NULL)/p的左子树为空时 /设置p的left为指向front的线索 p-ltag=1;p-left=front;数据结构（C+版）叶核亚中序线索化二叉树的过程(a)D为第1个访问的结点rootpfront=NULLACDBHFErootACDBHFE100rootfrontACDBHFE100p1

23、(b)B为第2个访问的结点rootfrontACDBHFE100p1(c)G为第3个访问的结点01rootfrontACDBHFE100p1(e)A为第5个访问的结点0010rootfrontACDBHFE100p1(f)F为第6个访问的结点001010rootfrontACDBHFE100p1(g)H为第7个访问的结点0010101000001101011011frontp(h)C为第8个访问的结点GGGrootfrontACDBHFE100p1(d)E为第4个访问的结点001G011G11G11G11G11数据结构（C+版）叶核亚3中根次序遍历中序线索二叉树 （1）查找中根次序下的前驱或后

24、继结点ThreadTreeNode1*ThreadTree1:innext(ThreadTreeNode1*p)/返回中根次序下的后继结点 if(p-rtag=1)/右子树为空时 p=p-right;/right就是指向后继结点的线索 else /右子树非空时 p=p-right;/进入右子树 while(p-ltag=0)/找到最左边的子孙结点 p=p-left;return p;（2）中根次序遍历数据结构（C+版）叶核亚例7-5 中序线索二叉树的线索化与中序遍历。#include ThreadTree1.h /线索二叉树类void main()char*str=ABD.EG.CF.H.;/

25、标明空子树的先根次序 coutThe ThreadTree:str;ThreadTree1 t1(str);t1.inThreadTree();t1.inorder();程序运行结果如下：The ThreadTree:ABD.EG.CF.H.中序线索化：front=NULL p=D ltag=1 rtag=1front=D p=B ltag=0 rtag=0front=B p=G ltag=1 rtag=1数据结构（C+版）叶核亚7.5 堆排序1堆的定义堆是一个关键字序列（k1，k2，kn），它具有如下特性：Ki k2i 且 kik2i+1(i=1，2，n/2)将堆序列理解成具有下列特性的一棵

26、完全二叉树结点的层次序列。数据结构（C+版）叶核亚2 堆排序算法描述57326481(b)看成是一棵完全二叉树结点的层次序列,此时不是堆57326184(c)将以第i(i=4)个元素为根结点的子树调整成堆ij52376184(d)将第38个元素的子序列调整成堆ij52176384(e)将第28个元素的子序列调整成堆ij12376485(f)将第18个元素的子序列调整成堆,之后序列为堆,根值最小25376481(g)将根结点值交换到最后位置,再调整第17个元素的子序列为堆ij1(a)顺序存储的一个待排序的数据序列2345678编号5table374682112345678ij35426781(h

27、)将根结点值向后交换,再调整第16个元素的子序列为堆ij45628731(i)将根结点值向后交换,再调整第15个元素的子序列为堆ij58624731(j)将根结点值向后交换,再调整第14个元素的子序列为堆ij68724531(k)将根结点值向后交换,再调整第13个元素的子序列为堆ij76824531(l)将根结点值向后交换,再调整第12个元素的子序列为堆ij86724531(m)将根结点值向后交换,堆排序完成ij1(n)序列已按递减次序排序2345678编号8table7654321数据结构（C+版）叶核亚3.堆排序算法实现#include /堆排序const int N=8;void output(int table,int n);/输出数组的N个元素，略void swap(int table,int i,int j);/交换tablei、tablej的值，略void sift(int table,int left,int right)/将以第left个元素为根结点的子树调整成堆 int i,j,x;i=left;j=2*i;/第j个元素是第i个元素的左孩子 x=tablei;/获得第i个元素的值 while(j=right)if(jtablej+1)j+;/如果右孩子值较小时,j表示右孩子数据结构（C+版）叶核亚