根据序列构造二叉树

一、单项选择题1.下面程序段的时间复杂度为( C ) 。

for(int i=0; i<m; i++)for(int j=0; j<n; j++)a[i][j]=i*j;A． O(m2) B． O(n2) C． O(m*n) D． O(m+n) 2.设有一个递归算法如下int fact(int n){串的长度 B.原串的子串 C.串的模式匹配 D.串的连接3.设有一个n×n的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B 中( C )处。

A．(i+3)*i／2 B．(i+1)*i／2 C．(2n-i+1)*i／2 D．(2n-i-1)*i／24.在( C )运算中，使用顺序表比链表好。

5.A．插入B．删除C．根据序号查找 D．根据元素值查找6.带头结点的单链表head为空的判断条件是( C )。

7.A．head= =NULL B．head->next= =NULLC．head->next=head D．head!=NULL8.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（ C ）最节省时间。

A）单链表 B）循环链单表 C）带尾指针的循环链单表 D）带头结点的双循环链表9.栈的插入与删除操作在（A ）进行。

A．栈顶 B．栈底 C．任意位置 D．指定位置10.设一个栈的输入序列为A、B、C、D，则借助一个栈所能得到的输出序列不可能是（ D ）。

11.A．ABCD B．DCBA C．ACDB D．DABC12.在一个链队中，假设F和R分别是队首和队尾指针，则删除一个结点的运算是( C )。

13.A．R=F->next; B．R=R->next; C．F=F->next; D．F=R->next;14.串是一种特殊的线性表，其特殊性体现在( B )。

15.A．可以顺序存储B．数据元素是一个字符16.C．可以链接存储D．数据元素可以是多个字符17.以下说法正确的是（C ）。

已知一棵二叉树的前序序列为bacdeghf,中序序列为cadbhgef,则后序序列为根据二叉树的前序序列bacdeghf和中序序列cadbhgef，可以确定该二叉树的结构。

二叉树是一种特殊的树，它只有左右两个子树，每个节点最多只有两个子节点。

二叉树的前序序列，可以从根节点开始，按照从上到下，从左到右的顺序依次访问每个节点，以根节点b开头的前序序列bacdeghf中，b为根节点，a和c为b的左右子节点，d为a的左子节点，e为a的右子节点，g为c的左子节点，h为c的右子节点。

二叉树的中序序列，可以从左到右依次访问每个节点，从根节点开始，先遍历左子树，再遍历右子树，以根节点b开头的中序序列cadbhgef中，c为b的左子节点，a为c的左子节点，d为a的左子节点，b为d的右子节点，h为b的右子节点，g为h的左子节点，e为g的右子节点。

根据前序序列和中序序列，可以绘制出该二叉树的结构。

其根节点为b，左子节点为c，右子节点为e，c的左子节点为a，a的左子节点为d，d的右子节点为b，e的左子节点为g，g的右子节点为h。

由此可知，该二叉树的后序序列为cdebhgfe，从右向左，从下到上的顺序依次访问每个节点，以根节点b结尾。

由前序序列和中序序列可以直接确定二叉树的结构，而后序序列可以帮助我们更好地理解二叉树的结构。

在许多算法中，后序序列的结构也是非常重要的。

二叉树的前序序列、中序序列和后序序列都是树的一种遍历方式，它们都可以用来确定一棵树的结构，而且这三种遍历方式之间互相转换也是非常方便的。

在计算机科学中，二叉树是一种重要的数据结构，它在图形处理、数据检索等方面有着广泛的应用。

本文综上所述，已知一棵二叉树的前序序列为bacdeghf，中序序列为cadbhgef，根据二叉树的前序序列和中序序列，可以确定该二叉树的结构，其后序序列为cdebhgfe。

二叉树的前序序列、中序序列和后序序列都是树的一种遍历方式，它们都可以用来确定一棵树的结构，而且这三种遍历方式之间互相转换也是非常方便的。

⼆叉树的建⽴⽅法总结之前已经介绍了⼆叉树的四种遍历(如果不熟悉)，下⾯介绍⼀些⼆叉树的建⽴⽅式。

⾸先需要明确的是，由于⼆叉树的定义是递归的，所以⽤递归的思想建⽴⼆叉树是很⾃然的想法。

1. 交互式问答⽅式这种⽅式是最直接的⽅式，就是先询问⽤户根节点是谁，然后每次都询问⽤户某个节点的左孩⼦是谁，右孩⼦是谁。

代码如下(其中字符'#'代表空节点)：#include <cstdio>#include <cstdlib>using namespace std;typedef struct BTNode *Position;typedef Position BTree;struct BTNode{char data;Position lChild, rChild;};BTree CreateBTree(BTree bt, bool isRoot){char ch;if (isRoot)printf("Root: ");fflush(stdin); /* 清空缓存区 */scanf("%c", &ch);fflush(stdin);if (ch != '#'){isRoot = false;bt = new BTNode;bt->data = ch;bt->lChild = NULL;bt->rChild = NULL;printf("%c's left child is: ", bt->data);bt->lChild = CreateBTree(bt->lChild, isRoot);printf("%c's right child is: ", bt->data);bt->rChild = CreateBTree(bt->rChild, isRoot);}return bt;}int main(){BTree bt;bt = CreateBTree(bt, true);LevelOrderTraversal(bt); /* 层序遍历 */return0;}2. 根据先序序列例如输⼊序列ABDH##I##E##CF#J##G##（#表⽰空），则会建⽴如下图所⽰的⼆叉树思路和第⼀种⽅式很相似，只是代码实现细节有⼀点区别，这⾥给出创建函数BTree CreateBTree(){BTree bt = NULL;char ch;scanf("%c", &ch);if (ch != '#'){bt = new BTNode;bt->data = ch;bt->lChild = CreateBTree();bt->rChild = CreateBTree();}return bt;}3. 根据中序序列和后序序列和⽅式⼆不同的是，这⾥的序列不会给出空节点的表⽰，所以如果只给出先序序列，中序序列，后序序列中的⼀种，不能唯⼀确定⼀棵⼆叉树。

一组序列大根堆小根堆的构造步骤大根堆和小根堆都是二叉堆的一种，是一种特殊的完全二叉树结构，其中每个父节点的值都大于或小于其子节点的值。

构造大根堆和小根堆的步骤如下：1.创建一个空的堆。

2.将待构造的序列依次插入堆中。

3.对于大根堆，从最后一个非叶子节点开始，依次进行下沉操作。

对于小根堆，则从第一个非叶子节点开始进行上浮操作。

4.在下沉操作中，比较该节点与其两个子节点的大小关系。

如果父节点的值小于其任意一个子节点的值，则将其与较大的子节点交换位置，并进入该子节点继续进行下沉操作。

5.在上浮操作中，比较该节点与其父节点的大小关系。

如果父节点的值大于该节点的值，则将其与父节点交换位置，并进入父节点继续进行上浮操作。

6.重复步骤4和步骤5，直到节点已到达堆的顶部，或者当前节点的值已符合堆的要求（父节点大于子节点或者父节点小于子节点）。

7.完成上述操作后，序列中的元素已经按照大根堆或小根堆的要求进行了排序。

对于大根堆来说，根节点的元素是序列中的最大值；而对于小根堆来说，根节点的元素是序列中的最小值。

通过这些步骤，我们可以将任意序列转换成大根堆或小根堆，并获取堆顶元素。

这在实际应用中经常被用于解决一些优先级相关的问题，例如优先级队列。

以上便是构造大根堆和小根堆的一般步骤。

值得注意的是，在实际应用中，我们可以通过一些优化手段来提升构造堆的效率。

比如，在插入新元素时，不必每个都进行上浮或下沉操作，可以利用堆的一些特性，减少交换次数，从而提高性能。

同时，在构造堆的过程中，我们也可以选择不同的节点作为起始点，以及不同的方法（如迭代或递归）来进行操作。

这些根据实际情况和需求进行调整和改进，以达到更好的效果。

实验四二叉树的操作班级：计算机1002班姓名：唐自鸿学号：201003010207 完成日期：2010.6.14 题目：对于给定的一二叉树，实现各种约定的遍历。

一、实验目的：（1）掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法；（2）掌握二叉树的遍历算法（先序、中序、后序遍历算法）的思想，并学会遍历算法的递归实现和非递归实现。

二、实验内容：构造二叉树，再实现二叉树的先序、中序、后序遍历，最后统计二叉树的深度。

三、实验步骤：(一) 需求分析1. 二叉树的建立首先要建立一个二叉链表的结构体，包含根节点和左右子树。

因为树的每一个左右子树又是一颗二叉树，所以用递归的方法来建立其左右子树。

二叉树的遍历是一种把二叉树的每一个节点访问并输出的过程，遍历时根结点与左右孩子的输出顺序构成了不同的遍历方法，这个过程需要按照不同的遍历的方法，先输出根结点还是先输出左右孩子，可以用选择语句来实现。

2．程序的执行命令为：1）构造结点类型，然后创建二叉树。

2）根据提示，从键盘输入各个结点。

3）通过选择一种方式（先序、中序或者后序）遍历。

4）输出结果，结束。

(二)概要设计1.二叉树的二叉链表结点存储类型定义typedef struct Node{DataType data;struct Node *LChild;struct Node *RChild;}BitNode,*BitTree;2.建立如下图所示二叉树：void CreatBiTree(BitTree *bt)用扩展先序遍历序列创建二叉树，如果是当前树根置为空，否则申请一个新节点。

3.本程序包含四个模块1) 主程序模块：2)先序遍历模块3)中序遍历模块4)后序遍历模块4.模块调用关系：主程序模块（三）详细设计1.建立二叉树存储类型//==========构造二叉树=======void CreatBiTree(BitTree *bt)//用扩展先序遍历序列创建二叉树，如果是当前树根置为空，否则申请一个新节点//{char ch;ch=getchar();if(ch=='.')*bt=NULL;else{*bt=(BitTree)malloc(sizeof(BitNode));//申请一段关于该节点类型的存储空间(*bt)->data=ch; //生成根结点CreatBiTree(&((*bt)->LChild)); //构造左子树CreatBiTree(&((*bt)->RChild)); //构造右子树}}2. 编程实现以上二叉树的前序、中序和后序遍历操作，输出遍历序列1）先序遍历二叉树的递归算法如下：void PreOrder(BitTree root){if (root!=NULL){Visit(root ->data);PreOrder(root ->LChild); //递归调用核心PreOrder(root ->RChild);}}2）中序遍历二叉树的递归算法如下：void InOrder(BitTree root){if (root!=NULL){InOrder(root ->LChild);Visit(root ->data);InOrder(root ->RChild);}}3）后序遍历二叉树的递归算法如下：void PostOrder(BitTree root){if(root!=NULL){PostOrder(root ->LChild);PostOrder(root ->RChild);Visit(root ->data);}}4）计算二叉树的深度算法如下：int PostTreeDepth(BitTree bt) //求二叉树的深度{int hl,hr,max;if(bt!=NULL){hl=PostTreeDepth(bt->LChild); //求左子树的深度hr=PostTreeDepth(bt->RChild); //求右子树的深度max=hl>hr?hl:hr; //得到左、右子树深度较大者return(max+1); //返回树的深度}else return(0); //如果是空树，则返回0}四、调试分析及测试结果1. 进入演示程序后的显示主界面：请输入二叉树中的元素；先序、中序和后序遍历分别输出结果。

《数据结构与数据库》实验报告实验题目二叉树的基本操作及运算一、需要分析问题描述：实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目，以及二叉树常用运算。

问题分析：二叉树树型结构是一类重要的非线性数据结构，对它的熟练掌握是学习数据结构的基本要求。

由于二叉树的定义本身就是一种递归定义，所以二叉树的一些基本操作也可采用递归调用的方法。

处理本问题，我觉得应该：1、建立二叉树；2、通过递归方法来遍历（先序、中序和后序）二叉树；3、通过队列应用来实现对二叉树的层次遍历；4、借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等；5、运用广义表对二叉树进行广义表形式的打印。

算法规定：输入形式：为了方便操作，规定二叉树的元素类型都为字符型，允许各种字符类型的输入，没有元素的结点以空格输入表示，并且本实验是以先序顺序输入的。

输出形式：通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印，再以广义表形式进行打印。

对二叉树的一些运算结果以整型输出。

程序功能：实现对二叉树的先序、中序和后序遍历，层次遍历。

计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。

对二叉树的某个元素进行查找，对二叉树的某个结点进行删除。

测试数据：输入一：ABC□□DE□G□□F□□□（以□表示空格）,查找5,删除E预测结果：先序遍历ABCDEGF中序遍历CBEGDFA后序遍历CGEFDBA层次遍历ABCDEFG广义表打印A（B（C,D（E（,G）,F）））叶子数3 深度5 宽度2 非空子孙数6 度为2的数目2 度为1的数目2查找5，成功，查找的元素为E删除E后，以广义表形式打印A（B（C,D（,F）））输入二：ABD□□EH□□□CF□G□□□（以□表示空格）,查找10,删除B预测结果：先序遍历ABDEHCFG中序遍历DBHEAGFC后序遍历DHEBGFCA层次遍历ABCDEFHG广义表打印A（B(D,E(H)),C(F(,G))）叶子数3 深度4 宽度3 非空子孙数7 度为2的数目2 度为1的数目3查找10，失败。

树和二叉树知识考点整理●树的基本概念●树的定义●n个结点的有限集●n=0代表空树●满足条件●只有一个根的结点●其余结点是互不相交的有限集，每个集合本身是一棵树，是根的子树●树是一种递归的数据结构●树的根结点没有前驱，其余结点只有一个前驱●树中所有结点可以有零个或多个后驱●基本术语●双亲、兄弟、孩子、祖先●度：孩子个数●分支结点：度大于0●叶子结点：度为0●深度：从下往上；●高度：从上往下；●有序树：从左到右是有次序的●路径和路径长度：路径是从上往下的●森林：m棵互不相交的树的集合。

●树的基本性质●结点数=所有结点度数之和+1●度为m的树中第i层上至多有m的i-1次分个结点●高度为h的m叉树至多有（m^h-1）/（m-1）个结点●具有n个结点的m叉树的最小高度为「logm（n（m-1）+1）]●二叉树的概念●定义●一种树形结构，特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点）并且二叉树的子树有左右之分，次序不可颠倒●二叉树与度为2的有序树区别●度为2的可以有三个结点，二叉树可以是空树●度为2的有序树的孩子左右之分是根据另一个孩子而言的；二叉树无论有没有，都要确定左右●特殊的二叉树●满二叉树●树中每一层都含有最多的结点●完全二叉树●高度为h，有n个结点的二叉树，当且仅当，每个结点都与高度为h的满二叉树中的编号一一对应●二叉排序树●用途：可用于元素的排序、搜索●左子树上所有结点的关键字均小于根结点的关键字；右子树上所有结点的关键字均大于根结点的关键字；左子树和右子树又是一棵二叉排序树●二叉树的性质●非空二叉树上的叶子结点数等于度为2的结点树加1，即n0=n2+1●非空二叉树上第k层至多有2^（k-1）个结点●高度为h的二叉树至多有2^h-1个结点●具有n个结点的完全二叉树的高度为log2（n+1）取顶或者log2n取底+1●二叉树的存储结构●顺序存储结构●只适合存储完全二叉树，数组从0开始●链式存储结构●顺序存储的空间利用率太低●至少三个指针域：数据域、左指针域、右指针域●增加了指向父结点后，变为三叉链表的存储结构●在含有n个结点的二叉链表中，含有n+1个空链域●二叉树的遍历和线索二叉树●二叉树的遍历●先序遍历●根左右●应用：求树的深度●中序遍历●左根右●后序遍历●左右根●应用：求根到某结点的路径、求两个结点的最近公共祖先等●三个遍历时间复杂度都是O(n)●递归算法和非递归算法的转换●层次遍历●需要借助队列●步骤●二叉树根结点入队，然后出队，访问出队结点，若有左子树，左子树根结点入队●遍历右子树，有右子树，右子树根结点入队。

计算机专业基础综合（查找）-试卷1(总分：94.00，做题时间：90分钟)一、单项选择题(总题数：25，分数：50.00)1.单项选择题1-40小题。

下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

__________________________________________________________________________________________ 2.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。

A.(n—1)／2B.n／2C.(n+1)／2 √D.n此题考查的知识点是顺序查找长度ASL的计算。

假设表长度为n，那么查找第i个数据元素需进行n一i+1次比较，即C i =n一i+l。

又假设查找每个数据元素的概率相等，即P i =1／n，则顺序查找算法的平均查找长度为：所以应选C。

3.顺序查找法适用于查找顺序存储或链式存储的线性表二分法查找只适用于查找顺序存储的有序表，平均比较次数为( )。

在此假定N为线性表中结点数，且每次查拔都是成功的。

A.N+1B.2log 2 NC.log 2 N √D.N／2此题考查的知识点是各类查找算法的比较次数计算。

顺序查找法用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败，其ASL=(n+1)／2，即查找成功时的平均比较次数约为表长的一半。

应选C。

4.顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为( )在此假定N为线性表中结点数，且每次查拔都是成功的。

A.N+1B.2log 2 NC.log 2 ND.N／2 √二分法查找过程可用一个称为判定树的二叉树描述，由于判定树的叶子结点所在层次之差最多为1，故n个结点的判定树的深度与n个结点的完全二叉树的深度相等，均为[log 2 n]+1。

这样，折半查找成功时，关键字比较次数最多不超过[log 2 n]+1。