预览加载中，请您耐心等待几秒...

数据结构-树(2)-严蔚敏版.ppt

预览
1/10
2/10
3/10
4/10
5/10
6/10
7/10
8/10
9/10
10/10

亲，该文档总共92页，到这已经超出免费预览范围，如果喜欢就直接下载吧～

下载提示 文本预览

如果您无法下载资料，请参考说明：

1、部分资料下载需要金币，请确保您的账户上有足够的金币

2、已购买过的文档，再次下载不重复扣费

3、资料包下载后请先用软件解压，在使用对应软件打开

第六章树A二、基本术语 结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支 结点的度(degree)——结点拥有的子树数 叶子(leaf)——度为0的结点 孩子(child)——结点子树的根称为该结点的孩子 双亲(parents)——孩子结点的上层结点叫该结点的~ 兄弟(sibling)——同一双亲的孩子 树的度——一棵树中最大的结点度数 结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层…… 深度(depth)——树中结点的最大层次数 森林(forest)——m(m0)棵互不相交的树的集合A树和线性结构的比较：6.2二叉树 定义 定义：二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成 特点 每个结点至多有二棵子树(即不存在度大于2的结点) 二叉树的子树有左、右之分，且其次序不能任意颠倒 二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念 基本形态二叉树的基本操作：二叉树性质 性质1：性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1几种特殊形式的二叉树 满二叉树 定义：1性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1in)，有： (1)如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是i/2 (2)如果2i>n，则结点i无左孩子；如果2in，则其左孩子是2i (3)如果2i+1>n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1三、二叉树的存储结构 1.顺序存储结构 实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素 特点： 结点间关系蕴含在其存储位置中 浪费空间，适于存满二叉树和完全二叉树2.链式存储结构 二叉链表基于该存储结构的二叉树基本操作有：三叉链表6.3遍历二叉树二叉树的遍历 方法 先序遍历：先访问根结点,然后分别先序遍历左子树、右子树 中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树 后序遍历：先后序遍历左、右子树，然后访问根结点 按层次遍历：从上到下、从左到右访问各结点AAA-算法 递归算法 1、先序遍历递归算法 void(PreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){ //采用二叉链表存贮二叉树，visit()是访问结点的函数。本算法先序遍历以为根结点指针的二叉树 if(T){//若二叉树为空，结束返回//若二叉树不为空，访问根结点；遍历左子树，遍历右子树 Visit(T->data)；PreOrderTraverse(T->lchild,Visit);PreOrderTraverse(T->rchild,Visit); } }//PreOrderTraverse 最简单的Visit函数是：statusPrintElement(TElemTypee){//输出元素e的值printf(e);ACDB先序序列：ABCD returnOK;}2、中序遍历递归算法3、后序遍历递归算法非递归法遍历二叉树1pAA中序非递归遍历2遍历算法应用 按先序遍历序列建立二叉树的二叉链表，已知先序序列为： ABCDEGF补充：层次遍历算法线索二叉树线索二叉树 定义： 前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为~ 线索：指向前驱或后继结点的指针称为~ 线索二叉树：加上线索的二叉链表表示的二叉树叫~ 线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫~ 实现 在有n个结点的二叉链表中必定有n+1个空链域 在线索二叉树的结点中增加两个标志域 lt:若lt=0,lc域指向左孩子；若lt=1,lc域指向其前驱 rt:若rt=0,rc域指向右孩子；若rt=1,rc域指向其后继 结点定义：AAAA算法 按中序线索化二叉树算法 按中序线索化二叉树算法 按中序线索化二叉树算法 按中序线索化二叉树算法 按中序线索化二叉树算法 按中序线索化二叉树算法 按中序线索化二叉树算法 按中序线索化二叉树算法 按中序线索化二叉树算法 按中序线索化二叉树算法 按中序线索化二叉树算法 按中序线索化二叉树算法 按中序线索化二叉树算法 按中序线索化二叉树算法 按中序线索化二叉树算法 按中序线索化二叉树算法 按中序线索化二叉树算法 按中序线索化二叉树 遍历中序线索二叉树例1：编写求二叉树中叶子结点个数的算法6.4树和森林 6.4.1树的存储结构 双亲表示法 实现：定义结构数组存放树的结点，每个结点含两个域： 数据域：存放结点本身信息 双亲域：指示本结点的双亲结点在数组中位置 特点：找双亲容易，找孩子难a二、孩子表示法 1、多重链表