下载文档原格式
期末复习复习第一章绪论数据：计算机处理的信息总称数据项：最小单位数据元素：最基本单数据对象：元素集合数据结构：相互之间存在一种或多种特定关系的数据元素集合。
概念：数据元素之间的关系线性结构：一对逻辑结构非线性结构数据结构树：一对多图：多对多顺序存储结构链表存储结构存储结构。
索引。
基。
散列。
础知数据运算识算法描述：指令的有限有序序列有穷性确定性算法特性可行性算法输入输出时间复杂度算法分析空间复杂度、计算机算法必须具备输入、输出、可行性、确定性、有穷性５个特性。
1 2、算法分析的两个主要方面是空间复杂度和时间复杂度。
3、数据元素是数据的基本单位。
4、数据项是数据的最小单位。
5、数据结构是带结构的数据元素的集合。
6、数据的存储结构包括顺序、链接、散列和索引四种基本类型。
线性表复习第二章定义逻辑关系：前趋后继节省空间基本特点随机存取插、删效率低顺序存储结构插入基本运算删除一个数据一个指针多占空特查找费插、删效率无法查找前趋结单链运算特点：单链表+前趋指针域链表存储双向结构链表插入运算删除特点：单链表的尾结点指针循环指向附加头结点。
链表运算：联接1 、一个指向后继结点的指针、在双链表中，每个结点有两个指针域，包括一个指向前驱结点的指针 2、线性表采用顺序存储，必须占用一片连续的存储单元、线性表采用链式存储，便于进行插入和删除操作3 、线性表采用顺序存储和链式存储优缺点比较。
4 5、简单算法复习栈和队列第三章．栈的概念：在一端操作的线性表LIFO栈的特点：先进后出存储结初始化push 进栈运算算法pop出栈队列概念：在两端操作的线性表FIFO队列特点：先进先出假溢出顺序队列front=rear队空：循环队列front=(rear+1)%MAXSIZE队满：队列front∧队空：链队列rear初始化判空顺序：进队基本运算链队：出队取队首元素1栈和队列的异同点。
、、2栈和队列的基本运算出栈和出队、3 、4基本运算复习串第四章．n(≥)个字符组成的有限序列1定义：由”c……cS=”cc n231串长度、空白串、空串。
数据结构期末复习要点第一章绪论1、掌握基本概念和术语，看教材P4—P6部分内容；2、看P10—P11关于类C的语法描述，算法设计写代码时可用到；3、掌握算法的特征（5个）和要求（5个）（P13—P14），能够结合具体算法分析算法的时间复杂度和空间复杂度（比如线性表的插入、删除操作，查找、排序等操作），理解O(n)、O(1)等时间复杂度的具体含义（P14—P17）。
第二章线性表1、看教材P21—P26，掌握有关线性表顺序存储的内容：（1）顺序表的随机存取（P21计算地址的公式）；（2）顺序表的表示（P22的Typedef）；（3）顺序表为空、为满的判定，插入和删除操作的特征以及时间复杂度的分析（P23—P25）；（4）有关顺序表的编程题。
2、看教材P27—P30，掌握有关线性表链式存储的内容：（1）单链表的表示（P28的Typedef）；（2）单链表为空的判定（带头结点、不带头结点）；（3）单链表插入、删除操作的特征（操作点的确定以和指针的修改）以及时间复杂度分析（P29—P30）；（4）有关单链表的编程。
3、为节约时间，循环链表、双向链表以及多项式加法可以不看；4、算法设计题要求写代码，在本章体现的可能性比较大。
第三章栈和队列1、顺序栈的表示，栈操作的特点以及为空、为满的判定（P46—P47）；2、栈的应用举例看个标题就足够了；3、链队列的表示以及入队、出队操作（P61—P62）；4、循环队列为空、为满的判定（P65的代码中）；5、离散事件模拟这节不用看；6、第四章只需要看P70就够了，掌握串的特点（元素受限），串长度、空串、串的位置、串相等几个概念即可。
第六章树和二叉树1、看教材P120，了解有关树的概念和术语；2、了解二叉树的链式存储结构（P127），掌握二叉树的性质（P123—P125），并会做题（参考课件或指导书相关内容）；3、掌握二叉树的各种遍历算法（P128—P129或课件）：（1）能够根据二叉树写出各种遍历序列；（2）能够由两种遍历序列（必须包含中序序列）恢复二叉树；（3）理解二叉树遍历算法的递归代码，能够读懂代码含义。
数据结构复习题集一、判断题1.线性表的长度是线性表所占用的存储空间的大小。
( F )2.双循环链表中，任意一结点的后继指针均指向其逻辑后继。
( F )3.在对链队列做出队操作时，不会改变front指针的值。
( F )4.如果两个串含有相同的字符，则说它们相等。
( F )5.如果二叉树中某结点的度为1，则说该结点只有一棵子树。
(T )6.已知一棵树的先序序列和后序序列，一定能构造出该树。
( F )7.图G的一棵最小代价生成树的代价未必小于G的其它任何一棵生成树的代价。
(T )8.图G的拓扑序列唯一，则其弧数必为n-1（其中n为顶点数）。
( F )9.对一个堆按层次遍历，不一定能得到一个有序序列。
(T )10.直接选择排序算法满足：其时间复杂度不受数据的初始特性影响，为O(n2)。
(T )11. 线性表的逻辑顺序与物理顺序总是一致的。
( F )12. 线性表的顺序存储表示优于链式存储表示。
( F )13.线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。
(T )14. 二维数组是其数组元素为线性表的线性表。
( F )15. 每种数据结构都应具备三种基本运算：插入、删除和搜索。
(T )16.（101，88，46，70，34，39，45，58，66，10）是堆；(T )17.将一棵树转换成二叉树后，根结点没有左子树；( F )18.对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同；(F)19.哈夫曼树是带权外部路径长度最短的树，路径上权值较大的结点离根较近( T )20.用一组地址连续的存储单元存放的元素一定构成线性表。
(F)21.堆栈、队列和数组的逻辑结构都是线性表结构。
( T )22.给定一组权值，可以唯一构造出一棵哈夫曼树。
( F)23.相对于索引文件的基本数据，索引表包含的信息量相对少得多，因此。
索引表可以常驻内存。
( T)24.在平均情况下，快速排序法最快，堆积排序法最节省空间。
1、数据(Data) ：是客观事物的符号表示。
在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素(Data Element)：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。
一个数据元素可由若干个数据项(Data Item)组成。
数据项是数据的不可分割的最小单位。
数据项是对客观事物某一方面特性的数据描述。
数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。
如字符集合C={‘A’,’B’,’C,…} 。
数据结构(Data Structure)：是指相互之间具有(存在)一定联系(关系)的数据元素的集合。
元素之间的相互联系(关系)称为逻辑结构。
数据元素之间的逻辑结构有四种基本类型，如图1-3所示。
①集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。
②线性结构：结构中的数据元素之间存在一对一的关系。
③树型结构：结构中的数据元素之间存在一对多的关系。
④图状结构或网状结构：结构中的数据元素之间存在多对多的关系。
2、顺序结构：数据元素存放的地址是连续的；链式结构：数据元素存放的地址是否连续没有要求。
数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。
在C语言中，用一维数组表示顺序存储结构；用结构体类型表示链式存储结构。
3、C语言中用带指针的结构体类型来描述typedef struct Lnode{ ElemType data; /*数据域，保存结点的值*/struct Lnode *next; /*指针域*/}LNode; /*结点的类型*/4、循环队列为空：front=rear 。
循环队列满：(rear+1)%MAX_QUEUE_SIZE =front。
5、性质1：在非空二叉树中，第i层上至多有2i-1个结点(i≧1)。
性质2：深度为k的二叉树至多有2k-1个结点（k≧1) 。
第5章数组和广义表5.1 复习笔记一、数组的定义1．二维数组类似于线性表，一个二维数组的逻辑结构形式表示为：2-Array＝（D，R）其中D＝{a ij|i＝c1，c1＋1，…，d l，j＝c2，c2＋1，…，d2，a ij∈D0}R＝{ROW，COL}ROW＝{<a ij，a i，j＋1>|c1≤i≤d1，c2≤j≤d2－1，a ij，a i，j＋1∈D}COL＝{<a ij，a i＋1，j>|c1≤i≤d1－1，c2≤j≤d2，a ij，a i＋1，j∈D}D0为某个数据对象，c1，c2，d1，d2均为整数。
【注意】①二维数组中含有（d1－c1＋1）×（d2－c2＋1）个数据元素，每个数据元素a ij都受行关系、列关系约束。
②a i，j＋1是a ij在行关系中的直接后继元素；而a i＋1，j是a ij在列关系中的直接后继元素。
③数组中所有的数据元素属于同一数据类型。
2．n维数组n 维数组的逻辑结构形式定义如下：n-Array ＝（D ，R ）其中 12120,1,,,1,2,,(0),n n i i i i j j j j j j i i j c c d i n n D a a D c d ⎧⎫=+=>⎪⎪=⎨⎬∈⎪⎪⎩⎭且和均为整数12{,},,n R R R R =11111111,1,i n i n i n i n i j j j j k k k j j i i i j j j j j j R a a c j d k n k c j d a a D ++=<>⎧⎫≤≤≤≤≠⎪⎪≤≤-⎨⎬⎪⎪∈⎩⎭ 且【注意】 ①n 维数组含有)1(1+-∏=i i ni c d 个数据元素，每个数据元素都受n 个关系的约束。
②在每个关系中，数据元素12(1)n j j j i i i a c j d ⋯≤≤-都有一个直接后继元素。
二、数组的顺序表示和实现1．二维数组的两种存储方式二维数组的顺序存储结构有两种存储方式：（1）以列序为主序的存储方式，如图5-1（a）所示；（2）以行序为主序的存储方式，如图5-1（b）所示。
1.复杂性分析对各种操作的时间复杂性的分析。
主要是链表，树，排序等简单一些的分析。
分析的时候,从简单的入手,学会方法。
后续的各种豆可能让你分析时间复杂度。
线性链表（顺序表和单链表）链表循环链表双向链表2.线性结构队列（循环队列)栈链表主要操作:找某一个元素，插入一个（在哪个位置增加），删除一个（在哪个位置删除)。
栈：查找，插入（位置固定），删除(位置固定）队列：查找，插入（位置固定)，删除（位置固定）顺序表（可以视为一个数组）单链表：（删除）(插入）倒置：(查找）循环链表双向链表栈：(插入删除查找)队列(插入删除查找）循环队列的实现，并不是像上面的图那样，实现了一个循环的样子。
3.二叉树基本概念二叉树是每个节点最多有两个子树的有序树。
二叉树常被用于实现二叉查找树和二叉堆。
值得注意的是,二叉树不是树的特殊情形。
二叉树是每个结点最多有两个子树的有序树。
通常根的子树被称作“左子树”(left subtree）和“右子树”（right subtree）。
二叉树常被用作二叉查找树和二叉堆或是二叉排序树。
二叉树的每个结点至多只有二棵子树（不存在出度大于2的结点），二叉树的子树有左右之分,次序不能颠倒。
二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，但树和二叉树有两个主要差别：1. 树中结点的最大度数没有限制,而二叉树结点的最大度数为2；2。
树的结点无左、右之分，而二叉树的结点有左、右之分。
二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：（1）空二叉树——如图（a)；（2)只有一个根结点的二叉树——如图（b);(3）只有左子树——如图（c）；（4)只有右子树-—如图（d）;(5）完全二叉树-—如图（e)注意:尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形性质（1）在非空二叉树中，第i层的结点总数不超过, i〉=1;(2）深度为h的二叉树最多有2^h—1个结点（h>=1），最少有h个结点；（3）对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2,则N0=N2+1；(4）具有n个结点的完全二叉树的深度为(5）有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系: 若I为结点编号则如果I>1,则其父结点的编号为I/2;如果2*I<=N，则其左儿子(即左子树的根结点）的编号为2*I；若2＊I>N,则无左儿子；如果2＊I+1〈=N,则其右儿子的结点编号为2*I+1；若2*I+1〉N，则无右儿子。
数据结构-（严蔚敏C语⾔版）-学习、复习提纲期末复习第⼀章绪论复习1、计算机算法必须具备输⼊、输出、可⾏性、确定性、有穷性５个特性。
2、算法分析的两个主要⽅⾯是空间复杂度和时间复杂度。
3、数据元素是数据的基本单位。
数据结算法数据：计算机处理的信息总称数据项：最⼩单位数据元素：最基本单概念：数据元素之间的关系线性结构：⼀对⼀⾮线性结构树：⼀对多图：多对多顺序存储结构链表存储结构算法描述：指令的有限有有穷性确定性可⾏性时间复杂4、数据项是数据的最⼩单位。
5、数据结构是带结构的数据元素的集合。
6、数据的存储结构包括顺序、链接、散列和索引四种基本类型。
第⼆章线性表复习1、在双链表中，每个结点有两个指针域，包括⼀个指向前驱结点的指针、⼀个指向后继结点的指针2、线性表采⽤顺序存储，必须占⽤⼀⽚连续的存储单元定义节省空间随机存取插⼊3、线性表采⽤链式存储，便于进⾏插⼊和删除操作4、线性表采⽤顺序存储和链式存储优缺点⽐较。
5、简单算法第三章栈和队列复习1、栈和队列的异同点。
2、栈和队列的基本运算 3、出栈和出队 4、基本运算存储结栈的概念：在⼀端操作的线性运算算栈的特点：先进后出初始化进栈顺序队队列概念：在两端操作的线性假溢出链队列队列特点：先进先出基本运顺序：队空：队满：(1)队初始化判空进队第四章串复习第五章数组和⼴义表复习定义：由n(≥1)个字符组成的有限序列紧缩格式⾮紧缩格式以字节为单位的存储基本运(s) 串长度 (s12) 联接 (s12) ⽐较模式匹失败链接值匹配算法单字符链表串串变量的存储映像：串名、串值对应关系表顺序存储压缩存储⾏优先顺序存放列优先顺序存放稀疏矩应⽤表达式⼴义表定义：n(≥0)个元素的有限序表头：(A)= a 1 概念：长度、深度、原⼦、⼦表尾：(A)=(a23,…)表结特殊矩对称矩阵三⾓矩阵三元组存储：三元组原⼦结第六章树复习1、三个结点可以组成2种不同形态的树。
2、⼀个稀疏矩阵*n 采⽤三元组形式表⽰，若完成了其的转置运算要经过哪⼏步:⼆叉树概定义：递归定义，不为空双亲、孩⼦、叶⼦、兄弟、存储⽅顺序：满、完全⼆⼆叉树已知先根、中根序列画树；先根线索线索线索树的画法树、森林与⼆叉树的相互树、森⼆叉排树的应哈夫曼左中哈夫曼树的矩阵的⾏、列数值互换、矩阵元素所在⾏列值互换、元素在矩阵中排列的位置）重新排列3、若⼆叉树中每⼀层结点的个数都达到了最⼤，则称为⼀棵满⼆叉树。
严蔚敏数据结构复习整理完整版数据结构是计算机科学中的重要基础课程，是指数据组织、存储和处理的方式。
严蔚敏教授是中国计算机教育领域的知名专家，他的《数据结构》一书被广泛使用于计算机相关专业的教学中。
下面是严蔚敏数据结构复习整理的完整版，总结了数据结构的基本概念、常见数据结构的特点和使用场景，以及一些重要的算法思想和应用。
一、数据结构的基本概念1.数据：数据是计算机能识别、处理的符号集合，可以是数字、文字、图像等。
2.数据元素：数据中的一个个基本单位，也称为记录。
3.数据项：数据元素中的一个个最小单位，是不可分割的数据单位。
二、常见数据结构1.数组：一组具有相同数据类型的元素的集合，可以通过下标来访问和操作。
2.链表：一组通过指针连接起来的数据元素的集合，可以分为单向链表和双向链表。
3.栈：一种特殊的线性表，只能在表尾进行插入和删除操作，遵循先进后出的原则。
4.队列：一种特殊的线性表，只能在表尾进行插入操作，在表头进行删除操作，遵循先进先出的原则。
5.树：一种非线性的数据结构，具有层次结构的特点，包括二叉树、二叉树、平衡树等。
6.图：一种非线性的数据结构，由顶点和边组成，包括有向图和无向图。
7.堆：一种完全二叉树的结构，用于实现优先队列等需要快速找到最值的场景。
8.哈希表：一种以键值对形式存储数据的数据结构，通过哈希函数将键映射到对应的位置，常用于快速查找场景。
三、常用算法和应用1.线性查找和二分查找：分别用于在无序数组和有序数组中查找指定的元素。
2.冒泡排序和快速排序：分别用于对数组进行升序排序，冒泡排序的时间复杂度较高，快速排序的时间复杂度较低。
3.广度优先和深度优先：分别用于在图中特定的路径，广度优先适用于找最短路径，深度优先适用于找所有路径。
4.迪杰斯特拉算法和贪心算法：迪杰斯特拉算法用于计算图中最短路径，贪心算法用于求解最优问题时，每一步都选择当前最好的选择。
5.动态规划算法：一种分阶段求解的问题求解方法，适用于具有最优子结构的问题，将问题分解为子问题，并逐步求解。
1.复杂性分析对各种操作的时间复杂性的分析。
主要是链表，树，排序等简单一些的分析。
分析的时候,从简单的入手,学会方法。
后续的各种豆可能让你分析时间复杂度。
线性链表（顺序表和单链表）链表循环链表双向链表2.线性结构队列（循环队列)栈链表主要操作:找某一个元素，插入一个（在哪个位置增加），删除一个（在哪个位置删除)。
栈：查找，插入（位置固定），删除(位置固定）队列：查找，插入（位置固定)，删除（位置固定）顺序表（可以视为一个数组）单链表：（删除）(插入）倒置：(查找）循环链表双向链表栈：(插入删除查找)队列(插入删除查找）循环队列的实现，并不是像上面的图那样，实现了一个循环的样子。
3.二叉树基本概念二叉树是每个节点最多有两个子树的有序树。
二叉树常被用于实现二叉查找树和二叉堆。
值得注意的是,二叉树不是树的特殊情形。
二叉树是每个结点最多有两个子树的有序树。
通常根的子树被称作“左子树”(left subtree）和“右子树”（right subtree）。
二叉树常被用作二叉查找树和二叉堆或是二叉排序树。
二叉树的每个结点至多只有二棵子树（不存在出度大于2的结点），二叉树的子树有左右之分,次序不能颠倒。
二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，但树和二叉树有两个主要差别：1. 树中结点的最大度数没有限制,而二叉树结点的最大度数为2；2。
树的结点无左、右之分，而二叉树的结点有左、右之分。
二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：（1）空二叉树——如图（a)；（2)只有一个根结点的二叉树——如图（b);(3）只有左子树——如图（c）；（4)只有右子树-—如图（d）;(5）完全二叉树-—如图（e)注意:尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形性质（1）在非空二叉树中，第i层的结点总数不超过, i〉=1;(2）深度为h的二叉树最多有2^h—1个结点（h>=1），最少有h个结点；（3）对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2,则N0=N2+1；(4）具有n个结点的完全二叉树的深度为(5）有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系: 若I为结点编号则如果I>1,则其父结点的编号为I/2;如果2*I<=N，则其左儿子(即左子树的根结点）的编号为2*I；若2＊I>N,则无左儿子；如果2＊I+1〈=N,则其右儿子的结点编号为2*I+1；若2*I+1〉N，则无右儿子。
（6)给定N个节点，能构成h（N)种不同的二叉树。
h(N)为卡特兰数的第N项。
h（n）=C(2*n，n）/(n+1).（7）设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i存储结构顺序存储表示二叉树可以用数组或线性表来存储,而且如果这是满二叉树，这种方法不会浪费空间。
用这种紧凑排列,如果一个结点的索引为i,它的子结点能在索引2i+1和2i+2找到，并且它的父节点（如果有）能在索引floor(（i—1）/2）找到（假设根节点的索引为0）。
这种方法更有利于紧凑存储和更好的访问的局部性,特别是在前序遍历中。
然而，它需要连续的存储空间，这样在存储高度为h的n个结点组成的一般普通树时将会浪费很多空间.一种最极坏的情况下如果深度为h的二叉树每个节点只有右孩子需要占用2的h次幂减1，而实际却只有h个结点，空间的浪费太大，这是顺序存储结构的一大缺点。
/* 二叉树的顺序存储表示 */#define MAX_TREE_SIZE 100 /＊二叉树的最大节点数＊/typedef TElemType SqBiTree［MAX_TREE_SIZE］； /* 0号单元存储根节点 */typedef struct{int level，order； /* 节点的层，本层序号（按满二叉树计算) */}position;二叉链表存储表示/＊二叉樹的二叉鏈表存儲表示 */typedef struct BiTNode{TElemType data;struct BiTNode *lchild，*rchild; /＊左右孩子指針＊/｝BiTNode，*BiTree；遍历算法二叉树的遍历三种方式，如下:（1)前序遍历（DLR），首先访问根结点,然后遍历左子树，最后遍历右子树.简记根-左—右。
（2)中序遍历（LDR）,首先遍历左子树，然后访问根结点，最后遍历右子树。
简记左-根—右。
（3)后序遍历（LRD)，首先遍历左子树，然后遍历右子树，最后访问根结点。
简记左-右—根。
例1：如上图所示的二叉树，若按前序遍历,则其输出序列为。
若按中序遍历,则其输出序列为.若按后序遍历，则其输出序列为。
前序：根A,A的左子树B,B的左子树没有，看右子树,为D，所以A-B-D。
再来看A的右子树，根C，左子树E，E的左子树F，E的右子树G，G的左子树为H，没有了结束。
连起来为C-E—F-G—H，最后结果为ABDCEFGH中序：先访问根的左子树,B没有左子树，其有右子树D，D无左子树,下面访问树的根A，连起来是BDA。
再访问根的右子树，C的左子树的左子树是F,F的根E，E的右子树有左子树是H，再从H出发找到G，到此C的左子树结束，找到根C，无右子树，结束.连起来是FEHGC, 中序结果连起来是BDAFEHGC后序:B无左子树，有右子树D,再到根B.再看右子树，最下面的左子树是F，其根的右子树的左子树是H，再到H的根G,再到G的根E，E的根C无右子树了，直接到C，这时再和B找它们其有的根A，所以连起来是DBFHGECA深度优先遍历在深度优先中，我们希望从根结点访问最远的结点。
和图的深度优先搜索不同的是，不需记住访问过的每一个结点,因为树中不会有环。
广度优先遍历和深度优先遍历不同，广度优先遍历会先访问离根节点最近的节点。
完全二叉树，满二叉树1.满二叉树：一棵深度为k，且有个节点称之为满二叉树2.完全二叉树:深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树4.树基本概念树(tree）是包含n（n〉0）个结点的有穷集，其中：（1）每个元素称为结点（node）；（2）有一个特定的结点被称为根结点或树根(root）。
（3)除根结点之外的其余数据元素被分为m(m≥0)个互不相交的集合T1，T2,……Tm—1，其中每一个集合Ti（1〈=i〈=m）本身也是一棵树,被称作原树的子树（subtree）。
树也可以这样定义：树是由根结点和若干颗子树构成的。
树是由一个集合以及在该集合上定义的一种关系构成的.集合中的元素称为树的结点，所定义的关系称为父子关系。
父子关系在树的结点之间建立了一个层次结构.在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。
我们可以形式地给出树的递归定义如下:单个结点是一棵树，树根就是该结点本身。
设T1,T2，..，Tk是树,它们的根结点分别为n1,n2,。
.,nk。
用一个新结点n作为n1，n2，..,nk 的父亲,则得到一棵新树，结点n就是新树的根。
我们称n1，n2，.。
,nk为一组兄弟结点,它们都是结点n的子结点.我们还称T1，T2,。
.,Tk为结点n的子树。
空集合也是树，称为空树。
空树中没有结点.术语1.节点的度：一个节点含有的子树的个数称为该节点的度；2.树的度：一棵树中，最大的节点的度称为树的度；3.叶节点或终端节点：度为零的节点;4.非终端节点或分支节点：度不为零的节点；5.父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；6.孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；7.兄弟节点：具有相同父节点的节点互称为兄弟节点；8.节点的层次：从根开始定义起，根为第1层，根的子节点为第2层,以此类推；9.树的高度或深度：树中节点的最大层次；10.堂兄弟节点：父节点在同一层的节点互为堂兄弟；11.节点的祖先：从根到该节点所经分支上的所有节点;12.子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
13.森林：由m(m〉=0）棵互不相交的树的集合称为森林；存储父节点表示法/＊树节点的定义 */＃define MAX_TREE_SIZE 100typedef struct｛TElemType data;int parent； /* 父节点位置域＊/｝ PTNode；typedef struct｛PTNode nodes[MAX_TREE_SIZE］；int n; /＊节点数＊/｝ PTree;孩子链表表示法/*树的孩子链表存储表示＊/typedef struct CTNode { // 孩子节点int child;struct CTNode ＊next；｝ *ChildPtr;typedef struct ｛ElemType data； // 节点的数据元素ChildPtr firstchild； // 孩子链表头指针｝ CTBox;typedef struct { CTBox nodes[MAX_TREE_SIZE］;int n， r; // 节点数和根节点的位置} CTree;5。
森林6.森林、树与二叉树的转换将树转换为二叉树树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟.按照这种关系很自然地就能将树转换成相应的二叉树：①在所有兄弟结点之间加一连线；②对每个结点,除了保留与其长子的连线外，去掉该结点与其它孩子的连线.注意：由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。
2）将一个森林转换为二叉树具体方法是：①将森林中的每棵树变为二叉树②因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起,就形成了一棵二叉树。
二叉树到树、森林的转换把二叉树转换到树和森林自然的方式是：若结点x是双亲y的左孩子,则把x的右孩子，右孩子的右孩子,…,都与y用连线连起来，最后去掉所有双亲到右孩子的连线.图二元组的定义图G是一个有序二元组（V，E），其中V称为顶集(Vertices Set），E称为边集(Edges set）,E与V不相交.它们亦可写成V（G）和E（G）。
E的元素都是二元组，用(x,y)表示，其中x,y∈V。
三元组的定义图G是指一个三元组(V，E,I),其中V称为顶集，E称为边集，E与V不相交；I 称为关联函数,I将E中的每一个元素映射到。
如果e被映射到(u,v)，那么称边e连接顶点u，v,而u,v则称作e的端点，u，v此时关于e相邻.同时，若两条边i,j有一个公共顶点u,则称i,j关于u相邻。
有/无向图如果给图的每条边规定一个方向,那么得到的图称为有向图.在有向图中，与一个节点相关联的边有出边和入边之分。
