数据结构第五章_11.ppt

第5章 树和二叉树（Tree Binary Tree）;树的基本概念 二叉树 遍历二叉树 线索二叉树 树的应用;树适于反应层次关系的数据对象的研究。层次化的数据之间可能有:祖先—后代、上级—下级、整体—部分等其它类似的关系。;5.1.1 树的定义 ;;若干术语;——即树的数据元素 ——结点挂接的子树数;A;5.2.1 二叉树的定义 定义：二叉树是n(n?0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成 特点 每个结点至多有二棵子树(即不存在度大于2的结点) 二叉树的子树有左、右之分，且其次序不能任意颠倒 基本形态;2. 二叉树的定义与树的定义的区别;3.满二叉树的定义 ;A;5.2.2 二叉树的性质 ;5.2.2 二叉树的性质 ;5.2.2 二叉树的性质 ;5.2.2 二叉树的性质 ;性质6;1;3. 深度为9的二叉树中至少有 个结点。 Ａ)２9 Ｂ)２8 Ｃ)９ Ｄ)２9－1; ;二叉树的抽象数据类型 ;二叉树的抽象数据类型 ;5.3.1 二叉树的存储结构;讨论：不是完全二叉树怎么办？;二、链式存储结构用二叉链表即可方便表示。;优点：①不浪费空间；②插入、删除方便 ;问：含有n个结点的二叉树中，共有链接域有2n个，空闲的（不用的）链接域有n+1个（为什么？） ;5.4.4 二叉树的其它操作 ;2)构造一棵二叉子树（或二叉树） ;A;5.4 二叉树链式存储结构下的操作;遍历规则———;A;A;A;+;A;构造二叉树：一步是先构造结点，第二步是将产生的结点联接在一起。 计算二叉树的深度：比较左子树和右子树的高度，取其最大值 删除二叉树 ：从叶子开始，先删除左子树，再删除右子树，最后删除根结点。 统计二叉树结点数 ：在遍历时，每次访问一个结点时，就在统计个数的计数器中加一。 插入结点或删除结点 ： ;5.4.2 二叉树的前序、中序、后序遍历操作 ;1）前序遍历的递归算法;主程序;前序遍历的非递归算法 DLR;非递归前序算法遍历思想：; ;二叉树的前序遍历非递归算法;二叉树的前序遍历非递归算法;2.中序遍历的递归算法 LDR ;中序遍历的非递归算法 ;表5.4.2 二叉树中序遍历非递归过程 ? ;do{ while (p) { //找最左子树 Push (S, p);//“根”结点（未访问）指针进栈，以后回朔时再退栈 p = p-LChild; //指针指向该“根”结点左子树 } if (!IsEmpty(S)) { //左子树为空时，利用堆栈回朔 Pop(S, p); //从堆栈中弹出回朔结点指针（该结点未访问过） cout p-data ; //访问“根”结点 p=p-RChild; //指针指向回朔结点的右子树 } }while （（p）|| !IsEmpty(S)）; ;3.二叉树的后序遍历 LRD;后序遍历的非递归算法 ;堆栈数据元素;非递归后序遍历算法思想：;A;while （（p）|| !IsEmpty(S)） if (p) //找最左子树 { temp.B = false; //准备进栈的结点进栈标志设为第一次进栈 temp.ptr = p; Push (S, temp);//“根”结点（未访问）指针及标志进栈，以后回朔时再退栈 p = p-LChild; //指针指向该“根”结点左子树 } else;;对遍历的分析：;5.4.3 二叉树的层次遍历操作 ;1.从上至下，从左至右（Top_Left）;while (p) { cout p-data ; //访问该结点 if (p-LChild) Enqueue(Q , p-LChild); //左子树进队 if (p-RChild) Enqueue(Q , p-RChild); //右子树进队 if (!DeQueue(Q , p)) return; //出队返回状码ERROR时结束（队空） } } ;2.从上至下，从右至左（Top_Right） ;程序设计 1.二叉???前序非递归遍历 ; 2.中序非递归遍历 ; 3.后序非递归遍历 ; 4.层次遍历 要求：建立如图的二叉树 ,结点为student,定义如下,给出遍历结果。 typedef struct { int num; //学号 char name[10]; //姓名 } student； typedef student EType;;3.关于从下至上算法讨论 ;2。求二叉树的高度 ;HL=0;3。删除二叉树