第五章树和二叉树说课教案
姓名：仇环
单位：信息工程系
年级与科目：08级计算机应用《数据结构》
课题：树和二叉树
职称：讲师
教龄：1年
（各位老师下午好，我说课的题目是树和二叉树）
说课的内容包括：
一．教学大纲分析
二．教材分析
三、学情分析
四．教学目标
五、教学重点与难点
六、教学方法
七、教学过程
八、教学效果预测及教学后记
一、教学大纲分析：
高职高专教育的人才培养特征是高级技术应用型人才，具体到计算机专业来说，就是培养从事计算机产品生产、维修和编程和实际应用的技术人才。在计算机专业的课程体系中，《数据结构》不仅是一门重要的专业基础课程，而且是计算机程序设计重要的理论基础，更
是计算机等级、专升本等考试的必考课程之一。它在整个学科体系中具有重要作用，有着不可替代的地位。
本课程的教学不仅重视学生对理论知识的理解和掌握，锻炼学生抽象思维能力和想象能力，更注重实践动手的能力，要求学生能够设计出结构清晰、可读性好、运行效率高的算法，并能够用一种或多种计算机高级程序设计语言实现。学好这门课程，对培养学生程序设计的能力、设计算法的能力和运用计算机进行数据处理的能力有着深远的意义。
其前导课程为：《C语言程序设计》或《C++语言》。
二、教材分析
本教材属于“21世纪高职高专规划教材”，这套教材主要面向高职高专院校学生。教材内容力求体现以应用为主体，强调理论知识的理解和运用，实现专科教学以实践体系及技术应用能力培养为主的目标。
1、教材特点：
本教材的特点可总结为：
（1）基础理论知识的阐述由浅入深、通俗易懂。内容的组织和编排以应用为主线，省略了一些理论推导和数学证明过程，淡化了算法的设计分析和复杂的时空分析。
（2）各章都配有应用举例，列举分析了很多实用的例子，且大多数算法都直接给出了相应的C语言程序，以便上机练习和实践。
（3）便于复习和掌握每章的重点，每章的起始处都给出了要点，并在每章结尾处给出了小结。
2、教材内容：
本书共分为8章。第一章叙述数据、数据结构、算法等基本概念。第2~6章分别讨论了线性表、栈和队列、串和数组、树和二叉树、图等的基本数据结构及其应用。第7章和第8章分别讨论了查找和排序的各种实现方法及其应用。因为此教材与我们通用的蔚学敏老师的《数据结构》（清华大学版）内容有一定的区别，所以在教材处理上参考了其他《数据结构》教材，对本教材进行了补充。我说课的内容是第五章第一节。在《数据结构》中，树这一章既是这门课程的难点也是该课程的重点。第一节的内容是对第五章内容的基础，对于第五章内容的学习有很重要的意义。
3、文献资料清单：
扩大学生的知识面并培养学生的自学能力，为学生的研究性学习和自主学习的开展提供下列文献资料清单：
《数据结构》（C语言版），严蔚敏，吴伟民，清华大学出版社。
《数据结构习题集》（C语言版），严蔚敏，清华大学出版社。
《数据结构》，陈雁，高等教育出版社。
三、学情分析
本人所教的学生属计算机类专业，08级计算机班共有学生46人，年龄在18-21岁之间，他们正处于自我表现意识和协作学习的愿望最强时期。拥有较多的业余时间，可利用的课外资源也比较丰富；同时拥有较强的自我意识和自我管理能力，学习目标和职业目标也比较明确，有充分的自主学习条件。
但从他们自身的理论基础而言，他们先行课的掌握不足。C语言程序设计是《数据结构》的前导课程之一。学生对它的熟悉、掌握程度，直接关系到数据结构课程的教学效果。由于C语言是学生最先接触的程序设计语言，编程思想与以往的思维方式不同，教学难度比较大，使得教学时间大部分花费在基本概念上。而学生对数组、结构体、指针这三种数据类型的认识和理解不深，甚至印象模糊，对函数、函数的参数、函数的返回值、函数调用的理解也不够，对递归及递归过程更是难以理解。但是，这些内容是数据结构课程的重要基础，在数据结构课程中使用频率很高。而且数据结构这门课理论性很强，比较抽象，学生掌握起来比较困难，因此我在教学中穿插补充了了C语言中的数组、结构体、指针，在教学过程中更是多以多种形式生动具体的讲述理论知识。
四、教学目标
对学生在知识、素质及能力方面的目标如下：
1、知识目标
（1）掌握树的各种术语，如根、叶子、父结点、兄弟、祖先、子孙等；
（2）掌握双亲表示法、孩子表示法、孩子兄弟表示法；
（3）掌握二叉树的定义、性质及应用。
2、素质目标
（1）工作方法：遇到问题能进行全面分析、解决；
（2）合作精神：能够与他人进行合作，具有协调工作能力和组织管理能力。
3、能力与技能要求
（1）提高学生的认知能力；
（2）培养学生自主学习和团结协作的能力；
（3）阅读基本算法程序；
（4）能进行算法评价。
五、教学重点与难点
1、重点
（1）树的各种术语，如根、叶子、父结点、兄弟、祖先、子孙等；
（2）掌握双亲表示法、孩子表示法、孩子兄弟表示法；
（3）掌握二叉树的定义、性质及应用。
2、落实方法：通过各种教学方法使抽象的概念、算法具体化。
3、难点
（1）二叉树的性质及应用；
4、突破方法：通过启发法、归纳总结等方法对二叉树的性质逐步分析、最终得到二叉树的性质。
六、教学方法
准确的目标为教学活动指明了方向，好的教学方法则为教学活动顺利进行提供了保障。
在计算机教学中努力倡导“以学生为中心，以培养学生应用能力为重点”的教学思想，多种教学方法相结合，鼓励并允许学生充分参与课堂教学活动，从真正意义上实现师生互动，教学相长的良好教学关系。从激发学生兴趣入手，在课堂教学中灵活运用多种形式来展示教学内容。
本门课程理论性较强、抽象，理解起来比较困难。因此我用的教学方法多是为引起学生兴趣，激发学生积极性，使学生的思维从抽象到具体再由具体到抽象便于学生理解的方法，如启发式教学、案例法教学、画图法教学、任务驱动式教学、讨论法教学，传统教学手段与多媒体教学相结合等。
1、启发式教学
对于数据结构中的某些内容，特别是一些抽象的概念、算法，应尽可能地先从直观意义或直观解释入手，引出实例，进而分析讨论。比如介绍栈和队列以及树这些抽象的概念的时候，先列举现实生活中的一些例子，这些例子都与这些概念有着密切的关系，这样学生就很容易接受并记住这些概念。通过这样一个从特殊到一般，从具体到抽象的逐步启发过程之后，往往能够达到很好的效果。
2、示例法
本门课程理论性很强，比较抽象难以理解，对于抽象理论知识的学习学生往往会觉得空洞而枯燥，为了使教学更有针对性，我们常常结合一些具体例题。利用示例的方式，把教学内容与这些内容有机地结合起来。使学生在学习本课程的过程中，对理论知识的应用、科学研究方法与手段、本学科的前沿研究成果有所了解和掌握。
3、画图法
本课程的很多算法是通过图示来解释其过程，如果要理解算法可以把算法的每一步画成图。特别是线性表、栈和队列、树、图这些存储结构一定要多画图，以图加强理解。
4、开展讨论，培养能力
《数据结构》中基本概念、算法较多, 彼此间具有连贯性，一味单纯地讲授教学，学生往往是被动地接受知识，枯燥乏味，往往难以激发学习兴趣。因此，在课堂教学中，让学生参与教学过程，调动学生的主动性，引导学生发现问题和分析问题，让他们能够自由地、充分地、广泛地进行课堂讨论，从而达到解决问题的目的。比如，针对课程中的主要问题或疑难问题让学生们展开讨论。首先，在进行课堂讨论之前，应该确定讨论题目并提出具体要求指导学生搜集有关资料。其次，在讨论时，要鼓励他们进行独立思考，各抒己见，引导他们逐步深入地对问题进行实质性的分析。我主要控制讨论的进程，合理分配讨论的时间，并进行及时的总结，从而指导学生进一步思考。实践证明，课堂讨论可以加深学生对理论知识的理解和记忆，有助于学生养成独立思考问题、相互交流意见的习惯，从而提高他们分析和解决问题的能力。
5、传统教学手段与多媒体技术相结合
多媒体技术以其多样生动的形式在计算机教学中为师生创造了一个丰富多彩的互动交际平台。作为一种新型的教学手段，多媒体教学有助于在计算机教学中帮助学生理解抽象的内容和算法。
《数据结构》中的线性表、栈等对于初学者而言，指针的操作、储存方式过于抽象；递归算法概念在生活经验中缺乏可供模拟的例子，教材在呈现数据结构概念时经常由于受到篇幅的限制，常省略算法部分细节过程，而让学生自己发挥想象力去补足；虽然，有时也会使用黑板及投影片，通过图解或举例的方式来帮助学生。但在问题或概念越复杂时，便越难以图解或举例说明。为了解决学生学习抽象概念的困扰，借助多媒体教学。利用多媒体技术教学，除了可以运用Flash 动画软件演示算法运行过程外，还可以将课前预习内容，课后复习内容用简短的语句以课件的形式表现出来，加深学生印象，督促学生认真完成任务。另外，还可以给学生播放一些成熟的优秀的视频教学软件，可以启发学生从不同老师的认识和解决
问题的角度去加深理解所学内容。
6、加强实践环节，实施教学方法多样化：由于<数据结构)中稍微复杂一些的算法设计常常涉及到多种技术和方法。同时，隐含于教材中各种算法的设计技巧丰富、形式多样。因而学生在学习过程中常常觉得教科书中的内容与具体的算法设计题相距甚远，无从下手。要使学生真正学好、学懂数据结构。除了在课堂上要采用行之有效的教学方法外，诸如案例法、讨论法等。还应加强实践环节。可以通过三种实践方式：一是做习题。二是上机实践。三是课程设计。习题主要限于章节的内容。使学生加深对各章节主要的理论、概念、方法、结构等的理解。由于专业课程的理论与技术往往表现出较强的综合性、前沿性、探索性。是发展中的科学。通过课程设计让学生撰写自己的小论文或总结报告，使学生时刻跟踪本课程的最新动态。上机实践则不仅能进一步提高学生灵活运用《数据结构》的能力，而且使学生在编程、上机操作、程序调试与正确性验证等基本技能方面受到严格的训练。
七、教学过程
这节课把整个教学过程安排如下六个教学段：
（一）精心设计，复习检查。
（二）创设情境，导入新课。
（三）运用各种教学方法，讲授新课，并对重、难点逐个突破。
（四）讨论归纳，突出重点、难点。
（五）布置作业，延伸到下节课内容。
通过多种摸式教学，充分调动学生学习的积极性和主动性，突出学生的主体作用，并能培养发现问题、解决问题的能力和学生互助合作精神，最终达到我们预定的目标。
第一教学段，精心设计，复习检查。(3分钟)
（1）栈和队列的定义、特性；
（2）栈和队列空、满时的判定。
第二教学段，创设情景，导入新课。（5分钟）
通常我们会用开枝散叶也就是树来形容人类的繁衍生息，所以我从人类的族谱说起，以我们人类的族谱来说明树的基本概念及其术语。例如祖先、双亲、孩子、兄弟等等。这里主要是激发学生学习这章内容的兴趣，促进学习的主动性和积极性，便于下面内容的学习。
第三教学段，运用各种教学方法，讲授新课，并对重、难点逐个突破。（25分钟）
在这一教学段，我分为三个阶段来完成新课的教授，这三个阶段是：
第一个阶段：实例法讲树的三种存储结构——双亲表示法、孩子表示法、孩子兄弟表示法。
这个部分主要用的是实例法，以实例来解释算法及其步骤，掌握他们的示意图及其应用。
第二个阶段：以启发法引出二叉树，满二叉树，完全二叉树的定义。
这个部分我从我国的计划生育政策说起，一对夫妻最多拥有两个孩子，以树来说，也就是我们要讲的二叉树。并由此引出满二叉树、完全二叉树的定义。 第三个阶段：讲二叉树的性质及应用。
一共有三个性质：首先抛出下面这几个问题，让学生们思考：
1、在二叉树的第i 层上最多有多少个结点？
2、深度为K 的二叉树最多有多少个结点（K ≥1）？
3、对于任意一棵二叉树BT ，如果度为0的结点个数为0n ，度为2的结点个数为2n ，则0n 和2n 的关系是什么？
然后，启发他们画出图形来观察一下二叉树存在什么规律。
最后，画出一棵简单的二叉树，并对其结点规律进行总结归纳，并扩展第三个性质，由二叉树展开到一般树得出结论。
以实例来说明二叉树的性质。
第四教学段，讨论归纳，突出重点、难点。（7分钟）
对本节课内容归纳总结，突出重、难点。然后让学生自己讨论这节课所学，听取学生的意见和对重难点的掌握情况，根据他们的意见，对于他们还有疑惑的地方再着重讲述。
第五教学段，布置作业，延伸到下节课内容。（2分钟）
在这一教学段，
布置作业1：
作业2 ：
下节课内容提示：1、访问所有结点的这个过程叫什么？
2、一共有几种方法可以访问到所有结点？怎样访问？
板书设计
一、树的定义与术语
1、树的定义
2、祖先、孩子、双亲、子孙、兄弟、堂兄弟
3、结点：终端结点（叶子）
非终端结点
4、结点的度
5、结点的层次
6、树的度
7、树的深度
8、有序树、无序树
9、森林
二、树的存储结构
1. 双亲表示法
2. 孩子表示法
3. 孩子兄弟表示法
三、二叉树的定义
定义：二叉树是另一种树形结构。它与树形结构的区别是：
（1）每个结点最多有两棵子树；
（2）子树有左右之分。
二叉树也可以用递归的形式定义。即：二叉树是n （n≥0 ）个结点的有限集合。当n=0 时，称为空二叉树；当n>0 时，有且仅有一个结点为二叉树的根，其余结点被分成两
个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。四、二叉树的性质
性质1：在二叉树的第i 层上最多有2i-1个结点（i≥1 ）。
性质2：深度为K的二叉树最多有2K-1个结点（K≥1）。
性质3：对于任意一棵二叉树BT，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。
八、教学效果预测及教学后记
教学效果预测：本节课结合教学大纲对教材和学生进行充分的分析，通过复习检查，创设情景，导入新课，运用各种教学方法，讲授新课，并对重、难点逐个突破，讨论归纳，突出重点、难点，布置作业，延伸到下节课内容的教学过程，让学生达到我们预定的知识、能力、技能、素质目标，这节课的教学效果必定显著。
实验报告 课程名称数据结构 实验项目实验三--创建一个二叉树并输出三种遍历结果 系别■计算机学院 _________________ 专业_______________ 班级/学号_____________ 学生姓名___________ 实验日期— 成绩______________________________ 指导 教师
实验题目：实验三创建一个二叉树并输出三种遍历结果 实验目的 1）掌握二叉树存储结构； 2）掌握并实现二叉树遍历的递归算法和非递归算法; 3）理解树及森林对二叉树的转换; 4）理解二叉树的应用一哈夫曼编码及WPL计算。 实验内容 1）以广义表或遍历序列形式创建一个二叉树，存储结构自选； 2）输出先序、中序、后序遍历序列； 3）二选一应用题：1）树和森林向二叉树转换；2）哈夫曼编码的应用问题。 题目可替换上述前两项实验内容） 设计与编码 1）程序结构基本设计框架 （提示：请根据所选定题目，描述程序的基本框架，可以用流程图、界面描述图、 框图等来表示） 2）本实验用到的理论知识遍历二叉树，递归和非递归的方法 （应用型
(提示：总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，要求结合自己的题目并阐述自己的理解和想法) 3) 具体算法设计 1) 首先，定义二叉树的存储结构为二叉链表存储，每个元素的数 据类型Elemtype,定义一棵二叉树，只需定义其根指针。 2) 然后以递归的先序遍历方法创建二叉树，函数为CreateTree()，在输 入字符时要注意,当节点的左孩子或者右孩子为空的时候,应当输入一 个特殊的字符(本算法为“ #”),表示左孩子或者右孩子为空。 3) 下一步,创建利用递归方法先序遍历二叉树的函数,函数为 PreOrderTreeQ,创建非递归方法中序遍历二叉树的函数，函数为 InOrderTree()，中序遍历过程是：从二叉树的根节点开始，沿左子树 向下搜索，在搜索过程将所遇到的节点进栈；左子树遍历完毕后，从 栈顶退出栈中的节点并访问；然后再用上述过程遍历右子树，依次类 推，指导整棵二叉树全部访问完毕。创建递归方法后序遍历二叉树的 函数，函数为LaOrderTree()。 (提示：该部分主要是利用C、C++ 等完成数据结构定义、设计算法实现各种操作，可以用列表分步形式的自然语言描述，也可以利用流程图等描述) 4) 编码 #include
二叉树遍历方法 1.中序遍历的投影法 如果给定一棵二叉树的图形形态，是否能根据此图快速地得出其中序遍历的序列？回答是肯定的。具体做法是：首先按照二叉树的标准绘制二叉树形态，即将所有左子树都严格绘于根结点的左边；将所有右子树都严格绘于根结点的右边。然后假设现在有一个光源从该二叉树的顶部投射下来，那么所有结点在地平线上一定会有相应的投影，从左至右顺序读出投影结点的数据即为该二叉树的中序遍历序列。如图11.10所示。 图示的中序遍历序列： D J G B H E A F I C 2.先序遍历的填空法 如果给定一棵二叉树的图形形态，可在图形基础上，采用填空法迅速写出该二叉树的先序遍历序列。具体做法是：我们知道，对于每个结点都由三个要素组成，即根结点，左子树、右子树；又已知先序遍历顺序是先访问根结点、然后访问左子树、访问右子树。那么，我们按层分别展开，逐层填空即可得到该二叉树的先序遍历序列。 图11.10 中序遍历投影法示意图 如图11.10 中的二叉树采用填空法的步骤如下： (1)根结点左子树右子树 A( )( ) (2)A （根结点（左子树）（右子树））（根结点（左子树）（右子树）） A B C (3)A(B(根结点（左）（右）)(根结点（左）（右）))（C(……)(……)） A B D 无 G E H 无 C F 无 (4)A B D G J E H C F I 此即为该二叉树的先序遍历序列。 注：后序遍历的序列亦可以此方法类推，请读者自己尝试。
3.利用遍历序列构造二叉树 如果已知一棵二叉树的先序遍历序列和中序遍历序列，则可以用这两个遍历序列构造一棵唯一的二叉树形态。我们知道任意一棵二叉树的先序遍历序列和中序遍历序列是唯一的，那么首先从给定的先序遍历序列入手，该先序序列的第一个元素一定是该二叉树的根；再分析这个根结点在中序遍历序列中的位置，中序遍历序列中根结点的左边即为左子树的全部元素，而根结点的右边即为右子树的全部元素；然后据此再将先序遍历序列除根结点以外的其余部分分为左、右子树两部分，并在这两部分中分别找出左、右子树的根结点。依此类推，即可得到完整的二叉树。例11.1 已知一棵二叉树的先序遍历和中序遍历序列分别为： 先序： A B C I D E F H G 中序： C I B E D A H F G 请构造这棵二叉树。 按前述分析，这棵二叉树的构造过程如图11.11所示 图11.11 二叉树的构造过程 树、森林与二叉树的转换(flash演示) 如前所述，树（或森林）的存储结构及其操作算法的实现，由于其“度”的不确定性而导致其存储结构不是较为复杂就是浪费空间，因而，定义在其存储结构上的算法也相应地较难兼顾全面。如果我们设定一定的规则，用二叉树来表示树和森林的话，就可以方便地解决树、森林的存储结构及其相关算法问题。 1.树、森林转换为二叉树 我们知道，一棵树中每个结点的孩子是无序的，而二叉树中各结点的孩子必须有左右之分。在此，为避免概念混淆，首先约定树中每个结点的孩子按从左至右的顺序升序编号，即将树中同一层上的兄弟分出大小。那么将一棵树转换成二叉树的方法是： （1）在树中同层兄弟间加一连线； （2）对树中每个结点仅保留其与长兄（左边第一个孩子）的连线，擦去其与其它孩子的连线； （3）以树（或子树）的根作为轴心，将所有的水平连线顺时针旋转45度，即可得到与该树完全等价的一棵二叉树。
/*实验三：二叉树遍历操作验证*/ #include
if(T) //若非空 { if(T->data) { //输出 printf("%c",T->data); } preOrderTraverse(T->lchild); preOrderTraverse(T->rchild); } } //递归方法中序遍历二叉树 void inOrderTraverse(BiTree T) { if(T) //若非空 { preOrderTraverse(T->lchild); if(T->data) { //输出 printf("%c",T->data); } preOrderTraverse(T->rchild); } } //递归方法后序遍历二叉树 void postOrderTraverse(BiTree T) { if(T) //若非空 { preOrderTraverse(T->lchild); preOrderTraverse(T->rchild); if(T->data) { //输出 printf("%c",T->data); } } } //层序遍历二叉树 void LevelTraverse(BiTree T) { queue
1.设一棵完全二叉树共有699 个结点，则在该二叉树中的叶子结点数？ 1根据二叉树的第i层至多有2A(i - 1)个结点；深度为k的二叉树至多有2A k - 1 个结点(根结点的深度为1)”这个性质： 因为2A9-1 < 699 < 2A10-1 , 所以这个完全二叉树的深度是10，前9 层是一个满二叉树， 这样的话，前九层的结点就有2A9-1=511 个；而第九层的结点数是2A(9-1)=256 所以第十层的叶子结点数是699-511=188 个；现在来算第九层的叶子结点个数。由于第十层的叶子结点是从第九层延伸的，所以应该去掉第九层中还有子树的结点。因为第十层有188 个，所以应该去掉第九层中的188/2=94 个；所以，第九层的叶子结点个数是256-94=162，加上第十层有188 个，最后结果是350 个 2完全二叉树：若二叉树中最多只有最下面两层的结点的度可以小于2，并且最下面一层的结点 (叶结点) 都依次排列在该层最左边的位置上，这样的二叉树为完全二叉树。 比如图：完全二叉树除叶结点层外的所有结点数(叶结点层以上所有结点数)为奇数，此题中，699 是奇数，叶结点层以上的所有结点数为保证是奇数，则叶结点数必是偶数，这样我们可以立即选出答案为B！如果完全二叉树的叶结点都排满了，则是满二叉树，易得满二叉树的叶结点数是其以上所有层结点数+1 比如图： 此题的其实是一棵满二叉树，我们根据以上性质，699+1=700，700/2=350，即叶结点数为350，叶结点层以上所有结点数为350-1=349。 3完全二叉树中，只存在度为2 的结点和度为0 的结点，而二叉树的性质中有一条是： nO=n2+1 ; nO指度为0的结点，即叶子结点，n2指度为2的结点，所以2n2+1=699 n2=349 ; n0=350 2.在一棵二叉树上第 5 层的结点数最多是多少一棵二叉树，如果每个结点都是是满的，那么会满足2A(k-1)1 。所以第5 层至多有2A(5-1)=16 个结点！ 3.在深度为5 的满二叉树中，叶子结点的个数为答案是16 ~ 叶子结点就是没有后件的结点~ 说白了~ 就是二叉树的最后一层~ 深度为K 的二叉树~ 最多有2Ak-1 个结点~ 最多有2A(k-1) 个结点~ 所以此题~ 最多有2A5-1=31 个结点~ 最多有2A(5-1)=16 个叶子结点~ 4.某二叉树中度为2 的结点有18 个，则该二叉树中有几个叶子结点？结点的度是指树中每个结点具有的子树个数或者说是后继结点数。 题中的度为2 是说具有的2 个子树的结点；二叉树有个性质：二叉树上叶子结点数等于度为2 的结点数加1。 5.在深度为7 的满二叉树中，度为2 的结点个数为多少，就是第一层只有一个节点，他有两个子节点，第二层有两个节点，他们也都有两个子节点以此类推，所以到第6 层，就有2的5次方个节点，他们都有两个子节点最后第7 层都没有子节点了。因为是深度为7 的。 所以就是1+2+4+8+16+32 了 2深度为1的时候有0个 深度为2的时候有1个 深度为3的时候有3个 深度为4的时候有7个 深度为n的时候有（2的n-1次方减1 ）个 6?—棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为？
实验三：二叉树的遍历问题 题目：编制一个遍历二叉树的程序 班级：姓名：学号：完成日期： 一.需求分析 1.问题描述：很多涉及二叉树的操作的算法都是以二叉树的遍历操作为基础的。编写程序，对一棵给定的二叉树进行先、中、后三种次序的遍历。 2.基本要求：以二叉链表为存储结构，实现二叉树的先、中、后三种次序的递归和非递归遍历。 3.测试数据：以教科书图6.9的二叉树为例。 4.实现提示： (1).设二叉树的结点不超过30个，且每个结点的数据均为字符，这样可利用先序遍历序列作为输入顺序创建二叉树链表存储结构。 (2.)也可利用完全二叉树在顺序存储中的特性，创建二叉树的存储结构，此时，二叉树中结点数据的类型不受限制。 二.概要设计 1.为实现上述功能，应先建立二叉树。为此，需要有一个二叉树的抽象数据类型。该抽象数据类型的定义为： ADT BinaryTree { 数据对象D：D是具有相同特性的数据元素的集合 termset中每个元素包含编号，密码，和一个指向下一节点的指针数据关系R： 若D=?，则R=?,称BinaryTree为空二叉树； 若D≠?，则R={H},H是如下二元关系： (1).在R中存在唯一的称为根的数据元素root,它在关系H下无前驱； (2).若D-(root) ≠?, 则存在D-(root)={D1,D2},且D1∩D2=?; (3). D1≠?，则D1中存在唯一的元素x1，
数据结构实验五 课程数据结构实验名称二叉树的建立及遍历第页 专业班级学号 姓名 实验日期:年月日评分 一、实验目的 １．学会实现二叉树结点结构和对二叉树的基本操作。 ２．掌握对二叉树每种操作的具体实现,学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。 二、实验要求 1．认真阅读和掌握和本实验相关的教材内容。 2．编写完整程序完成下面的实验内容并上机运行。 3.整理并上交实验报告。 三、实验内容 1.编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树,采用三种递归遍历算法（前序、中序、后序）对这棵二叉树进行遍历并计算出二叉树的高度。 2 .编写程序生成下面所示的二叉树,并采用先序遍历的非递归算法对此二叉 树进行遍历。 四、实验步骤 （描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的,发生的现象和中间结果) 第一题 #ｉnｃlude "sｔdafx.ｈ" #include＂ｉoｓtｒeam.h" #inclｕde"sｔｄliｂ.h"
＃incｌudｅ"ｓｔdiｏ.ｈ" #include
实验课题一：将下图中得二叉树用二叉链表表示： 1用三种遍历算法遍历该二叉树，给出对应得输出结果; 2写一个函数对二叉树搜索,若给出一个结点，根据其就是否属于该树，输出tｒｕe或者f ａｌse。 3写函数完成习题4、31(Ｃ＋+版)或4、2８（C版教科书）。 #iｎclｕde "stdio、h＂ ＃incluｄe”mallｏc、h" typedｅfｓtruct BｉTＮode ｛ cｈar data; sｔrucｔBiTＮode *lｃｈild,*rｃhiｌd; }ＢiTＮodｅ，*BiTrｅe； BｉＴree Creaｔe（BｉTｒeｅT) ｛ char ch； ch=getchａｒ(）; ｉｆ(ch=='#’） T=NULL; elｓe { T=(BiＴNode *）maｌloc(sｉｚｅｏf（ＢiTNｏｄe)）; Ｔ-〉data=ｃh； Ｔ-＞lｃｈiｌd=Creaｔe(T—〉lchilｄ); T—〉rchild=Creａte(Ｔ－〉rchｉld）； ｝ retuｒn Ｔ； } ｉnt node(BiＴrｅe Ｔ) { int sum1=0，a,b; ?iｆ（T) ｛ if（Ｔ！=ＮUＬL） ??sｕm1++;
?ａ=ｎode（Ｔ->lchiｌd); sｕm1＋=ａ； b=node(T—>rchｉld)； sum1+=b; ?} ｒetｕrn sum1； } int mｎode（BiTree T） { ?int sum２=0,ｅ，ｆ； if（T) { ?ｉf（（T->lcｈiｌd!=NULL）&＆(T－〉rchild!=NULL）)?sum2++； ?e=ｍnoｄｅ（Ｔ－〉lchild); suｍ2＋=e; f＝mnoｄｅ（T－〉rchｉｌd)； sum２+=f； ?｝ retｕrn sum2; ｝ void Preorｄer（BiTree T) { ｉf(Ｔ） { pｒintf（＂%c”，T－>daｔa)； Ｐreoｒder(Ｔ—>lchiｌｄ）； Ｐreorder（T－〉rchｉld）； ｝ } iｎt Sumｌeaｆ（BiTｒｅe T) { int suｍ=0,m，n; if（T） { if((！T-〉lchild）&&（!T-〉rｃhiｌd)) sum++； m=Ｓuｍleaf（T－>lchｉld)； suｍ+=m； n=Sumleaf(T—＞rｃhｉｌd); suｍ+＝ｎ； ｝ retuｒn ｓum； }
习题六树和二叉树 一、单项选择题 1．以下说法错误的是（） A. 树形结构的特点是一个结点可以有多个直接前趋 B. 线性结构中的一个结点至多只有一个直接后继 C. 树形结构可以表达（组织）更复杂的数据 D. 树（及一切树形结构）是一种”分支层次”结构 E. 任何只含一个结点的集合是一棵树 2. 下列说法中正确的是（） A. 任何一棵二叉树中至少有一个结点的度为2 B. 任何一棵二叉树中每个结点的度都为2 C. 任何一棵二叉树中的度肯定等于2 D. 任何一棵二叉树中的度可以小于2 3. 讨论树、森林和二叉树的关系，目的是为了（） A. 借助二叉树上的运算方法去实现对树的一些运算 B. 将树、森林按二叉树的存储方式进行存储 C. 将树、森林转换成二叉树 D. 体现一种技巧，没有什么实际意义4．树最适合用来表示（） A. 有序数据元素 B .无序数据元素 C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B ．11 C ．15 D ．不确定 6. 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1, M2和M3与森林F 对应的二叉树根结点的右子树上的结点个数是（）。 A．M1 B ．M1+M2 C ．M3 D ．M2+M3 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（） A．250 B ．500 C ．254 D ．505 E ．以上答案都不对 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为（） A. 不确定 B . 2n C . 2n+1 D . 2n-1 9．二叉树的第I 层上最多含有结点数为（） I I-1 I-1 I A．2I B ．2 I-1 -1 C ．2 I-1 D ．2 I -1 10．一棵二叉树高度为h, 所有结点的度或为0，或为2，则这棵二叉树最少有（）结点A．2h B ．2h-1 C ．2h+1 D ．h+1 11. 利用二叉链表存储树，则根结点的右指针是（）。 A.指向最左孩子 B .指向最右孩子 C .空D .非空 12．已知一棵二叉树的前序遍历结果为为（）。 A．CBEFDA B ．FEDCBA 13．已知某二叉树的后序遍历序列是（）。 ABCDEF中序遍历结果 为 C ．CBEDFA D dabec, 中序遍历序列是 CBAEDF则后序遍历的结 果 ．不定 debac , 它的前序遍历是
#include "stdio.h" #include "stdlib.h" #define STACK_INIT_SIZE 100 //栈存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 //------二叉树的存储结构表示------// typedef struct BiTNode{ int data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //-----顺序栈的存储结构表示------// typedef struct{ BiTree *top; BiTree *base; int stacksize; }SqStack; //*************************************************** //构造一个空栈s SqStack *InitStack(); //创建一颗二叉树 BiTree CreatBiTree(); //判断栈空 int StackEmpty(SqStack *S); //插入元素e为新的栈顶元素 void Push(SqStack *S,BiTree p); //若栈不为空，则删除s栈顶的元素e，将e插入到链表L中void Pop(SqStack *S,BiTree *q); //非递归先序遍历二叉树 void PreOrderTraverse(BiTree L); //非递归中序遍历二叉树 void InOrderTraverse(BiTree L); //非递归后序遍历二叉树 void PostOrderTraverse(BiTree L); //递归后序遍历二叉树 void PostOrder(BiTree bt); //递归中序遍历二叉树 void InOrder(BiTree bt); //递归先序遍历二叉树 void PreOrder(BiTree bt); //***************************************************
竭诚为您提供优质文档/双击可除二叉树的建立和遍历的实验报告 篇一：二叉树遍历实验报告 数据结构实验报告 报告题目：二叉树的基本操作学生班级： 学生姓名：学号： 一．实验目的 1、基本要求：深刻理解二叉树性质和各种存储结构的特点及适用范围；掌握用指针类型描述、访问和处理二叉树的运算；熟练掌握二叉树的遍历算法；。 2、较高要求:在遍历算法的基础上设计二叉树更复杂操作算法；认识哈夫曼树、哈夫曼编码的作用和意义;掌握树与森林的存储与便利。二.实验学时： 课内实验学时：3学时课外实验学时：6学时三．实验题目 1．以二叉链表为存储结构，实现二叉树的创建、遍历（实验类型：验证型）1）问题描述：在主程序中设计一个简单的菜单，分别调用相应的函数功能：1…建立树2…前序
遍历树3…中序遍历树4…后序遍历树5…求二叉树的高度6…求二叉树的叶子节点7…非递归中序遍历树0…结束2）实验要求：在程序中定义下述函数，并实现要求的函数功能：createbinTree(binTree structnode*lchild,*rchild; }binTnode;元素类型： intcreatebinTree(binTree voidpreorder(binTreevoidInorder(binTree voidpostorder(binTreevoidInordern(binTreeintleaf(bi nTree intpostTreeDepth(binTree 2、编写算法实现二叉树的非递归中序遍历和求二叉树高度。1）问题描述：实现二叉树的非递归中序遍历和求二叉树高度2）实验要求：以二叉链表作为存储结构 3)实现过程： 1、实现非递归中序遍历代码： voidcbiTree::Inordern(binTreeinttop=0;p=T;do{ while(p!=nuLL){ stack[top]=p;;top=top+1;p=p->lchild;}; if(top>0){ top=top-1;p=stack[top];
5.1树的概念 树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树 1.树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。 2.树的深度——组成该树各结点的最大层次，如上图，其深度为4； 3.森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林； 4.有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。 5.树的表示 树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如上图可写成如下形式： (A(B(E(K,L),F),C(G),D(H(M),I,J))) 5. 2 二叉树 1.二叉树的基本形态： 二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态： (1)空二叉树——(a)； (2)只有一个根结点的二叉树——(b)； (3)右子树为空的二叉树——(c)； (4)左子树为空的二叉树——(d)； (5)完全二叉树——(e) 注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。 2.两个重要的概念： (1)完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树； (2)满二叉树——除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树,。 如下图： 完全二叉树 1页
实验二二叉树的存储结构及各种运算的实现第一题： #include "stdio.h" #include "malloc.h" #define maxsize 66 typedef int datatype; typedef struct node { datatype data ; struct node *lchild,*rchild; } bitree; bitree *Q[maxsize]; bitree *creatree() { char ch; int front,rear; bitree *root,*s; root=NULL; front=1;rear=0; ch=getchar(); while (ch!='#') { s=NULL; if(ch!='@') { s=malloc(sizeof(bitree)); s->data=ch; s->lchild=NULL; s->rchild=NULL; } rear++; Q[rear]=s; if(rear==1) root=s; else { if (s&&Q[front]) if(rear%2==0) Q[front]->lchild=s; else Q[front]->rchild=s; if(rear%2==1)
front++; } ch=getchar(); } return root; } preorder(bitree *t) //前{ if (t) { printf(" %c ",t->data); preorder(t->lchild); preorder(t->rchild); } } inorder(bitree *t) //中{ if (t) { inorder(t->lchild); printf(" %c ",t->data); inorder(t->rchild); } } postorder(bitree *t) //后{ if (t) { postorder(t->lchild); postorder(t->rchild); printf(" %c ",t->data); } } int height(bitree *t) //高度{ int hl,hr; if(!t) return 0; else { hl=height(t->lchild); hr=height(t->rchild); return ((hl>hr?hl:hr)+1); } }
1.设一棵完全二叉树共有699个结点,则在该二叉树中的叶子结点数？ 1根据“二叉树的第i层至多有2^(i ? 1)个结点;深度为k的二叉树至多有2^k ? 1个结点(根结点的深度为1)”这个性质: 因为2^9-1 < 699 < 2^10-1 ,所以这个完全二叉树的深度就是10,前9层就是一个满二叉树, 这样的话,前九层的结点就有2^9-1=511个;而第九层的结点数就是2^(9-1)=256 所以第十层的叶子结点数就是699-511=188个; 现在来算第九层的叶子结点个数。 由于第十层的叶子结点就是从第九层延伸的,所以应该去掉第九层中还有子树的结点。因为第十层有188个,所以应该去掉第九层中的188/2=94个; 所以,第九层的叶子结点个数就是256-94=162,加上第十层有188个,最后结果就是350个 2完全二叉树:若二叉树中最多只有最下面两层的结点的度可以小于2,并且最下面一层的结点(叶结点)都依次排列在该层最左边的位置上,这样的二叉树为完全二叉树。 比如图: 完全二叉树除叶结点层外的所有结点数(叶结点层以上所有结点数)为奇数,此题中,699就是奇数,叶结点层以上的所有结点数为保证就是奇数,则叶结点数必就是偶数,这样我们可以立即选出答案为B！ 如果完全二叉树的叶结点都排满了,则就是满二叉树,易得满二叉树的叶结点数就是其以上所有层结点数+1比如图: 此题的其实就是一棵满二叉树,我们根据以上性质,699+1=700,700/2=350,即叶结点数为350,叶结点层以上所有结点数为350-1=349。 3完全二叉树中,只存在度为2的结点与度为0的结点,而二叉树的性质中有一条就是:n0=n2+1;n0指度为0的结点,即叶子结点,n2指度为2的结点,所以2n2+1=699 n2=349;n0=350 2.在一棵二叉树上第5层的结点数最多就是多少 一棵二叉树,如果每个结点都就是就是满的,那么会满足2^(k-1)1。 所以第5层至多有2^(5-1)=16个结点！ 3、在深度为5的满二叉树中,叶子结点的个数为 答案就是16 ~ 叶子结点就就是没有后件的结点~ 说白了~ 就就是二叉树的最后一层~ 深度为K的二叉树~ 最多有2^k-1个结点~ 最多有2^(k-1)个结点~ 所以此题~ 最多有2^5-1=31个结点~ 最多有2^(5-1)=16个叶子结点~ 4、某二叉树中度为2的结点有18个,则该二叉树中有几个叶子结点？ 结点的度就是指树中每个结点具有的子树个数或者说就是后继结点数。 题中的度为2就是说具有的2个子树的结点; 二叉树有个性质:二叉树上叶子结点数等于度为2的结点数加1。 5、在深度为7的满二叉树中,度为2的结点个数为多少, 就就是第一层只有一个节点,她有两个子节点,第二层有两个节点,她们也都有两个子节点以此类推,所以到第6层,就有2的5次方个节点,她们都有两个子节点 最后第7层都没有子节点了。因为就是深度为7的。 所以就就是1+2+4+8+16+32了
二叉树遍历算法的实现 题目：编制二叉树遍历算法的实现的程序 一．需求分析 1.本演示程序中，二叉树的数据元素定义为非负的整型（unsigned int）数据，输 入-1表示该处没有节点 2.本演示程序输入二叉树数据均是按先序顺序依次输入 3.演示程序以用户和计算机对话方式执行，即在计算机终端上显示“提示信息” 之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和运 算结果显示在其后 4.本实验一共包括三个主要程序，分别是：1）二叉树前序，中序，后序遍历递归 算法实现2）二叉树前序中序遍历非递归算法实现3)二叉树层次遍历算法实现 5.本程序执行命令包括：1）构建二叉树2）二叉树前序递归遍历3）二叉树中序 递归遍历4）二叉树后序递归遍历5）二叉树前序非递归遍历6）二叉树中序非 递归遍历7）二叉树层次遍历 6.测试数据 （1）7 8 -1 9 10 -1 -1 -1 6 11 -1 -1 12 13 -1 -1 14 -1 -1 （2）1 -1 -1 （3）7 8 -1 -1 9 -1 -1 二．概要设计 1.为实现二叉树的遍历算法，我们首先给出如下抽象数据类型 1）二叉树的抽象数据类型 ADT BiTree{ 数据对象D:D是具有相同特性的数据元素的集合 数据关系R： 若D=Φ，则R=Φ，称BiTree是空二叉树； 若D≠Φ，则R={H}，H是如下二元关系： (1)在D中存在唯一的成为根的数据元素root，它在关系H下无前驱； (2)若D-{H}≠Φ，则存在D-{root}={D1,D r}，且D1∩D r=Φ (3)若D1≠Φ，则D1中存在唯一的元素x1，
树和二叉树 树与二叉树是本书的重点内容之一，知识点多且比较零碎。其中二叉树又是本章的重点。 在本章中我们要了解树的定义、熟悉树的存储结构、遍历；二叉树的定义、性质、存储结构、遍历以及树、森林、二叉树的转换。哈夫曼树及哈夫曼编码等内容。 算法的重点是二叉树的遍历及其应用。 6.1 树的定义 一、树的定义 树：树是n(n>0)个结点的有限集合T。一棵树满足下列条件： （1）有且仅有一个称为根的结点； （2）其余结点可分为m(m>=0)棵互不相交的有限集合T1,T2,T3,…Tm， 其中每个集合又是一棵树，并称之为根的子树。 有关树的一些基本概念： 1）结点的度：树中每个结点具有的子树数目或后继结点数。 如图中结点A的度为2，B的度为3 2) 树的度：所有结点的度的最大值为树的度。 （图中树的度为3） 3) 分支结点：即：树中所有度大于0的结点。 4) 叶子结点：即：树中度为零的结点，也称为终端结点。 5) 孩子结点：一个结点的后续结点称为该结点的孩子结点。 6) 双亲结点：一个结点为其后继结点的双亲结点。 7) 子孙结点：一个结点的所有子树中的结点为该结点的子孙结点。 8) 祖先结点：从根结点到一个结点的路径上所有结点（除自己外） 称为该结点的祖先结点。（如Ａ和Ｂ为Ｄ结点的祖先结点） 9) 兄弟结点：具有同一父亲的结点互相为兄弟结点。（如Ｂ和Ｃ为兄弟结点） 10) 结点的层数：从根结点到该结点的路径上的结点总数称为该结点的层数（包括该结点）。 11) 树的深度（高度）：树中结点的最大层数为树的深度。（图中树的深度为4） 12) 森林：0个或多个互不相交的树的集合。 上图中：树的度为3，树的深度为4。 结点A，B，C，D，E，F，G，H，I，J的度分别为：2, 3, 2, 0 ,2 , 0, 0, 0, 0, 0 叶结点有：D, F, G, H, I, J B,C为兄弟，D, E, F为兄弟，F, G为兄弟。I，J为兄弟。 二、树的表示 1. 树的逻辑结构描述 Tree=（D，R） 其中：D为具有相同性质的数据元素的集合。 R为D上元素之间的关系集合。 如上图中的树： D=（A，B，C，D，E，F，G，H，I，J） R={
1.设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数？ 1根据“二叉树的第i层至多有2^(i ? 1)个结点；深度为k的二叉树至多有2^k ? 1个结点（根结点的深度为1）”这个性质： 因为2^9-1 < 699 < 2^10-1 ,所以这个完全二叉树的深度是10，前9层是一个满二叉树， 这样的话，前九层的结点就有2^9-1=511个；而第九层的结点数是2^(9-1)=256 所以第十层的叶子结点数是699-511=188个； 现在来算第九层的叶子结点个数。 由于第十层的叶子结点是从第九层延伸的，所以应该去掉第九层中还有子树的结点。因为第十层有188个，所以应该去掉第九层中的188/2=94个； 所以，第九层的叶子结点个数是256-94=162，加上第十层有188个，最后结果是350个 2完全二叉树：若二叉树中最多只有最下面两层的结点的度可以小于2，并且最下面一层的结点（叶结点）都依次排列在该层最左边的位置上，这样的二叉树为完全二叉树。 比如图： 完全二叉树除叶结点层外的所有结点数（叶结点层以上所有结点数）为奇数，此题中，699是奇数，叶结点层以上的所有结点数为保证是奇数，则叶结点数必是偶数，这样我们可以立即选出答案为B！ 如果完全二叉树的叶结点都排满了，则是满二叉树，易得满二叉树的叶结点数是其以上所有层结点数+1比如图： 此题的其实是一棵满二叉树，我们根据以上性质，699+1=700，700/2=350，即叶结点数为350，叶结点层以上所有结点数为350-1=349。 3完全二叉树中，只存在度为2的结点和度为0的结点，而二叉树的性质中有一条是：n0=n2+1；n0指度为0的结点，即叶子结点，n2指度为2的结点，所以2n2+1=699 n2=349；n0=350 2.在一棵二叉树上第5层的结点数最多是多少 一棵二叉树，如果每个结点都是是满的，那么会满足2^(k-1)1。 所以第5层至多有2^(5-1)=16个结点！ 3.在深度为5的满二叉树中，叶子结点的个数为 答案是16 ~ 叶子结点就是没有后件的结点~ 说白了~ 就是二叉树的最后一层~ 深度为K的二叉树~ 最多有2^k-1个结点~ 最多有2^(k-1)个结点~ 所以此题~ 最多有2^5-1=31个结点~ 最多有2^(5-1)=16个叶子结点~ 4.某二叉树中度为2的结点有18个，则该二叉树中有几个叶子结点？ 结点的度是指树中每个结点具有的子树个数或者说是后继结点数。 题中的度为2是说具有的2个子树的结点； 二叉树有个性质：二叉树上叶子结点数等于度为2的结点数加1。 5.在深度为7的满二叉树中，度为2的结点个数为多少， 就是第一层只有一个节点，他有两个子节点，第二层有两个节点，他们也都有两个子节点以此类推，所以到第6层，就有2的5次方个节点，他们都有两个子节点
二叉树三种遍历算法的源码 二叉树三种遍历算法的源码背诵版 本文给出二叉树先序、中序、后序三种遍历的非递归算法，此三个算法可视为标准算法，直接用于考研答题。 1.先序遍历非递归算法 #define maxsize 100 typedef struct { Bitree Elem[maxsize]; int top; }SqStack; void PreOrderUnrec(Bitree t) { SqStack s; StackInit(s); p=t; while (p!=null || !StackEmpty(s)) { while (p!=null) //遍历左子树 { visite(p->data); push(s,p); p=p->lchild; }//endwhile if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历 { p=pop(s); p=p->rchild; }//endif }//endwhile }//PreOrderUnrec 2.中序遍历非递归算法 #define maxsize 100 typedef struct { Bitree Elem[maxsize];
int top; }SqStack; void InOrderUnrec(Bitree t) { SqStack s; StackInit(s); p=t; while (p!=null || !StackEmpty(s)) { while (p!=null) //遍历左子树 { push(s,p); p=p->lchild; }//endwhile if (!StackEmpty(s)) { p=pop(s); visite(p->data); //访问根结点 p=p->rchild; //通过下一次循环实现右子树遍历}//endif }//endwhile }//InOrderUnrec 3.后序遍历非递归算法 #define maxsize 100 typedef enum{L,R} tagtype; typedef struct { Bitree ptr; tagtype tag; }stacknode; typedef struct { stacknode Elem[maxsize]; int top; }SqStack; void PostOrderUnrec(Bitree t)