考研专业课之统考计算机蓝宝书(24)
3.3 树和森林
3.3.1 树的存储结构
1. 双亲表示法
由树的定义可以知道,树中的每个结点都有唯一的一个双亲结点,根据这一特性,可用一组连续的存储空间(一维数组)存储树中的各个结点,数组中的一个元素表示树中的一个结点,数组元素为结构体类型,其中包括结点本身的信息以及结点的双亲结点在数组中的序号,树的这种存储方法称为双亲表示法。其存储表示可描述为:
此外,这种存储方式不能反映各兄弟结点之间的关系,所以实现RightSibling(t,x)操作也比较困难。在实际中,如果需要实现这些操作,可在结点结构中增设存放第一个孩子的域和存放第一个右兄弟的域,就能较方便地实现上述操作了。
2. 孩子表示法
(1). 多重链表法
由于树中每个结点都有零个或多个孩子结点,因此,可以令每个结点包括一个结点信息域和多个指针域,每个指针域指向该结点的一个孩子结点,通过各个指针域值反映出树中各结点之间的逻辑关系。在这种表示法中,树中每个结点有多个指针域,形成了多条链表,所以这种方法又常称为多重链表法。
在一棵树中,各结点的度数各异,因此结点的指针域个数的设置有两种方法:
① 每个结点指针域的个数等于该结点的度数;
② 每个结点指针域的个数等于树的度数。
对于方法①,它虽然在一定程度上节约了存储空间,但由于树中各结点是不同构的,各种操作不容易实现,所以这种方法很少采用;方法②中各结点是同构的,各种操作相对容易实现,但为此付出的代价是存储空间的浪费。
树中结点的存储表示可描述为:
(2). 孩子链表表示法
孩子链表法其主体是一个与结点个数一样大小的一维数组,数组的每一个元素有两个域组成,一个域用来存放结点信息,另一个用来存放指针,该指针指向由该结点孩子组成的单链表的首位置。单链表的结构也由两个域组成,一个存放孩子结点在一维数组中的序号,另一个是指针域,指向下一个孩子。
在孩子表示法中查找双亲比较困难,查找孩子却十分方便,故适用于对孩子操作多的应用。
这种存储表示可描述为:
3. 双亲孩子表示法
双亲表示法是将双亲表示法和孩子表示法相结合的结果。其仍将各结点的孩子结点分别组成单链表,同时用一维数组顺序存储树中的各结点,数组元素除了
包括结点本身的信息和该结点的孩子结点链表的头指针之外,还增设一个域,存储该结点双亲结点在数组中的序号。
4. 孩子兄弟表示法
在树中,每个结点除其信息域外,再增加两个分别指向该结点的第一个孩子结点和下一个兄弟结点的指针。在这种存储结构下,树中结点的存储表示可描述为:
>" src="http://i1.w.hjfile.cn/doc/200811/32502.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/32502.gif">>" src="http://i1.w.hjfile.cn/doc/200811/26508.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/26508.gif">>" src="http://i1.w.hjfile.cn/doc/200811/52955.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/52955.gif">>" src="http://i1.w.hjfile.cn/doc/200811/71602.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/71602.gif">>" src="http://i1.w.hjfile.cn/doc/200811/11087.gif" border=0 mce_src="http://i1.w.hjfile.cn/doc/200811/11087.gif">
猜你喜欢
- 出国留学中介前十名介绍 沪江是最好的选择
想要出国留学却没有时间没有精力去办理出国留学的手续,这个时候寻找一个好的出国留学中介就成了最好的办法,好的中介可以让自己更合理的去挑选自己喜欢的国家和学校,而且中介还有出国培训相关的内容,这...
- 日本动漫游戏:学校的圣域
feng社第9作第1弹《彼女のセイイキ(她的圣域)》,而系列的第2弹《妹的圣域》已于2015年08月28日发售,系列第3弹《学校的圣域》在2016年11月发售。
- 日本惊悚恐怖电影《裸体之夜:掠夺狂爱》
《裸体之夜2:掠夺狂爱》是由石井隆执导,竹中直人、佐藤宽子等领衔主演日本惊悚情色电影。该片讲述了主人公红次郎替年轻女孩加藤怜寻找叫“多绘”的救命恩人,结果踏入充满危机的“粉红”漩涡中。
- 秒变单身狗:哪些话不能对恋人说
恋爱初期总是美好而甜蜜的,然而两人长期处下来,就会发现对方的不足之处。生气起来口不择言,结果深深的伤害到两人的感情。这期给大家介绍一些对恋人可不能说的一些话。
- 日本礼仪:你真的会斟酒吗?
走进社会,我们不仅要在工作上努力努力再努力,还要一边学习一些社交礼仪。酒会作为一种常见的社交活动,学会其中的斟酒礼仪也是一门学问。今日,小编给大家整理了日本的斟酒礼仪供大家参考学习。
- 汉字词和成语 - 속담_뜻이 비슷한 속담
가재는 게와 생김새가 비슷하기 때문에 게 편을 든다는 말로, 서로 인연이 있는 것끼리 한편이 된다는 뜻이다. 비슷한 속담으로 '초록은 동색', … 가재는 게와 생김새가 비슷하기 때문에 게 ...