31构建二叉树的二叉链表存储结构.pdfVIP

Computer Education 教育与教学研究 文章编号：1672-5913(2008)06-0066-03 构建二叉树的二叉链表存储结构 王岁花，岳冬利 (河南师范大学 计算机与信息技术学院，新乡 453007) 摘 要：本文根据笔者多年的教学经验，介绍了四种构建二叉树的二叉链表存储结构的方法。 关键词：二叉树；链表；存储结构；递归 中图分类号：G642 文献标识码：B 1 引言 出了以下四种构建方法，希望能对同仁和学数据结构的学 生有所帮助。通过本文的学习，学生将会对二叉链表和递 《高等学校计算机科学与技术专业发展战略研究报 归有更深入的理解。 告暨专业规范》中将“计算机科学与技术”专业名称下的 人才培养规格归纳为三种类型、四个不同的专业方向：科 2 二叉树的二叉链表存储结构构建方法 学型(计算机科学专业方向) 、工程型(包括计算机工程专业 方向和软件工程专业方向) 、应用型(信息技术专业方向) 。 假设有关二叉树的二叉链表存储的类型定义如下： “数据结构”课程出现在四个专业方向的核心课程中，而 typedef struct BiTNode{ // 结点结构 树型结构同样无一例外的出现在了四个专业方向的核心 ElemType data ；//数据域 知识单元中。 struct BiTNode *Lchild ；//左孩子指针 树型结构描述的是研究对象之间一对多的关系。在存 struct BiTNode *Rchild；//右孩子指针 储树时，如果用指针来描述元素之间的父子关系，则由于 } BiTNode ，*BiTree ； 对每个元素的孩子数量没有限制(最小可以是 0，最多可以 说明：ElemType 为二叉树的元素值类型，根据具体 是树的度 d)，若结点的结构定义为一个数据域 data 和 d 个 情况进行定义，本文假设为 char 型；BiTNode 为结点类型； 指针域，则可以证明，有 n 个结点、度为 d 的树的多重链 BiTree 为指向 BiTNode 的指针类型。下面的算法均用类 C 表存储结构中，有 n*(d-1)+1 个空链域，采用这样的存储 描述。 将造成很大的浪费。 2.1 利用扩展二叉树的先序序列构建 二叉树是树型结构的一种特殊情况，对于它的操作 只根据二叉树的先序序列是不能唯一确定一棵二叉 和存储要比树简单的多，且树和森林可以用二叉链表做 树的。针对这一问题，可做如下处理：对二叉树中每个结 媒介同二叉树进行相互转换，所以对二叉树的研究就显 点的空指针引出一个虚结点，设其值为# ，表示为空，把 得特别重要。 这样处理后的二叉树称为原二叉树的扩展二叉树。扩展二 二叉树的二叉链表存储是二叉树的一种重要的存储 叉树的先序序列可唯一确定这棵二叉树。如图 1 所示，给 结构，在每一本“数据结构”教材中都占据了一定的篇幅， 出了一棵二叉树的扩展二叉树，以及该扩展二叉树的先序 但对于怎样建立一棵二叉树的二叉链表存储结构，却很少