构建二叉树的二叉链表存储结构

hustjw

贡献于2011-05-19

字数:0 关键词:

66 Computer Education 教育与教学研究 文章编号:1672-5913(2008)06-0066-03 构建二叉树的二叉链表存储结构 王岁花,岳冬利 (河南师范大学 计算机与信息技术学院,新乡 453007) 摘 要:本文根据笔者多年的教学经验,介绍了四种构建二叉树的二叉链表存储结构的方法。 关键词:二叉树;链表;存储结构;递归 中图分类号:G642 文献标识码:B 1 引言 《高等学校计算机科学与技术专业发展战略研究报 告暨专业规范》中将“计算机科学与技术”专业名称下的 人才培养规格归纳为三种类型、四个不同的专业方向:科 学型(计算机科学专业方向)、工程型(包括计算机工程专业 方向和软件工程专业方向)、应用型(信息技术专业方向)。 “数据结构”课程出现在四个专业方向的核心课程中,而 树型结构同样无一例外的出现在了四个专业方向的核心 知识单元中。 树型结构描述的是研究对象之间一对多的关系。在存 储树时,如果用指针来描述元素之间的父子关系,则由于 对每个元素的孩子数量没有限制(最小可以是 0,最多可以 是树的度 d),若结点的结构定义为一个数据域 data 和 d 个 指针域,则可以证明,有 n 个结点、度为 d 的树的多重链 表存储结构中,有 n*(d-1)+1 个空链域,采用这样的存储 将造成很大的浪费。 二叉树是树型结构的一种特殊情况,对于它的操作 和存储要比树简单的多,且树和森林可以用二叉链表做 媒介同二叉树进行相互转换,所以对二叉树的研究就显 得特别重要。 二叉树的二叉链表存储是二叉树的一种重要的存储 结构,在每一本“数据结构”教材中都占据了一定的篇幅, 但对于怎样建立一棵二叉树的二叉链表存储结构,却很少 提及。笔者从事“数据结构”课程教学已二十余年,总结 出了以下四种构建方法,希望能对同仁和学数据结构的学 生有所帮助。通过本文的学习,学生将会对二叉链表和递 归有更深入的理解。 2 二叉树的二叉链表存储结构构建方法 假设有关二叉树的二叉链表存储的类型定义如下: typedef struct BiTNode{ // 结点结构 ElemType data ;//数据域 struct BiTNode *Lchild ;//左孩子指针 struct BiTNode *Rchild;//右孩子指针 } BiTNode ,*BiTree ; 说明:ElemType 为二叉树的元素值类型,根据具体 情况进行定义,本文假设为 char 型;BiTNode 为结点类型; BiTree 为指向 BiTNode 的指针类型。下面的算法均用类 C 描述。 2.1 利用扩展二叉树的先序序列构建 只根据二叉树的先序序列是不能唯一确定一棵二叉 树的。针对这一问题,可做如下处理:对二叉树中每个结 点的空指针引出一个虚结点,设其值为#,表示为空,把 这样处理后的二叉树称为原二叉树的扩展二叉树。扩展二 叉树的先序序列可唯一确定这棵二叉树。如图 1 所示,给 出了一棵二叉树的扩展二叉树,以及该扩展二叉树的先序 序列。 收稿日期:2007-12-15 作者简介:王岁花,副教授,主要研究方向是语义 Web 和课程教学论。 项目资助:河南师范大学教学研究基金资助 67 Computer Education 教育与教学研究 建立二叉链表的算法如下: void Create(BiTree &T) {//输入扩展二叉树的先序序列,构建二叉链表 scanf(&ch); //输入一个元素 if (ch=='# ') T = NULL; else { T= (BiTree)malloc(sizeof(BiTNode)); //申请根结点 T->data =ch; // 给根结点数据域赋值 Create(T->Lchild);//建左子树 Create(T->Rchild);//建右子树 } } // Create 2.2 利用二叉树的先序序列和中序序列 容易证明:由一棵二叉树的先序序列和中序序列可唯 一确定一棵二叉树。 基本思想:先根据先序序列的第一个元素建立根结点; 然后在中序序列中找到该元素,确定根结点的左、右子树的 中序序列;根据左、右子树的中序序列确定左、右子树中结 点的个数;再根据结点个数在先序序列中确定左、右子树的 先序序列;最后由左子树的先序序列与中序序列建立左子 树,由右子树的先序序列与中序序列建立右子树。 显然,这是一个递归过程。假设先序序列放在数组 pre[0..n-1]中,中序序列放在数组 mid[0..n-1]中,n 是二叉 树中元素的个数,其算法如下: int Find(ElemType *P, int L2 ,int H2, ElemType x) {//在数组 P 的区间 L2..H2 内确定 x 的位置 i=L2; while(P[i]!=x) i++; return i; }// Find void Create (BiTree &T, int L1, int H1, int L2, int H2) {//已知先序序列 pre[L1..H1], //中序序列 mid[L2..H2]构建二叉链表 if (L2>H2) T=NULL; //建空树 else { T =(BiTree)malloc(sizeof(BiTNode)); //创建根结点 T T ->data=pre[L1]; //给根数据域赋值 k=Find(mid, L2, H2, pre[L1]); //找根在中序序列的位置 Create (T ->Lchild, L1+1,k+L1-L2, L2,k-1); //创建左子树 Create(T->Rchild,k+L1-L2+1,H1,k+1, H2); //创建右子树 } }// Create 2.3 利用扩展完全二叉树的顺序存储 约定对二叉树上的结点从根结点起,自上而下,自左 而右进行连续编号,根结点的编号为 1。深度为 k 的,有 n 个结点的二叉树,当且仅当其每个结点的编号都与深度 为 k 的满二叉树中编号为 1 至 n 中的结点一一对应时,称 其为完全二叉树。 如果一棵二叉树不是完全二叉树,可以用添加虚结点 的方式将其扩展为一棵完全二叉树。虚结点的值设为#, 表示该结点不存在,把这样处理后的二叉树称为原二叉树 的扩展完全二叉树。如图 2 中的(a)不是完全二叉树,(b) 为(a)的扩展完全二叉树。 完全二叉树的性质:如果一棵完全二叉树有n个结点, 则有 1)编号为 i 的结点如果有左孩子,则左孩子的编号为 2i;2)如果有右孩子,则右孩子的编号为 2i+1。 基本思想: 1) 将二叉树扩展为一棵完全二叉树; 2) 根据编号将结点的值依次放在数组 s 的 s[1..n]中; 3) 根据完全二叉树的性质,构造二叉树的二叉链表 存储结构。这里 n 为扩展完全二叉树的结点个数,如图 2 中的 n 为 11。 对于第 3)步,s[1]是二叉树的根结点,如果 2<=n 则 s[2]是 s[1]的左孩子,否则左孩子为空;如果 3<=n,则 s[3] 68 Computer Education 教育与教学研究 是 s[1]的右孩子,否则右孩子为空;一般的,对于 s[i]: if (s[i]== '#' ) then 建空树; else { if (2i<=n) then s[2i]是 s[i]的左孩 子 else 左孩子为空; if (2i+1<=n) then s[2i+1]是 s[i]的右孩子; else 右孩子为空; } 显然,这是一个递归过程。其算法如下: void Create (Bitree &T , ElemType *s, int i, int n) {//创建一棵以 s[i]值为根的值的二叉树的二 //叉链表,树的根为 T if(s[i]=='#') T =NULL; else { T =(BiTree)malloc(*sizeof(BiTNode)); //申请根结点 T ->data=s[i]; // 给根结点的数据域赋值 j=2*i; if (j<=n) //创建左子树 Create (T->Lchild , s, j, n); else T->Lchild=NULL; j++; if(j<=n) //创建右子树 Create (T ->Rchild , s, j, n); else T ->Rchild=NULL; } }// Create 2.4 利用二叉排序树的性质 基本思想:从一棵空二叉树出发,按照先序序列依次 插入各结点。假设先序列放在 pre[1..n]中,中序序列放在 mid[1..n]中,这里 n 是二叉树的结点个数。pre[1]是树的根, pre[i](i=2,3,…n)究竟插在左子树上还是右子树上,则要看 pre[i]在中序序列中的位置,如果 pre[i]在 pre[1]的之前,则 插入到左子树上,否则插在右子树上。为此可定义一个函 数 Find 来确定结点在中序序列中的位置。 Find:pre[1..n]Æ1..n 定义如下: 如果 pre[i]=mid[j] 则 Find(pre[i])=j ; 这样,对于 pre[1..n]中的每个元素(即树上的每个结点) 都赋予了一个值,根据 pre[1..n] 和赋予每个元素 pre[i](i=1,2…n)的 Find(pre[i])值,按照构造二叉排序树的方 法依次插入各结点,建立二叉树。其算法如下: int Find (ElemType *mid , int n, ElemType x) {//求 x 在中序序列中的位置 for( j=1;j<=n ; j++) if(x==mid[j]) return j; }// Find void Insert_Node(Bitree &T , Bitree s) {//将 s 插在以 T 为根的二叉树的合适位置上 if (T==NULL) T=s; //在空树上插入 s else { if(Find(T->data)>Find(s->data)) //将 s 所指结点插在左子树上 Insert_Node(T->Lchild,s); else //将 s 所指结点插在右子树上 Insert_Node(T->Rchild,s); }// Insert_Node void Create (Bitree &T, int n) {//建有 n 个结点的二叉树的二叉链表 T=NULL; //先建立一棵空树 for(j=1;j<=n;j++) { //依次产生结点和插入结点 s= (BiTree)malloc(*sizeof(BiTNode)); s ->data=pre[j]; s->Lchild=NULL; s->Rchild=NULL; Insert_Node(T,s);//插入 s } }// Create 参考文献 [1] 教育部高等学校计算机科学与技术教学指导委员会. 高等学校计算机科学与技术专业发展战略研究报告暨专业规范[R]. 北京:高等教育出版社,2006. [2] 严蔚敏,吴伟民. 数据结构(C 语言版)[M]. 北京:清华大学出版社,1997:124-125,136.

下载文档,方便阅读与编辑

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 15 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档

相关文档