数据结构ppt 2016ppt 第7章

1、第7章 树和森林,本章主要内容,7.1 树的定义 7.2 树的存储结构 7.3 树的遍历 7.4 并查集 7.5 B树,树的应用,如族谱、等 级制度等,树的应用,分类,树的应用,文件系统、编译系统、 目录组织等方面,7.1 树的定义,树（Tree）是含有n（n0）个结点的有限集合。在任意一棵非空树中： （1）有且仅有一个特定的称为根（root）的结点； （2）当n1时，其余结点可分为m（m0）个互不相交的有限集T1, T2, , Tm，其中每一个集合本身又是一棵树。并且T1, T2, , Tm称为根的子树（SubTree）。,7.1 树的定义,森林(Forest)是m(m0)棵互不相交的树的集

2、合，可记为F = (T1, T2, T3,., Tm)。森林中所有树是有序的。对树中的每个结点而言，其子树的集合即为子树森林。,7.2 树的存储结构,存储结构要点：存储各结点本身的信息，还能表示树中各结点之间存在的关系。 7.2.1 双亲表示法 7.2.2 双亲孩子表示法 7.2.3 孩子兄弟表示法,7.2.1 双亲表示法,在树中，除根结点没有双亲（即父结点）外，其他结点的双亲是唯一确定的。 双亲表示法用数组存储树中结点及其关系。数组中的每个分量含有两个域: 元素值data和该结点的双亲位置parent。,B,C,D,E,F,A,7.2.1 双亲表示法,树的双亲存储结构的类型定义如下： typ

3、edef struct PTNode TElemType data; / 元素值 int parent; / 双亲位置，根结点的parent值为-1 PTNode; / 双亲结点类型 typedef struct PTNode *nodes; / 由初始化操作分配的结点数组 int r, nodeNum; / 根位置和结点数 PTree; / 树的双亲存储结构类型,7.2.2 双亲孩子表示法,双亲孩子表示法是对双亲表示法的扩展，为各结点构造孩子单链表。结点数组增加一个firstChild域作为结点的孩子链表的头指针。在孩子链表中，每个结点包含孩子在结点数组的位置childIndex和指向下一个

4、孩子结点的指针nextChild。,B,C,D,E,F,A,7.2.2 双亲孩子表示法,树的双亲孩子存储结构的类型定义为,typedef struct ChildNode int childIndex; / 孩子在结点数组的位置 struct ChildNode *nextChild; / 下一个孩子 ChildNode; / 孩子链表中的结点类型 typedef struct TElemtype data; / 元素值 int parent; / 双亲位置 struct ChildNode *firstChild; / 孩子链表头指针 PCTreeNode; / 双亲孩子结点类型 typed

5、ef struct PCTreeNode *nodes; / 结点数组 int nodeNum, r; / 结点元素个数,根位置 PCTree; / 树的双亲孩子存储结构类型,7.2.3 孩子兄弟表示法,孩子兄弟表示法采用二叉链式存储结构，每个结点包含3个域：元素值data、最左孩子指针firstChild和右兄弟指针nextSibling.,B,C,D,E,A,7.2.3 孩子兄弟表示法,树的孩子兄弟表示法的类型定义为 typedef struct CSTNode TElemType data; / 数据域 struct CSTNode *firstChild,*nextSibling; /

6、 最左孩子指针 、右兄弟指针 CSTNode,*CSTree,*CSForest; / 孩子兄弟链表,7.2.3 孩子兄弟表示法,基于孩子兄弟表示法的树的接口 CSTree MakeTree(TElemType e, int n, .); / 创建根结点e和n棵子树的树 int TreeDepth(CSTree T); / 返回树T的深度 StatusInsertChild(CSTreeT, inti, CSTreec);/ 插入c为T的第i棵子树，1id+1（d为T所指结点的度），c非空并与T不相交 .,可变参数的使用,使用可变参数应该有以下步骤（要加入): 1)首先在函数里定义一个va_l

7、ist型的变量,比如说是argptr,这个变量是指向参数的指针. /va_list argptr; 2)然后用va_start宏初始化变量argptr, va_start(argptr, n); /这个宏的第二个参数是第一个可变参数的前一个参数,是一个固定的参数. 3)然后用va_arg返回可变的参数,并赋值给变量p(CSTree类型). p = va_arg(argptr, CSTree) ; /va_arg的第二个参数是你要返回的参数的类型,这里是CSTree类型.然后你就可以在函数里使用第二个参数了.如果函数有多个可变参数的,依次调用va_arg获取各个参数. 4)最后用va_end宏结

8、束可变参数的获取. /va_end(argptr),创建树,CSTree MakeTree(TElemType e, int n, .),生成一个新结点t,其数据域的值为e,t = (CSTree)malloc(sizeof(CSTreeNode); if(NULL=t) return NULL; t-data = e; / 根结点的值为e t-firstChild = t-nextSibling = NULL;,t,e,创建树,CSTree MakeTree(TElemType e, int n, .),生成一个新结点t,其数据域的值为e 创建一棵树T，以t为根结点，其它n棵树为t的子树 i

9、f(nfirstChild = p; p1 = p; for(i=1; inextSibling = p; p1=p; va_end(argptr); return t;,t,e,B,E,C,D,创建树,CSTree MakeTree(TElemType e, int n, .),#include / 标准头文件，提供宏va_start、va_arg和va_end， / 用于存取变长参数表 CSTree MakeTree(TElemType e, int n, .) / 创建根结点e和n棵子树的树 int i; CSTree t, p, p1; va_list argptr; / argptr

10、是存放变长参数表信息的数组 t = (CSTree)malloc(sizeof(CSTreeNode); if(NULL=t) return NULL; t-data = e; / 根结点的值为e t-firstChild = t-nextSibling = NULL; if(nfirstChild = p; p1 = p; for(i=1; inextSibling = p; p1=p; va_end(argptr); return t; ,插入第i棵子树,StatusInsertChild(CSTreeT, int i, CSTreec),判断树空和插入位置的合理性 树非空，则插入从为树T

11、的第i棵子树，需要分成两种情况 1. i=1,if(NULL=T | inextSibling = T-firstChild; T-firstChild = c;/ c成为T的第1棵子树 ,T,e,B,E,C,D,F,c,插入第i棵子树,StatusInsertChild(CSTreeT, int i, CSTreec),判断树空和插入位置的合理性 树非空，则插入从为树T的第i棵子树，需要分成两种情况 2.1id+1,else p = T-firstChild;/ p指向T的第1棵子树 for(j=2;p!=NULL / 参数i过大 ,e,B,E,C,F,G,D,c,插入第i棵子树,Statu

12、sInsertChild(CSTreeT, int i, CSTreec),Status InsertChild(CSTree T, int i, CSTree c) / 插入c为T的第i棵子树，1id+1（d为T所指结点的度），c非空并与T不相交 int j, CSTree p; if(NULL=T | inextSibling = T-firstChild; T-firstChild = c; / c成为T的第1棵子树 else p = T-firstChild; for(j=2; p!=NULL ,7.2.3 孩子兄弟表示法,树与二叉树的等价性,7.2.3 孩子兄弟表示法,森林和二叉树之

13、间的对应关系,7.3 树和森林的遍历,树的遍历可有三种遍历算法 先序(次序)遍历: 若树不空，则先访问根结点，然后依次先序遍历各棵子树。 后序(次序)遍历: 若树不空，则先依次后序遍历各棵子树，然后访问根结点。 按层次遍历: 若树不空，则自上而下自左至右访问树中每个结点。,7.3树和森林的遍历,先序遍历时顶点的访问 次序：ABCDE 后序遍历时顶点的访问 次序：BDCEA 层次遍历时顶点的访问 次序：ABCED,B,C,E,D,A,7.3树和森林的遍历,树的遍历和二叉树遍历的对应关系？ 树 二叉树 先序遍历 先序遍历 后序遍历 中序遍历 森林的遍历与树遍历的关系？ 由森林与二叉树的一一对应关系

14、，可将森林划分成三个部分：根结点，根结点的子树森林（即对应二叉树的左子树）和除去第一棵树之外剩余的树构成的森林（简称剩余森林，即对应二叉树的右子树）。树是特例，是只有一棵树的森林，其剩余森林为空。以下讨论的森林的操作及实现都直接适用于树。,森林的先序遍历,Status PreOrderTraverseTree(CSTree T, Status(*visit)(TElemType),若森林采用孩子兄弟表示法，并且不为空，则其先序遍历过程为： （1）访问第一棵树的根结点； （2）遍历第一棵树的子树森林； （3）遍历剩余森林。,Status PreOrderTraverseForest(CSFore

15、st F, Status(*visit)(TElemType) / 先序遍历森林F if(NULL=F) return OK; / 森林为空 if(ERROR=visit(F-data) return ERROR; / 访问第一棵树的根结点 if(ERROR=PreOrderTraverseForest(F-firstChild, visit) return ERROR; / 递归先序遍历第一棵树的子树森林 return PreOrderTraverseForest(F-nextSibling, visit); / 递归先序遍历剩余森林 ,7.3 树和森林的遍历,森林的遍历应用求森林的深度 i

16、nt ForestDepth(CSForest F) / 求森林F的深度 int dep1, dep2, dep; if(NULL=F) dep = 0; / 森林为空，深度则为0 else dep1 = ForestDepth(F-firstChild); / 求第一棵树的子树森林的深度 dep2 = ForestDepth(F-nextSibling); / 求剩余森林的深度 dep = dep1+1dep2 ? dep1+1 : dep2; / 森林的深度 return dep; ,7.3 树和森林的遍历,森林的遍历应用查找 CSTreeNode* Search(CSForest F,

17、TElemType e) / 查找森林F中的结点e并返回其指针 CSTNode* result = NULL; if(NULL= F) return NULL; / 森林为空，返回NULL if(F-data=e) return T; / 找到结点，返回其指针 if(result = Search(F-firstChild, e)!=NULL) / 在第一棵树的子树森林查找 return result; return Search(F-nextSibling, e); / 在剩余森林中查找 ,7.4 并查集,背景：在集合的一些应用中，需要将n（n 0）个不同的元素划分为若干等价子集。这类问题的

18、一种解决方法是，首先令每个元素自成一个单元素集合，然后将等价的元素所属的集合合并。 并查集（Union Find Sets）是指由一组不相交子集（Disjoint Sets）所构成的集合，记作： S S1, S2, S3,., Sn 其中： 任意两个子集Si和Sj（1i, jn且ij）两两不相交 每个子集选取某个元素作为其标识，称为集合代表 例，已知并查集S = S1, S2 , S3，S11, 2, 4, 7，S23, 5, 8，S30, 6，子集S1、S2和S3两两不相交，元素1、3和0可分别为S1、S2和S3的代表元。,7.4 并查集,并查集通常需要以下两种操作： （1）查找某元素所属的

19、子集，简称查找（Find）操作； （2）合并两个元素所属的子集，简称合并（Union）操作。 为了高效地实现上述操作，可用森林 F =（T1, T2, T3,., Tn） 来表示并查集S，森林中的每棵树Ti（1in）表示并查集S中的一个子集Si，树中的每个结点表示Si中的一个元素。为操作方便，结点应含有指向其双亲结点的指针，并约定根结点作为代表元。,7.4 并查集,并查集可采用双亲表示法，类型定义如下： typedef struct / 森林结构 int *parent; / 双亲数组，其中数组下标表示元素，数组存储对应 / 元素所属树的双亲结点的位序，当为-1时，表示 / 是树的根结点 in

20、t n; / 森林中结点数目 PForest, MFSet; / 并查集类型 例：,7.4 并查集,并查集的基本操作定义为如下的接口 Status InitMFSet(MFSet / 合并并查集S中元素i和j所属的两个子集,Status InitMFSet(MFSet S.parentri = rj; else ,7.4 并查集,合并操作的时间复杂度：取决于查找长度，即树的高度。因此，降低操作时间复杂度即降低树的高度。 两种常用的方法 路径压缩（path compression）法：在查找结点所在树的根结点的过程中，令查找路径上的每个结点直接指向根结点。,int FindMFSet_CP(MF

21、Set / 结点当前拥有的关键字的个数 KeyType keym+1; / 关键字，key0未用 struct BTNode *parent; / 双亲结点指针 struct BTNode *ptrm+1; / 孩子结点指针数组 Record *recptrm+1; / 记录指针向量，0号单元未用 BTNode, *BTree; / B树的结点及指针类型,7.5.2 B树的查找,B树的查找过程是根据给定值查找结点和在结点的关键字中进行查找交叉进行。从根结点开始，重复以下过程： 若给定关键字等于结点中某个关键字Ki，则查找成功；若给定关键字比结点中的K1小，则进入指针A0指向的下一层结点继续查找

22、；若在两个关键字Ki和Ki+1之间，则进入它们之间的指针Ai指向的下一层结点继续查找；若比该结点所有关键字大，则在其最后一个指针An指向的下一层结点继续查找；若查找到叶子结点，则说明给定值对应的数据记录不存在，则查找失败。,查找36,查找108,36,7.5.2 B树的查找,7.5.2 B树的查找,typedef struct BTree pt;/ 指向找到的结点 int i;/ 1im，在结点中的关键字位序 int tag; / 1:查找成功，0:查找失败 result; / B树的查找结果类型,7.5.2 B树的查找,void SearchBTree(BTree t, int k, res

23、ult ,7.5.2 B树的查找,Search操作如下： /在p-key1.p-keynum找k int Search(BTree p, int k) int i = 1; while(i keynum ,7.5.3 B树的插入,B树的插入可描述为：利用前述的B树的查找过程查找关键字k的插入位置。若找到，则说明该关键字已经存在，直接返回；否则查找操作必失败于某个最底层的非终端结点上。在该结点插入，若其关键字总数n未达到m，算法结束；否则，需分裂结点。 分裂的方法是：生成一新结点，从中间位置把结点（不包括中间位置的关键字）分成两部分。前半部分留在旧结点中，后半部分复制到新结点中，中间位置的关键字

24、连同新结点的存储位置插入到父结点中。如果插入后父结点的关键字个数也超过m-1，则要再分裂。这个向上分裂过程如果持续到根结点分裂为止，则会产生新的根结点。,7.5.3 B树的插入,50, 20 40 , 80 ,插入关键字 = 60, 60 80 ,90,608090,90,50 80,60,30, 40 , 20 ,30 50 80,80,30,50,7.5.4 B树的删除,在B树上删除关键字k的过程可利用前述的B树的查找过程找出该关键字所在的结点，然后根据k所在结点是否为最下层非终端结点有不同的处理方法。 1若该结点为最下层非终端结点，首先将要删除的关键字k直接从该结点中删除。然后根据不同情

25、况分别作相应的处理，共有三种可能情况：,7.5.4 B树的删除,（1）如果被删关键字所在结点的原关键字个数n=m/2，说明删去该关键字后该结点仍满足B树的定义。这种情况最为简单，只需从该结点中直接删去关键字即可。,7.5.4 B树的删除,（2）如果被删关键字所在结点的关键字个数n等于m/2-1，说明删去该关键字后该结点将不满足B树的定义，需要调整。 调整过程为：如果其左右兄弟结点中有“富余”的关键字，即与该结点相邻的右（或左）兄弟结点中的关键字数目大于m/2-1。则可将右（左）兄弟结点中最小（大）关键字上移至双亲结点。而将双亲结点中小（大）于该上移关键字的关键字下移至被删关键字所在结点中。,7

26、.5.4 B树的删除,（3）如果相邻兄弟结点中没有“富余”的关键字，即相邻兄弟结点中的关键字数目均等于m/2-1。需把要删除关键字的结点与其左（或右）兄弟结点以及双亲结点中分割二者的关键字合并成一个结点，即在删除关键字后，该结点中剩余的关键字和指针，加上双亲结点中的关键字Ki一起，合并到Ai-1（或Ai）结点，即该删除关键字结点的左（右）兄弟结点。如果导致双亲结点中关键字个数小于m/2-1，则对此双亲结点做同样处理。如果直到对根结点也作合并处理，则整棵树减少一层。,7.5.4 B树的删除,2若该结点不是最下层非终端结点，且被删关键字为该结点中第i个关键字keyi，则可从指针ptri所指的子树中找出位于最下层非终