第五章树和二叉树.pptVIP

* * 通过上述三种不同的遍历方式得到三种不同的线性序列，它们的共同的特点是有且仅有一个开始结点和一个终端结点，其余各结点都有且仅有一个前驱结点和一个后继结点。 从二叉树的遍历定义可知，三种遍历算法的不同之处仅在于访问根结点和遍历左右子树的先后关系。如果在算法中隐去和递归无关的语句printf()，则三种遍历算法是完全相同的。遍历二叉树的算法中的基本操作是访问结点，显然，不论按那种方式进行遍历，对含n个结点的二叉树，其时间复杂度均为O(n)。所含辅助空间为遍历过程中占的最大容量，即树的深度。最坏的情况下为n，则空间复杂度也为O(n)。 * * 3．二叉链表的构造 (1) 基本思想 利用遍历可以实现对结点的一些操作，如求结点的双亲，求结点的孩子等。还可以在遍历过程中生成结点，建立二叉树的存储结构。前面介绍过用栈建立二叉树，此处介绍一种基于先序遍历的二叉树构造方式，即以二叉树的先序序列为输入构造二叉链表。先序序列中必须加入虚结点以示空指针的位置。 (2) 构造算法（举例说明） * * 【例5-4】建立图5-8 (a)所示二叉树，其输入的先序序列是：ABD∮G∮∮CE∮∮F∮∮。 【解】假设虚结点输入时以空格字符表示，相应的构造算法为： void CreateBinTree (BTree **T) { //构造二叉链表。T是指向根指针的指针，故修改*T就修改了实参(根指针)本身 ? char ch; ? if((ch=getchar())==‘ ‘) *T=NULL; //读入空格，将相应指针置空 ??else //读入非空格 ??{ *T=(BTree *)malloc(sizeof(BTree)); //生成结点 ??? (*T)-data=ch； ??? CreateBinTree((*T)-lchild)； //构造左子树 ?? ? CreateBinTree((*T)-rchild)； //构造右子树 ???} } 调用该算法时，应将待建立的二叉链表的根指针的地址作为实参。 阶段总结 二叉树的性质有哪些 遍历二叉树的三种方式之间的主要不同点 树的遍历除了使用递归方式还可以使用什么方式 本章总结 主要讲解树的逻辑结构和存储结构 讲解二叉树的定义性质和存储结构 重点讲解如何遍历二叉树 树的逻辑结构和存储结构 树和二叉树 二叉树 遍历二叉树 实验1 实验内容 题目：创建一棵二叉树，加入n个节点，对此二叉树进行遍历。 实验目的 熟悉树的存储结构、掌握树的创建、遍历操作。 实验分析 定义树的结构体 创建树，生成新的树节点并插入二叉树中 对树进行遍历，遍历可以考虑使用递归 本章主要介绍了树和二叉树两种数据结构的定义以及它们的存储结构和运算定义。 树是以分支关系定义的层次结构，结构中的数据元素之间存在着“一对多”的关系。树中除根结点没有前驱外，其它每个结点只有一个前驱；所有结点都有零个或多个后继。因此树型结构为自然界和计算机应用中出现的具有层次关系或分支关系的数据，提供了一种自然的表示方法。 如可用树型结构描述人类社会的族谱和各种社会组织机构等。 在计算机学科和应用领域中，树也得到广泛应用。例如在编译程序中，可用树来表示源程序的语法结构等。树还是一种典型的递归结构。 二叉树是另一种树型结构，是度为2的有序树。本章重点讨论了二叉树。二叉树中每个结点至多有两个孩子，它有明确的左、右之分。 一棵深度为h的二叉树，最少含有h个结点，最多含有2h-1个结点；一棵具有n个结点的二叉树，其最小深度为 ?log2n」+1。 二叉树具有顺序和链式两种存储结构。对于完全二叉树通常采用顺序存储结构，对于普通二叉树通常采用链式存储结构。 树和二叉树的遍历算法是实现各种操作的基础。是把非线性结构变成线性结构的一种排列方式。对这种非线性结构的遍历需要选择合适的有哪些信誉好的足球投注网站路径，以确保在这条路径上可以访问到结构中的所有数据元素。它包括先序、中序、后序三种不同的遍历次序（树没有中序遍历）。要求读者能熟练掌握二叉树的前序，中序，后序遍历的递归算法，以及树和二叉树之间，森林和树之间转换的具体方法，熟悉线索二叉树的定义及其线索化算法。 作为应用，最后介绍了最优二叉树和最优前缀编码的构造方法。最优二叉树是一种“带权路径长度WPL”最短的二叉树，最优前缀编码（哈夫曼编码）是最优二叉树的一种应用。 * * 存储结构描述为： #define MaxTreeSize 100 //定义数组空间的大小 ? typedef char DataType； //定义数据类型 ? typedef