6章讲义1.ppt

1/30/202316.1 树的定义与基本术语树的定义与基本术语一、树的概念和基本术语一、树的概念和基本术语1/30/20232DHIJPANLKM树是由树是由n n个结点构成的有限集。个结点构成的有限集。n=0n=0为空树为空树n0n0为非空树为非空树1/30/20233DHIJPANLKM非空树的特点：非空树的特点：有且仅有一个根结点；有且仅有一个根结点；若若n1n1，则其余结点可以分为，则其余结点可以分为m m个互不相交个互不相交的有限集的有限集T T1 1,T,T2 2,T,Tm m，其中，每一个集合本其中，每一个集合本身又是一棵身又是一棵子树子树。T1T2T31/30/20234DHIJPANLKMT1T2T3有序树；无序树有序树；无序树第一个孩子；最后一个孩子第一个孩子；最后一个孩子1/30/20235结点结点:结点的度结点的度:树的度树的度:叶子结点（终端结点）叶子结点（终端结点）:分支结点（非终端结点）分支结点（非终端结点）:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJPNLKM内部结点：除根外的分支结点内部结点：除根外的分支结点1/30/20236孩子孩子结点结点双亲双亲结点结点兄弟兄弟结点结点堂堂兄弟兄弟祖先祖先结点结点子孙子孙结点结点结点的层次结点的层次:树的深度：树的深度：层次层次ABCDEFGHIJMKL假设根结点的层次为假设根结点的层次为1,1,第第l 层的层的结点的子树根结点的层次为结点的子树根结点的层次为l+1树中叶子结点所在的最大层次树中叶子结点所在的最大层次1 12 23 34 41/30/20237任何一棵非空树是一个二元组 Tree=（root，F）其中：其中：root 被称为根结点，F 被称为子树森林森林：森林：是 m（m0）棵互不相交的树的集合ArootBEFKLCGDHIJMF1/30/20238对比对比树型结构树型结构和和线性结构线性结构的结构特点的结构特点1/30/20239线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 (无前驱无前驱)根结点根结点 (无前驱无前驱)最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 (无后继无后继)其它数据元素其它数据元素(一个前驱、一个前驱、一个后继一个后继)其它数据元素其它数据元素(一个前驱、一个前驱、一个或多个后继一个或多个后继)1/30/202310二、二、树的类型定义树的类型定义1/30/202311数据对象数据对象 D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。若若D为空集，则称为空树；为空集，则称为空树；否则否则:(1)在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root,(2)当当n1时，其余结点可分为时，其余结点可分为m(m0)个互个互 不相交的有限集不相交的有限集T1,T2,Tm,其中每一其中每一 个子集本身又是一棵符合本定义的树，个子集本身又是一棵符合本定义的树，称为根称为根root的子树。的子树。数据关系数据关系 R：1/30/202312 基本操作：基本操作：查查 找找 类类 插插 入入 类类删删 除除 类类1/30/202313 Root(T)/求树的根结点求树的根结点 查找类：查找类：Value(T,cur_e)/求当前结点的元素值求当前结点的元素值 Parent(T,cur_e)/求当前结点的双亲结点求当前结点的双亲结点LeftChild(T,cur_e)/求当前结点的最左孩子求当前结点的最左孩子 RightSibling(T,cur_e)/求当前结点的右兄弟求当前结点的右兄弟TreeEmpty(T)/判定树是否为空树判定树是否为空树 TreeDepth(T)/求树的深度求树的深度TraverseTree(T,Visit()/遍历遍历1/30/202314InitTree(&T)/初始化，构造空树初始化，构造空树 插入类：插入类：CreateTree(&T,definition)/按定义构造树按定义构造树Assign(T,&cur_e,value)/给当前结点赋值给当前结点赋值InsertChild(&T,&p,i,c)/将将以以c为根的树为根的树插入为插入为T中结点中结点p的的第第i棵子树棵子树1/30/202315 ClearTree(&T)/将树清空将树清空 删除类：删除类：DestroyTree(&T)/销毁树的结构销毁树的结构DeleteChild(&T,&p,i)/删除结点删除结点p的第的第i棵子树棵子树1/30/202316ABCDEFGHIJMKLA()T1T3T2树根例如例如:B(E,F(K,L),C(G),D(H,I,J(M)1/30/2023176.2 二叉树二叉树1/30/2023186.2.1 二叉树的类型定义二叉树的类型定义1/30/202319 二叉树为有序树，其上的每个结点至多只有两棵子树，分别称为左子树和右子树。ABCDEFGHK根结点左子树右子树EF1/30/202320二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树1/30/202321 二叉树的主要基本操作二叉树的主要基本操作：查查 找找 类类插插 入入 类类删删 除除 类类1/30/202322 Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T,Visit();InOrderTraverse(T,Visit();PostOrderTraverse(T,Visit();LevelOrderTraverse(T,Visit();查查 找找 类类1/30/202323 InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(&T,&p,LR,c);插插 入入 类类初始条件：初始条件：P指向二指向二叉树中某个结点，叉树中某个结点，LR为为0或或1，非空二叉树，非空二叉树c右子树为空，且不与右子树为空，且不与T相交。相交。操作结果：操作结果：将树将树c插入为插入为T中中p结点的左子树或右子树，结点的左子树或右子树，而以而以p结点为根的原左或右子树则成为结点为根的原左或右子树则成为c的右的右子树。子树。1/30/202324ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(&T,&p,LR);删删 除除 类类初始条件：初始条件：P指向指向T中某个结点，中某个结点，LR为为0或或1操作结果：操作结果：根据根据LR为为0或或1，删除，删除P所指结所指结点的左子树或右子树。点的左子树或右子树。1/30/2023256.2.2二叉树的性质二叉树的性质1/30/202326 性质性质 1：在二叉树的第 i 层上至多有2i-1 个结点。(i1)性质性质 2：深度为 k 的二叉树上至多含 2k-1 个结点（k1）1/30/202327 性质性质 3：对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0=n2+11/30/202328两类两类特殊特殊的二叉树：的二叉树：满二叉树满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树完全二叉树：树中所含的 n 个结点和满二叉树中编号编号为为 1 至至 n 的结点的结点一一对应。123456789 10 11 12 13 14 15abcdefghij1/30/202329对于一棵完全对于一棵完全二叉树，其叶二叉树，其叶子结点只可能子结点只可能出现在层次最出现在层次最大的两层上；大的两层上；abcdefghij对于任一个结点，若其右分支下子孙的最对于任一个结点，若其右分支下子孙的最大层次为大层次为l，则其左分支下子孙的最大层次，则其左分支下子孙的最大层次必定为必定为l或或l+1。即对于任何一个结点，如。即对于任何一个结点，如果不是叶子结点，则必定存在左子树。果不是叶子结点，则必定存在左子树。1/30/202330 性质性质 4：具有 n 个结点的完全二叉树的深度深度为 log2n +1证明：证明：设设 完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n k 因为因为 k 只能是整数，因此，只能是整数，因此，k=log2n +1log2 n 1，则编号为 i/2 的结点为其双亲双亲结点;(2)若 2in，则该结点无左孩子，该结点为叶子。否则，编号为 2i 的结点为其左孩子左孩子结点；(3)若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子右孩子结点。1/30/2023326.2.3 二叉树的存储结构二叉树的存储结构二、二叉树的链式二、二叉树的链式 存储表示存储表示一、一、二叉树的顺序二叉树的顺序 存储表示存储表示1/30/202333#define MAX_TREE_SIZE 100 /二叉树的最大结点数typedef TElemType SqBiTreeMAX_TREE_SIZE;/0号单元存储根结点SqBiTree bt;一、一、二叉树的顺序存储表示二叉树的顺序存储表示1/30/202334二叉树的顺序存储表示方式二叉树的顺序存储表示方式存放元素的规则：存放元素的规则：从上到下、从左到右的顺序，依从上到下、从左到右的顺序，依次存放完全二叉树中的各个结点次存放完全二叉树中的各个结点对应的数据元素。对应的数据元素。1/30/202335例如例如:ABECGNDFHJLIKM014132635791181012 A B C D E F G H I J K L M 0 1 2 3 4 5 6 7 8 9 10 11 12 13N1/30/202336例如例如:A B C D E F 0 1 2 3 4 5 6 7 8 9 10 11 12 13ABDCEF1401326下标为下标为i的结点的左右孩子结的结点的左右孩子结点下标为：点下标为：2i+1和和2i+21/30/202337二、二叉树的链式存储表示二、二叉树的链式存储表示1.1.二叉链表二叉链表2三叉链表三叉链表3线索链表线索链表1/30/202338lchild data rchild结点结构结点结构:1.1.二叉链表二叉链表ABDCEF1/30/202339ACEBDF rootlchild data rchild结点结构结点结构:1.1.二叉链表二叉链表未占用指针的个数未占用指针的个数:n+11/30/202340typedef struct BiTNode /结点结构结点结构 TElemType data;struct BiTNode *lchild,*rchild;/左右孩子指针左右孩子指针 BiTNode,*BiTree;lchild data rchild结点结构结点结构:二叉链表的二叉链表的C 语言类型描述语言类型描述1/30/202341基本操作的函数原型说明基本操作的函数原型说明Status CreateBiTree(BiTree&T);/按先序秩序输入二叉树中结点的值，构造按先序秩序输入二叉树中结点的值，构造/二叉链表表示的二叉树二叉链表表示的二叉树Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e);/先序遍历二叉树先序遍历二叉树TStatus InOrderTraverse(BiTree T,Status(*Visit)(TElemType e);/中序遍历二叉树中序遍历二叉树T1/30/202342基本操作的函数原型说明基本操作的函数原型说明Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e);/后序遍历二叉树后序遍历二叉树TStatus LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e);/层序遍历二叉树层序遍历二叉树T1/30/202343visit是一个函数，可以是对结点的插入、删除是一个函数，可以是对结点的插入、删除和修改，可以是其他的操作，例如，最简单的和修改，可以是其他的操作，例如，最简单的Visit函数：输出结点数据的值。函数：输出结点数据的值。Status PrintElement(TElemType e)/输出元素输出元素e的值的值 printf(e);/return OK;1/30/2023442三叉链表三叉链表lchild data parent rchild 结点结构结点结构:abcd a b c d 1/30/202345 typedef struct TriTNode /结点结构结点结构 TElemType data;struct TriTNode *lchild,*rchild;/左右孩子指针 struct TriTNode *parent;/双亲指针 TriTNode,*TriTree;lchild data parent rchild结点结构结点结构:三叉链表的三叉链表的C 语言类型描述语言类型描述1/30/202346树的存储结构的选择依据：树的存储结构的选择依据：树的形态；树的形态；对树进行对树进行的基本操作。的基本操作。1/30/2023476.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树1/30/2023486.3.1二叉树的遍历二叉树的遍历1/30/202349顺着某一条搜索路径顺着某一条搜索路径巡访巡访二叉树二叉树中的结点，使得每个结点中的结点，使得每个结点均被访均被访问一次问一次，而且，而且仅被访问一次仅被访问一次。一、遍历二叉树一、遍历二叉树“访问访问”的含义可以很广，如：输出结的含义可以很广，如：输出结点的信息，对结点元素进行相应处理等。点的信息，对结点元素进行相应处理等。遍历：遍历：1/30/202350“遍历遍历”是任何数据结构类型均有的操作，是任何数据结构类型均有的操作，对线性结构而言，只有一条搜索路径对线性结构而言，只有一条搜索路径(因因每个结点均只有一个后继每个结点均只有一个后继)，故不需要另，故不需要另加讨论。加讨论。而二叉树是非线性结构，而二叉树是非线性结构，每个结点的后继每个结点的后继可以多达两个，也可以只有一个后继，或可以多达两个，也可以只有一个后继，或没有后继没有后继，则存在如何遍历，即按什么样，则存在如何遍历，即按什么样的的搜索路径搜索路径进行进行遍历的问题。遍历的问题。1/30/202351遍历的方法：遍历的方法：把二叉树上的复杂的结点关系变为一个把二叉树上的复杂的结点关系变为一个线性结构关系，使得线性结构关系，使得每个结点元素都有每个结点元素都有明确的唯一的一个直接前驱和一个直接明确的唯一的一个直接前驱和一个直接后继后继。即使得二叉树上的结点能够排列。即使得二叉树上的结点能够排列在一个线性队列上，这样就便于对结点在一个线性队列上，这样就便于对结点进行各种操作。进行各种操作。1/30/202352 对对“二二叉叉树树”而而言言，如如果果遍遍历历完完根根结结点点，左左子子树树和和右右子子树树，则则遍历完了整个二叉树。遍历完了整个二叉树。D:遍历根结点遍历根结点L:遍历左子树遍历左子树R:遍历右子树遍历右子树DLR,DLR,LDR,LRD,RDL,RLD限定先左后右：限定先左后右：DLR,LDR,LRD1/30/202353先先（根）序的遍历算法（根）序的遍历算法中中（根）序的遍历算法（根）序的遍历算法后后（根）序的遍历算法（根）序的遍历算法根根左子树右子树根根根根根根根根根根1/30/202354 若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1）访问根结点；）访问根结点；（2）先序遍历左子树；）先序遍历左子树；（3）先序遍历右子树。）先序遍历右子树。先（根）序的遍历算法：先（根）序的遍历算法：1/30/202355 若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1）中序遍历左子树；）中序遍历左子树；（2）访问根结点；）访问根结点；（3）中序遍历右子树。）中序遍历右子树。中（根）序的遍历算法：中（根）序的遍历算法：1/30/202356 若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1）后序遍历左子树；）后序遍历左子树；（2）后序遍历右子树；）后序遍历右子树；（3）访问根结点。）访问根结点。后（根）序的遍历算法：后（根）序的遍历算法：1/30/202357ABCDEFGHK例如：例如：先序先序序列：序列：中序序列：中序序列：后序序列：后序序列：A B C D E F G H KB D C A E H G K FD C B H K G F E A1/30/202358 若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1 1）访问根结点；）访问根结点；（2 2）先序遍历左子树；）先序遍历左子树；（3 3）先序遍历右子树。）先序遍历右子树。先（根）序的遍历算法先（根）序的遍历算法算法的递归描述算法的递归描述1/30/202359void PreorderTraverse(BiTree T,Status(*visit)(TElemType e)/先序遍历二叉树 if(T)if(visit(T-data)/访问根结点 if(PreorderTraverse(T-lchild,visit)/遍历左子树 if(PreorderTraverse(T-rchild,visit)/遍历右子树 return OK;return ERROR;else return OK;/PreorderTraverse 1/30/202360void preorder(BiTree*T)if(T!=NULL)printf(%dt,T-data);preorder(T-lchild);preorder(T-rchild);/先序遍历先序遍历主程序主程序Pre(T)先序遍历左子树先序遍历左子树先序遍历右指数先序遍历右指数程序中的先序遍历程序中的先序遍历1/30/202361主程序主程序Pre(T)返回返回返回返回pre(T R);返回返回返回返回ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回返回T左是空返回左是空返回pre(T R);T左是空返回左是空返回T右是空返回右是空返回T左是空返回左是空返回T右是空返回右是空返回pre(T R);先序序列：先序序列：A B D Cpre(T R);1/30/202362 若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1）中序遍历左子树；）中序遍历左子树；（2）访问根结点；）访问根结点；（3）中序遍历右子树。）中序遍历右子树。中（根）序的遍历算法中（根）序的遍历算法1/30/202363void InorderTraverse(BiTree T,Status(*visit)(TElemType e)/中序遍历二叉树 if(T)if(InorderTraverse(T-lchild,visit)/遍历左子树 if(visit(T-data)/访问根结点 if(InorderTraverse(T-rchild,visit)/遍历右子树 return OK;return ERROR;else return OK;/InorderTraverse 1/30/202364 若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1 1）后序遍历左子树；）后序遍历左子树；（2 2）后序遍历右子树；）后序遍历右子树；（3 3）访问根结点。）访问根结点。后（根）序的遍历算法后（根）序的遍历算法1/30/202365void PostorderTraverse(BiTree T,Status(*visit)(TElemType e)/后序遍历二叉树后序遍历二叉树 if(T)if(PostorderTraverse(T-lchild,visit)/遍历左子树遍历左子树 if(PostorderTraverse(T-rchild,visit)/遍历右子树遍历右子树 if(visit(T-data)/访问根结点访问根结点 return OK;return ERROR;else return OK;/PostorderTraverse 1/30/202366利用二叉树表示表达式：利用二叉树表示表达式：a+5+b*6-c/8表达式表达式=(第一操作数第一操作数)(运算符运算符)(第二操作数第二操作数)运算符运算符第一操作数第一操作数第二操作数第二操作数算术运算符或算术运算符或逻辑运算符逻辑运算符表达式或简单表达式或简单变量变量1/30/202367表达式在计算机内的表达方式表达式在计算机内的表达方式前缀表示（波兰式）前缀表示（波兰式）中缀表示中缀表示后缀表示（逆波兰式）后缀表示（逆波兰式）OP S1 S2+abS1 OP S2a+bS1 S2 OPab+1/30/202368表达式：表达式：a+b*(c-d)-e/f前缀表示（波兰式）：前缀表示（波兰式）：中缀表示：中缀表示：后缀表示（逆波兰式）：后缀表示（逆波兰式）：-+a*b-cd/efa+b*c-d-e/fabcd-*+ef/-操作数间的关系不变；操作数间的关系不变；运算符的相对秩序变了；运算符的相对秩序变了；中缀式没有意义；中缀式没有意义；1/30/202369表达式：表达式：a+b*(c-d)-e/f前缀表示（波兰式）：前缀表示（波兰式）：后缀表示（逆波兰式）：后缀表示（逆波兰式）：-+a*b-cd/efabcd-*+ef/-前缀式运算规则：从左向右扫描，连续出前缀式运算规则：从左向右扫描，连续出现的两个操作数和紧靠其前的操作符组成一现的两个操作数和紧靠其前的操作符组成一个最小的表达式；个最小的表达式；后缀式运算规则：从左向右扫描，运算符和后缀式运算规则：从左向右扫描，运算符和其前连续出现的两个操作数组成一个最小的表其前连续出现的两个操作数组成一个最小的表达式。达式。1/30/202370-+/a*b-efcd先序遍历：先序遍历：中序遍历：中序遍历：后序遍历：后序遍历：层次遍历：层次遍历：-+a*b-c d/e f-+a*b-cd/ef-+a*b-cd/e f-+a*b-c d/e fa+b*(c-d)-e/f前缀表示（波兰式）前缀表示（波兰式）中缀表示中缀表示后缀表示（逆波兰式）后缀表示（逆波兰式）1/30/202371四、中序遍历算法的非递归描述四、中序遍历算法的非递归描述递归工作栈：递归工作栈：递归过程执行过程中占用的数据区。递归过程执行过程中占用的数据区。递归工作记录：递归工作记录：每一层的递归参数组成一个记录。每一层的递归参数组成一个记录。当前活动记录：当前活动记录：栈顶记录指示当前层的执行情况。栈顶记录指示当前层的执行情况。当前环境指针：当前环境指针：递归工作栈的栈顶指针。递归工作栈的栈顶指针。ABCDEFGp1/30/202372中序遍历过程中递归工作栈的状态中序遍历过程中递归工作栈的状态工作记录中包括两项：其一是递归调用的语句编号；工作记录中包括两项：其一是递归调用的语句编号；其二为指向根结点的指针。其二为指向根结点的指针。如果栈顶记录中的指针值非空，则说明二叉树的根如果栈顶记录中的指针值非空，则说明二叉树的根结点存在，则应中序遍历这棵二叉树，即先遍历其结点存在，则应中序遍历这棵二叉树，即先遍历其左子树，将指向左子树根结点的指针压入栈顶；左子树，将指向左子树根结点的指针压入栈顶；如果栈顶记录中的指针值为空，则说明该二叉树不如果栈顶记录中的指针值为空，则说明该二叉树不存在，应该退到这个空二叉树的上一层。如果此时存在，应该退到这个空二叉树的上一层。如果此时是从左子树返回来的，则应立即访问栈顶指针所指是从左子树返回来的，则应立即访问栈顶指针所指的根结点。如果是从右子树返回的，则说明当前层的根结点。如果是从右子树返回的，则说明当前层访问完毕。访问完毕。1/30/202373void InorderTraverse(BiTree T,void(*visit)(TelemType e)/中序遍历算法的非递归描述中序遍历算法的非递归描述 IniStack(S);Push(S,T);while(!StackEmpty(S)/栈非空栈非空 while(GetTop(S,p)&pwhile(GetTop(S,p)&p)Push(S,pPush(S,p-lchildlchild););/向左进到叶子结点向左进到叶子结点 Pop(S,pPop(S,p););/弹出空的根结点弹出空的根结点 if(!StackEmpty(S)/栈非空栈非空 Pop(S,p);if(!Visit(p-data)return ERROR;/访问根结点，该根结点退出栈访问根结点，该根结点退出栈 Push(S,p-rchild);/右子树根结点进栈右子树根结点进栈 /end if /end while return OK;/InorderTraverse 1/30/202374ABCDEFGpA(1)ABCDEFGpAB(2)ABCDEFGpABC(3)p=NULLABCDEFGAB访问：C(4)1/30/202375pABCDEFGA访问：C B(5)ABCDEFGAD访问：C Bp(6)ABCDEFGADE访问：C Bp(7)ABCDEFGAD访问：C B Ep(8)1/30/202376ABCDEFGADG访问：C B Ep=NULL(9)ABCDEFGA访问：C B E G Dp(11)ABCDEFGAF访问：C B E G Dp(12)ABCDEFGAD访问：C B E Gp(10)1/30/202377ABCDEFGA访问：C B E G D Fp=NULL(13)ABCDEFG访问：C B E G D F Ap(14)ABCDEFG访问：C B E G D F Ap=NULL(15)1/30/202378void InorderTraverse(BiTree T,void(*visit)(TelemType e)IniStack(S);p=T;while(p|(!StackEmpty(S)/栈非空或还有右子树栈非空或还有右子树 if(p)Push(S,p);p=p-lchild;/压入非空根结点压入非空根结点 else Pop(S,p);if(!Visit(p-data)return ERROR;p=p-rchild;/查看右子树查看右子树 /end else/end while return OK;/InorderTraverse1/30/202379四四、遍历算法的应用举例遍历算法的应用举例2 2、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数3 3、求二叉树的深度、求二叉树的深度4 4、建立二叉树的存储结构、建立二叉树的存储结构1 1、查询二叉树中某个结点、查询二叉树中某个结点1/30/202380