考研专业课之统考计算机蓝宝书(19)
3.2.2 二叉树的存储
1.顺序存储结
所谓二叉树的顺序存储,就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。这样结点在存储位置上的前驱后继关系并不一定就是它们在逻辑上的邻接关系,然而只有通过一些方法确定某结点在逻辑上的前驱结点和后继结点,这种存储才有意义。因此,依据二叉树的性质,完全二叉树和满二叉树采用顺序存储比较合适,树中结点的序号可以唯一地反映出结点之间的逻辑关系,这样既能够最大可能地节省存储空间,又可以利用数组元素的下标值确定结点在二叉树中的位置,以及结点之间的关系。
二叉树的顺序存储表示可描述为:
#define MAXNODE /*二叉树的最大结点数*/
typedef elemtype SqBiTree[MAXNODE] /*0号单元存放根结点*/
SqBiTree bt;
即将bt定义为含有MAXNODE个elemtype类型元素的一维数组。
2.链式存储结构
所谓二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示着元素的逻辑关系。通常有下面两种形式。
(1)二叉链表存储
链表中每个结点由三个域组成,除了数据域外,还有两个指针域,分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。结点的存储的结构为:
其中,data、lchild以及rchild三个域的意义同二叉链表结构;parent域为指
向该结点双亲结点的指针。这种存储结构既便于查找孩子结点,又便于查找双亲结点;但是,相对于二叉链表存储结构而言,它增加了空间开销。
>" 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:掠夺狂爱》是由石井隆执导,竹中直人、佐藤宽子等领衔主演日本惊悚情色电影。该片讲述了主人公红次郎替年轻女孩加藤怜寻找叫“多绘”的救命恩人,结果踏入充满危机的“粉红”漩涡中。
- 秒变单身狗:哪些话不能对恋人说
恋爱初期总是美好而甜蜜的,然而两人长期处下来,就会发现对方的不足之处。生气起来口不择言,结果深深的伤害到两人的感情。这期给大家介绍一些对恋人可不能说的一些话。
- 日本礼仪:你真的会斟酒吗?
走进社会,我们不仅要在工作上努力努力再努力,还要一边学习一些社交礼仪。酒会作为一种常见的社交活动,学会其中的斟酒礼仪也是一门学问。今日,小编给大家整理了日本的斟酒礼仪供大家参考学习。
- 汉字词和成语 - 속담_뜻이 비슷한 속담
가재는 게와 생김새가 비슷하기 때문에 게 편을 든다는 말로, 서로 인연이 있는 것끼리 한편이 된다는 뜻이다. 비슷한 속담으로 '초록은 동색', … 가재는 게와 생김새가 비슷하기 때문에 게 ...