第五章树.ppt
《第五章树.ppt》由会员分享,可在线阅读,更多相关《第五章树.ppt(115页珍藏版)》请在三一文库上搜索。
1、第五章 树,任课教员:张 铭 http:/ 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有,转载或翻印必究,北京大学信息学院 版权所有,转载或翻印必究 Page 2,主要内容,5.1 树的概念 5.2 树的链式存储 5.3 树的顺序存储 5.4 K叉树,北京大学信息学院 版权所有,转载或翻印必究 Page 3,5.1 树的概念,5.1.1 树和森林 5.1.2 森林与二叉树的等价转换 5.1.3 树的抽象数据类型 5.1.4 树的周游,北京大学信息学院 版权所有,转载或翻印必究 Page 4,树的逻辑结构,包含n个结点的有穷集合K (n0),且在K上定义了一个关系N,关系N满足以
2、下条件: 有且仅有一个结点k0K,它对于关系N来说没有前驱。结点k0称作树的根 除结点k0外,K中的每个结点对于关系N来说都有且仅有一个前驱 除结点k0外的任何结点kK,都存在一个结点序列k0,k1,ks,使得k0就是树根,且ks=k,其中有序对N(1is)。这样的结点序列称为从根到结点k的一条路径,北京大学信息学院 版权所有,转载或翻印必究 Page 5,树形结构的各种表示法,树的逻辑结构是: 结点集合K=A,B,C,D,E,F,G,H,I,J K上的关系N=, , ,,北京大学信息学院 版权所有,转载或翻印必究 Page 6,树形结构的各种表示法,(a)树形表示法,北京大学信息学院 版权所
3、有,转载或翻印必究 Page 7,树形结构的各种表示法,(b)文氏图表示法,北京大学信息学院 版权所有,转载或翻印必究 Page 8,树形结构的各种表示法,(c)凹入表表示法,北京大学信息学院 版权所有,转载或翻印必究 Page 9,树形结构的各种表示法,(A(B(D)(E(I)(J)(F)(C(G)(H),(d)嵌套括号表示法,北京大学信息学院 版权所有,转载或翻印必究 Page 10,树的定义,树是包括n个结点的有限集合T(n1),使得: 有一个特别标出的称作根的结点 除根以外的其它结点被分成m个(m0)不相交的集合T1,T2,Tm,而且这些集合的每一个又都是树。 树T1,T2,Tm称作这
4、个根的子树 这个定义是递归的,我们用子树来定义树:只包含一个结点的树必然仅由根组成,包含n1个结点的树借助于少于n个结点的树来定义,北京大学信息学院 版权所有,转载或翻印必究 Page 11,树结构中的概念,若N,则称k是k的父结点(或称“父母”),而k则是k的 子结点(或“儿子”、“子女”) 若有序对及N,则称k和k互为兄弟 若有一条由 k到达ks的路径,则称k是ks的祖先,ks是k的子孙 树形结构中,两个结点的有序对,称作连接这两结点的一条边,北京大学信息学院 版权所有,转载或翻印必究 Page 12,树结构中的概念,没有子树的结点称作树叶或终端结点 非终端结点称为分支结点 一个结点的子树
5、的个数称为度数 根结点的层数为0,其它任何结点的层数等于它的父结点结点的层数加1,北京大学信息学院 版权所有,转载或翻印必究 Page 13,树结构中的概念,有序树 在树T中如果子树T1,T2,Tm的相对次序是重要的,则称树T为有向有序树,简称有序树。 在有序树中可以称T1是根的第一棵子树,T2是根的第二棵子树,等等,北京大学信息学院 版权所有,转载或翻印必究 Page 14,森林与树,森林(forest) 森林是零棵或多棵不相交的树的集合(通常是有序集合)。 自然界的树和森林是不同的概念,而数据结构的树和森林只有微小的差别。删去树根,树就变成森林。加上一个结点作树根,森林就变成树,北京大学信
6、息学院 版权所有,转载或翻印必究 Page 15,森林与二叉树的等价转换,在树或森林与二叉树之间有一个自然的一一对应的关系。 任何森林都唯一地对应到一棵二叉树;反过来,任何二叉树也都唯一地对应到一个森林。 树所对应的二叉树里 一个结点的左子结点是它在原来树里的第一个子结点 右子结点是它在原来的树里的下一个兄弟,北京大学信息学院 版权所有,转载或翻印必究 Page 16,森林与二叉树的等价转换,北京大学信息学院 版权所有,转载或翻印必究 Page 17,森林到二叉树的等价转换,把森林F看作树的有序集合,F=(T1,T2,Tn),对应于F的二叉树B(F)的定义是: 若n=0,则B(F)为空 若n0
7、,则B(F)的根是T1的根W1,B(F)的左子树是B(T11,T12,T1m),其中T11,T12,T1m是W1的子树;B(F)的右子树是B(T2,Tn) 此定义精确地确定了从森林到二叉树的转换,北京大学信息学院 版权所有,转载或翻印必究 Page 18,森林到二叉树的等价转换,设B是一棵二叉树,rt是B的根,L是rt的左子树,R是rt的右子树,则对应于B的森林 F(B)的定义是: 若B为空,则F(B)是空的森林。 若B不为空,则F(B)是一棵树T1加上森林F(R),其中树T1的根为rt,rt的子树为F(L),北京大学信息学院 版权所有,转载或翻印必究 Page 19,树/森林的抽象数据类型,
8、template class TreeNode public: TreeNode(const T /返回右兄弟,北京大学信息学院 版权所有,转载或翻印必究 Page 20,树/森林的抽象数据类型,void setValue(T,北京大学信息学院 版权所有,转载或翻印必究 Page 21,树/森林的抽象数据类型,template class Tree public: Tree(); /构造函数 virtual Tree(); /析构函数 /返回树中的根结点 TreeNode* getRoot(); /创建树中的根结点,使根结点元素的值为rootValue void CreateRoot(cons
9、t T,北京大学信息学院 版权所有,转载或翻印必究 Page 22,树/森林的抽象数据类型,/返回current结点的父结点 TreeNode* Parent(TreeNode* current); /返回current结点的前一个邻居结点 TreeNode* PrevSibling(TreeNode* current); /删除以subroot为根的子树的所有结点 void DeleteSubTree(TreeNode* subroot); /先根深度优先周游树 void RootFirstTraverse(TreeNode* root); /后根深度优先周游树 void RootLastT
10、raverse(TreeNode* root); /宽度优先周游树 void WidthTraverse(TreeNode* root); ;,北京大学信息学院 版权所有,转载或翻印必究 Page 23,森林的周游,按深度的方向周游 先根次序: a)访问头一棵树的根 b)在先根次序下周游头一棵树树根的子树 c)在先根次序下周游其他的树 后根次序: a)在后根次序下周游头一棵树树根的子树 b)访问头一棵树的根 c)在后根次序下周游其他的树,北京大学信息学院 版权所有,转载或翻印必究 Page 24,先根深度优先周游森林,template void Tree:RootFirstTraverse(T
11、reeNode* root) while(root!=NULL) Visit(root-Value(); /访问当前结点 /周游头一棵树树根的子树 RootFirstTraverse(root-LeftMostChild(); root=root-RightSibling();/周游其他的树 ,北京大学信息学院 版权所有,转载或翻印必究 Page 25,后根深度优先周游森林,template void Tree:RootLastTraverse ( TreeNode* root) while (root !=NULL) /周游头一棵树树根的子树 RootLastTraverse (root-L
12、eftMostChild(); Visit (root-Value();/访问当前结点 root=root-RightSibling();/周游其他的树 ,北京大学信息学院 版权所有,转载或翻印必究 Page 26,深度优先周游森林,按先根次序周游森林正好等同于按前序法周游对应的二叉树 按后根次序周游森林正好等同于按中序法周游对应的二叉树 不方便仿照中序法定义树的中根周游,因为当一个根多于两个子结点时无法明确给出根与这些子结点的次序,北京大学信息学院 版权所有,转载或翻印必究 Page 27,宽度优先周游森林,template void Tree:WidthTraverse2(TreeNode
13、* root) using std:queue; /使用STL队列 queue* aQueue; TreeNode* pointer=root; if(pointer) aQueue.push(pointer); while(!aQueue.empty() pointer=aQueue.front();/取队列首结点指针,北京大学信息学院 版权所有,转载或翻印必究 Page 28,宽度优先周游森林,Visit(pointer-Value(); /访问当前结点 while(pointer-RightSibling() if(pointer-LeftMostChild()/左子结点进入队列 aQu
14、eue.push(pointer-LeftMostChild(); pointer=pointer-RightSibling(); Visit(pointer-Value(); /访问右兄弟结点 ,北京大学信息学院 版权所有,转载或翻印必究 Page 29,宽度优先周游森林,if(pointer-LeftMostChild() aQueue.push(pointer -LeftMostChild(); aQueue.pop(); /出队列 /end while /end if ,北京大学信息学院 版权所有,转载或翻印必究 Page 30,5.2 森林的链式存储,5.2.1 子结点表表示法 5.
15、2.2 左子结点/右兄弟结点表示法 5.2.3 动态结点表示法 5.2.4 动态“左子结点/右兄弟结点”二叉链表表示法 5.2.5 父指针表示法,北京大学信息学院 版权所有,转载或翻印必究 Page 31,子结点表表示法,每个分支结点均存储其子结点信息,子结点按照从左至右的顺序形成一个链表 “子结点表”表示法在数组中存储树的结点。每个结点包括结点值、一个父指针以及一个指向子结点链表的指针 结点的最左子结点可由链表的第一个表项直接找到 找到结点的右侧兄弟结点要困难一些,北京大学信息学院 版权所有,转载或翻印必究 Page 32,左子结点/右兄弟结点表示法,每个结点都存储结点的值,以及指向父结点、
16、最左子结点和右侧兄弟结点的指针 ADT的基本操作可通过读取结点中的一个值来实现。如果两棵树存储在同一个数组中,那么把其中一个添加为另一棵树的子树只需简单设置三个指针值即可。 这种表示法比子结点表表示法空间效率更高,而且结点数组中的每个结点仅需要固定大小的存储空间,北京大学信息学院 版权所有,转载或翻印必究 Page 33,动态结点表示法,为每个结点分配可变的存储空间 将一个指向子结点的指针数组作为结点的一部分分配给结点。实质上,每个结点存储一个基于数组的子结点指针表。在子结点的数目不变时,这种方法效果最佳;如果子结点的数目发生变动(特别是增加),就必须提供一种专门的校正机制来改变子结点指针数组
17、的大小 每个结点存储一条子结点指针链表。本质上 “子结点表”表示法相同,但是它动态地分配结点空间,而不是把结点分配在数组中,北京大学信息学院 版权所有,转载或翻印必究 Page 34,动态“左子结点/右兄弟结点” 二叉链表表示法,本质上,我们使用二叉树来替换树 新的结构中左子结点在树中是结点的最左子结点。右子结点是结点原来的右侧兄弟结点 可以很容易的把这种转化推广到森林,因为森林中每棵树的根结点可以看成互为兄弟结点 由于树的每个结点均包含固定数目的指针,而且树的ADT的每个函数均能有效实现,因此动态“左子结点/右兄第结点”表示法比以上介绍的其他方法更为常用,北京大学信息学院 版权所有,转载或翻
18、印必究 Page 35,树结点抽象数据类型的实现,/补充与具体实现相关的私有成员变量申明 private: T m_Value; /树结点的值 TreeNode* pChild; /左子结点 TreeNode* pSibling; /右兄弟结点 /公有成员函数的具体实现 templateTreeNode:TreeNode(const T ,北京大学信息学院 版权所有,转载或翻印必究 Page 36,树结点抽象数据类型的实现,template T TreeNode:Value() /返回结点的值 return m_Value; template bool TreeNode:isLeaf() /如
19、果结点是叶,返回true if(pChild=NULL) return true; return false; ,北京大学信息学院 版权所有,转载或翻印必究 Page 37,树结点抽象数据类型的实现,template TreeNode*TreeNode:LeftMostChild() /返回第一个左子结点 return pChild; template TreeNode* TreeNode:RightSibling() /返回右兄弟 return pSibling; templatevoid TreeNode:setValue(T ,北京大学信息学院 版权所有,转载或翻印必究 Page 38,
20、树结点抽象数据类型的实现,template void TreeNode:setChild(TreeNode* pointer) /设置左子结点 pChild=pointer; template void TreeNode:setSibling(TreeNode* pointer) /设置右兄弟 pSibling=pointer; ,北京大学信息学院 版权所有,转载或翻印必究 Page 39,树结点抽象数据类型的实现,template void TreeNode:InsertFirst(TreeNode* node) /以第一个子结点的身份插入结点 if(!pChild) pChild=node
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五
链接地址:https://www.31doc.com/p-2561281.html