下载文档原格式
数据结构各章概要数据结构是计算机科学中非常重要的一个学科，其主要研究各种数据的组织方式和操作方法。
善于运用合适的数据结构可以提高算法的效率，并优化程序的性能。
本文将对数据结构的各个章节进行概要介绍，帮助读者了解不同章节的主要内容和应用。
第一章：引论在引论章节，我们将引入数据结构的基本概念和术语，例如什么是数据、数据项、数据对象等等。
同时，还将介绍数据结构的分类和基本操作，如搜索、遍历、插入、删除和排序。
这些基础知识是后续章节的基础。
第二章：线性表线性表是数据结构中最简单、最基本的一种结构。
其特点是数据元素之间的前驱和后继关系非常明确。
线性表可以用数组和链表两种方式实现。
在本章节中，我们将分别介绍顺序表和链表的实现原理、插入、删除、合并以及应用场景。
第三章：栈和队列栈和队列是两种特殊的线性表结构，它们对数据的访问具有限制性。
栈具有“先进后出”的特点，而队列则具有“先进先出”的特点。
在本章节中，我们将介绍栈和队列的实现方式以及常见的应用场景，如递归、表达式求值、广度优先搜索等。
第四章：串串是由零个或多个字符组成的有限序列，其长度可以为零。
在本章节中，我们将介绍串的定义和操作，包括字符串的模式匹配、模式识别和编辑操作。
串的相关算法在文本处理、计算机网络等领域具有广泛的应用。
第五章：数组和广义表数组是一种在内存中以连续方式存储的数据结构，它具有高效的随机访问特性。
广义表是线性表的一种扩展，可以包含表结构、原子结构以及其他广义表。
本章节将介绍数组和广义表的定义、操作和应用。
第六章：树树是一种非线性的数据结构，具有分层次、递归和层次遍历等特点。
在本章节中，我们将介绍树的基本概念、二叉树、树的遍历算法、平衡树以及树的应用，如编译器中的语法树、文件系统的目录结构等。
第七章：图图是一种复杂的非线性数据结构，由顶点集合和边集合组成。
在本章节中，我们将介绍图的各种表示方式，图的遍历算法、最短路径算法以及常用的图算法，如最小生成树算法和拓扑排序。
第六章习题1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。
3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，则该树中有多少个叶子结点并证明之。
4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。
5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？6．给出满足下列条件的所有二叉树：①前序和后序相同②中序和后序相同③前序和后序相同7． n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child 域有多少个？8．画出与下列已知序列对应的树Ｔ：树的先根次序访问序列为GFKDAIEBCHJ；树的后根次序访问序列为DIAEKFCJHBG。
9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10请为这8个字母设计哈夫曼编码。
10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点指针,是否可不用递归且不用栈来完成?请简述原因.11. 画出和下列树对应的二叉树：12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。
13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。
在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。
15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。
16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。
17．对以孩子-兄弟链表表示的树编写计算树的深度的算法。
18．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。
以二叉树或树作为表的组织形式，称为树表，它是一类动态查找表，不仅适合于数据查找，也适合于表插入和删除操作。
常见的树表：二叉排序树平衡二叉树B-树B+树9.3.1 二叉排序树二叉排序树（简称BST）又称二叉查找（搜索）树，其定义为：二叉排序树或者是空树，或者是满足如下性质（BST性质）的二叉树：❶若它的左子树非空，则左子树上所有节点值（指关键字值）均小于根节点值；❷若它的右子树非空，则右子树上所有节点值均大于根节点值；❸左、右子树本身又各是一棵二叉排序树。
注意：二叉排序树中没有相同关键字的节点。
二叉树结构满足BST性质：节点值约束二叉排序树503080209010854035252388例如:是二叉排序树。
66不试一试二叉排序树的中序遍历序列有什么特点？二叉排序树的节点类型如下：typedef struct node{KeyType key;//关键字项InfoType data;//其他数据域struct node*lchild,*rchild;//左右孩子指针}BSTNode;二叉排序树可看做是一个有序表，所以在二叉排序树上进行查找，和二分查找类似，也是一个逐步缩小查找范围的过程。
1、二叉排序树上的查找Nk< bt->keybtk> bt->key 每一层只和一个节点进行关键字比较！∧∧p查找到p所指节点若k<p->data，并且p->lchild=NULL，查找失败。
若k>p->data，并且p->rchild=NULL，查找失败。
查找失败的情况加上外部节点一个外部节点对应某内部节点的一个NULL指针递归查找算法SearchBST()如下（在二叉排序树bt上查找关键字为k的记录，成功时返回该节点指针，否则返回NULL）：BSTNode*SearchBST(BSTNode*bt,KeyType k){if(bt==NULL||bt->key==k)//递归出口return bt;if(k<bt->key)return SearchBST(bt->lchild,k);//在左子树中递归查找elsereturn SearchBST(bt->rchild,k);//在右子树中递归查找}在二叉排序树中插入一个关键字为k的新节点，要保证插入后仍满足BST性质。
第6章树和二叉树习题解答一、下面是有关二叉树的叙述，请判断正误（每小题1分，共10分）（√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。
（×）2.二叉树中每个结点的两棵子树的高度差等于1。
（√）3.二叉树中每个结点的两棵子树是有序的。
（×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。
（×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。
（应当是二叉排序树的特点）（×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。
（应2i-1）（×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
（×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。
（应2i-1）（√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
（正确。
用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。
由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。
）即有后继链接的指针仅n-1个。
（√）10. 〖01年考研题〗具有12个结点的完全二叉树有5个度为2的结点。
最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5二、填空（每空1分，共15分）1．由３个结点所构成的二叉树有5种形态。
2. 【计算机研2000】一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。
注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。
3．一棵具有２５７个结点的完全二叉树，它的深度为9。
（注：用⎣ log2(n) ⎦+1= ⎣ 8.xx ⎦+1=94.【全国专升本统考题】设一棵完全二叉树有700个结点，则共有350个叶子结点。
【课后习题】第6章树和二叉树网络工程2010级（）班学号：姓名：一、填空题（每空1分，共16分)1.从逻辑结构看，树是典型的。
2.设一棵完全二叉树具有999个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个度为1的结点。
3.由n个权值构成的哈夫曼树共有个结点。
4.在线索化二叉树中，T所指结点没有左子树的充要条件是。
5.在非空树上，_____没有直接前趋。
6.深度为k的二叉树最多有结点，最少有个结点。
7.若按层次顺序将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么当i为且小于n时，结点i的右兄弟是结点，否则结点i没有右兄弟。
8.N个结点的二叉树采用二叉链表存放，共有空链域个数为。
9.一棵深度为7的满二叉树有___ ___个非终端结点。
10.将一棵树转换为二叉树表示后,该二叉树的根结点没有。
11.采用二叉树来表示树时，树的先根次序遍历结果与其对应的二叉树的遍历结果是一样的。
12.一棵Huffman树是带权路径长度最短的二叉树，权值的外结点离根较远。
二、判断题（如果正确，在对应位置打“√”，否则打“⨯”。
每题0.5分，共5分)1.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i-1个结点。
2.二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该二叉树的根结点是那一个，则可以确定这棵二叉树。
3.一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。
4.度≤2的树就是二叉树。
5.一棵Huffman树是带权路径长度最短的二叉树，权值较大的外结点离根较远。
6.采用二叉树来表示树时，树的先根次序遍历结果与其对应的二叉树的前序遍历结果是一样的。
7.不存在有偶数个结点的满二叉树。
8.满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树。
9.已知二叉树的前序遍历顺序和中序遍历顺序，可以惟一确定一棵二叉树；10.已知二叉树的前序遍历顺序和后序遍历顺序，不能惟一确定一棵二叉树；三、单项选择（请将正确答案的代号填写在下表对应题号下面。
