树的存储结构 – 数据结构和算法41
树的存储结构
让编程改变世界
Change the world by program
树的存储结构
不好意思哈,这节课又需要大家搞脑子了。对于知识,你理解的越多,需要记住的就越少!
上节课我们简单的介绍了树结构的强大,这节课我们来关心一下如何在内存中安排树这种结构的存放。
说到存储结构,就会想到我们前面章节讲过的顺序存储和链式存储两种基本结构。
对于线性表来说,很直观就可以理解,但对于树这种一对多的结构,我们应该怎么办呢?
要存储树,简单的顺序存储结构和链式存储结构是不能滴!不过如果充分利用它们各自的特点,完全可以间接地来实现。
大家先思考下,如果你是总工程师,让你来设计和规划,你有多少种方法可以实现对树结构的存放?
当然你要考虑到双亲、孩子、兄弟之间的关系。
小甲鱼这里要介绍三种不同的表示法:双亲表示法、孩子表示法、孩子兄弟表示法。
双亲表示法
双亲表示法,言外之意就是以双亲作为索引的关键词的一种存储方式。
我们假设以一组连续空间存储树的结点,同时在每个结点中,附设一个指示其双亲结点在数组中位置的元素。
也就是说,每个结点除了知道自己是谁之外,还知道它的粑粑妈妈在哪里。
那么我们可以做如下定义:parent.c
这样的存储结构,我们可以根据某结点的parent指针找到它的双亲结点,所用的时间复杂度是O(1),索引到parent的值为-1时,表示找到了树结点的根。
可是,如果我们要知道某结点的孩子是什么?那么不好意思,请遍历整个树结构。
这真是麻烦,能不能改进一下呢?
鱼油们怎么看?
电视机前的小盆友们怎么看?
当然可以,我们只需要稍微改变一下结构即可:
那现在我们又比较关心它们兄弟之间的关系呢?
存储结构的设计是一个非常灵活的过程,只要你愿意,你可以设计出任何你想要的奇葩!
一个存储结构设计得是否合理,取决于基于该存储结构的运算是否适合、是否方便,时间复杂度好不好等等。
不要拘泥于你所学过的有限的数据类型,要把思维放开些,放开些,放开些!
当你的思维放开了,世界就变小了!
当你的思维放开了,知识就变少了!
备用视频下载
技术, IT技术, 数据结构和算法, 存储
风险提示及免责条款
市场有风险,投资需谨慎。本文不构成个人投资建议,也未考虑到个别用户特殊的投资目标、财务状况或需要。用户应考虑本文中的任何意见、观点或结论是否符合其特定状况。据此投资,责任自负。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场,不承担相关法律责任。如若转载,请注明出处。 如若内容造成侵权/违法违规/事实不符,请点击【内容举报】进行投诉反馈!