资源描述：
《论数据结构中二叉树的链式存储new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、*2010年8月安庆师范学院学报(自然科学版)Aug.2010第16卷第3期JournalofAnqingTeachersColege(NaturalScienceEdition)Vol.16No.3论数据结构中二叉树的链式存储刘影(安徽电子信息职业技术学院软件学院,安徽蚌埠233000)摘要:二叉树是树型结构中的重点研究对象。二叉树的操作是以二叉树的存储为基础,其存储主要包括顺序存储和链式存储,常用的是链式存储。目前研究者对二叉树的链式存储缺少一个全面、系统的分析。因此本文对二叉树的动态链式存储和静态链式存储进行了全面的
2、介绍,并对其进行了分析研究。关键词:二叉树;动态链式存储;静态链式存储中图分类号:TP311.12文献标识码:A文章编号:1007-4260(2010)03-0053-040引言在计算机领域中,树型结构是一类非常重要的非线性结构,其中二叉树最为常用,对二叉树的操作和存储比树相对简单。二叉树的存储一般采用顺序存储和链式存储。顺序存储是将一棵二叉树的结点存放于一组地址连续的存储单元中,这种存储结构对完全二叉树而言,既简单又节省存储空间。但对于一般二叉树,尤其对于单支结点较多的二叉树很不适合,由于对其存储也必须按完全二叉树的形式
3、存储二叉树中的结点,从而造成存储空间的浪费。因此,二叉树一般采用链式存储结构。二叉树的链式存储结构分为两种,一种是动态链式存储,另一种是静态链式存储。二叉树的动态链式存储是采用链表的形式存储二叉树,一般采用二叉链表和三叉链表。二叉树的静态存储是用一个数组存储二叉树的各个结点,数组中不仅保存每个结点的信息,还存储该结点左、右孩子在数组中的地址信息。下面分别对二叉树的动态链式存储和静态链式存储进行分析研究。1二叉树的动态链式存储二叉树的动态链式存储有两种形式,一是二叉链表,即链表中每个结点由三个域组成:数据域、左孩子指针和右孩
4、子指针。二为三叉链表,即在二叉链表的基础上,增加了一个指向双亲结点的指针。1.1二叉链表存储二叉链表的结点类型定义如下,结点结构如图1所示。图2为一棵一般的二叉树,图3为图2采用二叉链表存储的结构示意图。typedefstructnode{datatypedata;structnode*lchild,*rchild;图1二叉链表结点的存储结构}BiTNodeT;datatype为结点的数据类型,本文中均采用字符型。具体使用时需在程序中将datatype替换为char,或者在程序头部添加语句/#definedatatypec
5、har0(本文定义与算法均采用C语言编写)。利用二叉链表建立二叉树的一种算法如下:*收稿日期:2009-12-06作者简介:刘影,女,安徽砀山人,安徽电子信息职业技术学院讲师,研究生,主要从事程序设计、网络安全研究。#54#安庆师范学院学报(自然科学版)2010年1)算法BiTNodeT*CreateBitT(){charch;BiTNodeT*t=NULL;ch=getchar();/*接收键盘输入的字符*/if(ch=='*')/*输入的字符为'*'时,表示该结点为空*/t=NULL;else图2一棵一般的二叉树{t=
6、(BiTNodeT*)malloc(sizeof(BiTNodeT));t->data=ch;t->lchild=CreateBitT();/*创建左子树*/t->rchild=CreateBitT();/*创建右子树*/}returnt;}2)分析该算法在字符串输入时采用先序遍历的次序输入,一次性输入所有字符。图2存储结构的字符输入序列为ABD***CE**F**。图3二叉链表存储结构示意图对于一个二叉链表,一般用根指针作为二叉链表的名称,如图3可以称为二叉树T1或二叉链表T1。采用二叉链表建立二叉树,可以节省存储空间,
7、尤其对于单支结点比较多的二叉树,对于具有n(n>=1)个结点的二叉树中,共有2n个指针域,其中n-1个指针域用来指示结点的左、右孩子,其余n+1个指针域为空。但该存储方法不能随机地访问结点,对二叉树的遍历等算法实现过程也较复杂。1.2三叉链表存储三叉链表是在二叉链表的基础上,增加了指向该结点双亲结点的指针,类型定义如下,结点结构见图4所示。图5为图2采用三叉链表存储结构示意图。图4三叉链表结点的存储结构typedefstructnode{datatypedata;structnode*lchild,*rchild,*par
8、ent;}BiTNodeTh;利用三叉链表建立二叉树的一种算法如下:1)算法BiTNodeTh*CreateBitTh(){charch;图5二叉树的三叉链表存储结构示意图BiTNodeTh*t=NULL,*p;ch=getchar();/*接收键盘输入的字符*/if(ch=='*')/*输入的字符为'
