二叉树链式存储结构(Binary Tree)

原创
2014/06/01 12:12
阅读数 672

二叉树链式存储结构(Binary Tree)

所谓二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示着元素的逻辑关系。通常有下面两种形式。

(1)二叉链表存储

链表中每个结点由三个域组成,除了数据域外,还有两个指针域,分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。结点的存储的结构为:

         

其中,data域存放某结点的数据信息;lchild与rchild分别存放指向左孩子和右孩子的指针,当左孩子或右孩子不存在时,相应指针域值为空(用符号∧或NULL表示)

整个二叉树可用一个指向根结点的指针表示,如下列右图所示二叉树的二叉链表如下列左图所示。

 

(2)三叉链表存储

每个结点由四个域组成,具体结构为:

       

其中,data、lchild以及rchild三个域的意义同二叉链表结构一样;parent域为指向该结点双亲结点的指针。这种存储结构既便于查找孩子结点,又便于查找双亲结点;但是,相对于二叉链表存储结构而言,它增加了空间开销。

图6.11给出了一棵二叉树的三叉链表示。

尽管在二叉链表中无法由结点直接找到其双亲,但由于二叉链表结构灵活,操作方便,对于一般情况的二叉树,甚至比顺序存储结构还节省空间。因此,二叉链表是最常用的二叉树存储方式

========END========

展开阅读全文
打赏
0
1 收藏
分享
加载中
更多评论
打赏
0 评论
1 收藏
0
分享
返回顶部
顶部