下载文档原格式
数据结构树的知识点总结一、树的基本概念。
1. 树的定义。
- 树是n（n ≥ 0）个结点的有限集。
当n = 0时，称为空树。
在任意一棵非空树中：- 有且仅有一个特定的称为根（root）的结点。
- 当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1、T2、…、Tm，其中每个集合本身又是一棵树，并且称为根的子树（sub - tree）。
2. 结点的度、树的度。
- 结点的度：结点拥有的子树个数称为结点的度。
- 树的度：树内各结点的度的最大值称为树的度。
3. 叶子结点（终端结点）和分支结点（非终端结点）- 叶子结点：度为0的结点称为叶子结点或终端结点。
- 分支结点：度不为0的结点称为分支结点或非终端结点。
- 除根结点之外，分支结点也称为内部结点。
4. 树的深度（高度）- 树的层次从根开始定义起，根为第1层，根的子结点为第2层，以此类推。
树中结点的最大层次称为树的深度（或高度）。
二、二叉树。
1. 二叉树的定义。
- 二叉树是n（n ≥ 0）个结点的有限集合：- 或者为空二叉树，即n = 0。
- 或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
2. 二叉树的特点。
- 每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
- 二叉树的子树有左右之分，次序不能颠倒。
3. 特殊的二叉树。
- 满二叉树。
- 一棵深度为k且有2^k - 1个结点的二叉树称为满二叉树。
满二叉树的特点是每一层上的结点数都是最大结点数。
- 完全二叉树。
- 深度为k的、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。
完全二叉树的叶子结点只可能在层次最大的两层上出现；对于最大层次中的叶子结点，都依次排列在该层最左边的位置上；如果有度为1的结点，只可能有一个，且该结点只有左孩子而无右孩子。
三、二叉树的存储结构。
1. 顺序存储结构。
- 二叉树的顺序存储结构就是用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。
一、基础知识题6.1设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，求树T中的叶子数。
【解答】设度为m的树中度为0,1,2,…,m的结点数分别为n0, n1, n2,…, nm，结点总数为n，分枝数为B，则下面二式成立n= n0+n1+n2+…+nm (1)n=B+1= n1+2n2 +…+mnm+1 (2)由(1)和(2)得叶子结点数n0=1+即： n0=1+(1-1)*4+(2-1)*2+(3-1)*1+(4-1)*1=86.2一棵完全二叉树上有1001个结点，求叶子结点的个数。
【解答】因为在任意二叉树中度为2 的结点数n2和叶子结点数n0有如下关系：n2=n0-1,所以设二叉树的结点数为n, 度为1的结点数为n1，则n= n0+ n1+ n2n=2n0+n1-11002=2n0+n1由于在完全二叉树中，度为1的结点数n1至多为1，叶子数n0是整数。
本题中度为1的结点数n1只能是0，故叶子结点的个数n0为501.注：解本题时要使用以上公式，不要先判断完全二叉树高10，前9层是满二叉树，第10层都是叶子，……。
虽然解法也对，但步骤多且复杂，极易出错。
6.3 一棵124个叶结点的完全二叉树，最多有多少个结点。
【解答】由公式n=2n0+n1-1,当n1为1时，结点数达到最多248个。
6.4．一棵完全二叉树有500个结点，请问该完全二叉树有多少个叶子结点？有多少个度为1的结点？有多少个度为2的结点？如果完全二叉树有501个结点，结果如何？请写出推导过程。
【解答】由公式n=2n0+n1-1，带入具体数得，500=2n0+n1-1，叶子数是整数，度为1的结点数只能为1，故叶子数为250，度为2的结点数是249。
若完全二叉树有501个结点，则叶子数251，度为2的结点数是250，度为1的结点数为0。
6.5 某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数是多少。
填空题（10 ＊1’ = 10' ）一、概念题2。
2.当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。
2。
3。
当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。
2。
6。
带头结点的单链表L中只有一个元素结点的条件是L—〉Next->Next==Null。
3。
6。
循环队列的引入,目的是为了克服假溢出.4。
2。
长度为0的字符串称为空串。
4。
5.组成串的数据元素只能是字符。
4。
8.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。
7.2。
为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。
5.7。
广义表的深度是广义表中括号的重数7。
8.有向图G可拓扑排序的判别条件是有无回路。
7.9。
若要求一个稠密图的最小生成树，最好用Prim算法求解。
8。
8.直接定址法法构造的哈希函数肯定不会发生冲突。
9。
2。
排序算法所花费的时间，通常用在数据的比较和交换两大操作。
1。
1。
通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。
1。
2.对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。
1。
3。
存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。
1。
4。
抽象数据类型的定义仅取决于它的一组逻辑特性,而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变,都不影响其外部使用。
1。
5.一个算法具有五大特性:有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。
2.8.在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点,则需执行下列语句:s—〉prior= p—〉prior; s-〉next= p; p-〉prior- next= s；p-〉prior= s；。
2.9。
在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空,并使得对单链表的操作（如插入和删除)在各种情况下统一。
⼆叉树遍历（前中后序遍历，三种⽅式）⽬录刷题中碰到⼆叉树的遍历，就查找了⼆叉树遍历的⼏种思路，在此做个总结。
对应的LeetCode题⽬如下：，，，接下来以前序遍历来说明三种解法的思想，后⾯中序和后续直接给出代码。
⾸先定义⼆叉树的数据结构如下：//Definition for a binary tree node.struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}};前序遍历，顺序是“根-左-右”。
使⽤递归实现：递归的思想很简单就是我们每次访问根节点后就递归访问其左节点，左节点访问结束后再递归的访问右节点。
代码如下：class Solution {public:vector<int> preorderTraversal(TreeNode* root) {if(root == NULL) return {};vector<int> res;helper(root,res);return res;}void helper(TreeNode *root, vector<int> &res){res.push_back(root->val);if(root->left) helper(root->left, res);if(root->right) helper(root->right, res);}};使⽤辅助栈迭代实现：算法为：先把根节点push到辅助栈中，然后循环检测栈是否为空，若不空，则取出栈顶元素，保存值到vector中，之后由于需要想访问左⼦节点，所以我们在将根节点的⼦节点⼊栈时要先经右节点⼊栈，再将左节点⼊栈，这样出栈时就会先判断左⼦节点。
代码如下：class Solution {public:vector<int> preorderTraversal(TreeNode* root) {if(root == NULL) return {};vector<int> res;stack<TreeNode*> st;st.push(root);while(!st.empty()){//将根节点出栈放⼊结果集中TreeNode *t = st.top();st.pop();res.push_back(t->val);//先⼊栈右节点，后左节点if(t->right) st.push(t->right);if(t->left) st.push(t->left);}return res;}};Morris Traversal⽅法具体的详细解释可以参考如下链接：这种解法可以实现O(N)的时间复杂度和O(1)的空间复杂度。
数据结构第六章题⽬讲解02⼀选择题：1、以下说法错误的是①树形结构的特点是⼀个结点可以有多个直接前趋②线性结构中的⼀个结点⾄多只有⼀个直接后继③树形结构可以表达(组织)更复杂的数据④树(及⼀切树形结构)是⼀种"分⽀层次"结构⑤任何只含⼀个结点的集合是⼀棵树2．深度为6的⼆叉树最多有( )个结点①64 ②63 ③32 ④313 下列说法中正确的是①任何⼀棵⼆叉树中⾄少有⼀个结点的度为2②任何⼀棵⼆叉树中每个结点的度都为2 ⼆叉树可空③任何⼀棵⼆叉树中的度肯定等于2 ④任何⼀棵⼆叉树中的度可以⼩于24 设森林T中有4棵树，第⼀、⼆、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成⼀棵⼆叉树后，且根结点的右⼦树上有（）个结点。
①n1-1 ②n1③n1+n2+n3④n2+n3+n4⼆．名词解释：1 结点的度 3。
叶⼦ 4。
分⽀点 5。
树的度三填空题⼆叉树第i(i>=1)层上⾄多有_____个结点。
1、深度为k(k>=1)的⼆叉树⾄多有_____个结点。
2、如果将⼀棵有n个结点的完全⼆叉树按层编号，则对任⼀编号为i(1<=i<=n)的结点X有：若i=1,则结点X是_ ____；若i〉1,则X的双亲PARENT(X)的编号为__ ____。
若2i>n，则结点X⽆_ _____且⽆_ _____；否则，X的左孩⼦LCHILD(X)的编号为____。
若2i+1>n，则结点X⽆__ ____；否则，X的右孩⼦RCHILD(X)的编号为_____。
4．以下程序段采⽤先根遍历⽅法求⼆叉树的叶⼦数，请在横线处填充适当的语句。
Void countleaf(bitreptr t,int *count)/*根指针为t，假定叶⼦数count的初值为0*/ {if(t!=NULL){if((t->lchild==NULL)&&(t->rchild==NULL))__ __;countleaf(t->lchild,&count);countleaf(t->rchild,&count);}}5 先根遍历树和先根遍历与该树对应的⼆叉树，其结果_____。
若x是二叉树中序线索树中一个有左孩子的结点1二叉树中序线索树二叉树中序线索树（Threaded Binary Tree）是指用线索把二叉树的空缺指针打上标记，使其成为双链表，以便让二叉树具有更强的访问能力，同时节省存储空间。
2特点线索标识：对于空链接而言，我们给其添加一个特殊标记，来标识空链接，用来控制遍历时循环跳出。
数据结构：在线索树中，将每一个节点结构体特殊定义为线索化节点结构体，用tag标记左右孩子的指针是否为空，及其空时的处理方式。
3操作中序线索树的操作主要是遍历二叉树，即中序遍历和前序遍历。
中序遍历：中序遍历的核心在于只有当结点的左子树遍历完了才能继续遍历右子树，所以用线索树以后，其中序遍历可以沿所有指向前驱结点的线索一路返回根结点，即访问根结点之前访问它的前驱，然后从根结点出发，依次访问所有后继结点。
前序遍历：前序遍历的核心在于无论根节点在哪里，都要先访问它，然后访问左孩子，最后访问右孩子。
因此采用线索树以后，只要沿着指向父结点的线索一路回退根结点，即可访问所有的先序顺序访问。
4具体应用二叉树中序线索树和树结构在很多应用程序中都有广泛的应用，其中最常用的两个应用分别是树查询和语法分析。
树查询：用线索树具有快速查询的特性，可以大大提高查询的速度，尤其是在复杂的树结构中使用线索树，查询的速度会更快。
语法分析：用于自动处理语言，是对源代码中的符号进行分析的过程，以构建出一棵源程序的语法树节点，可以用线索树这种数据结构来实现快速的访问和查找。
5若x是二叉树中序线索树中一个有左孩子的结点若节点x具有左孩子，那么该节点x通过线索把左孩子结点加上标记，以便于后续遍历，当访问x时，可通过线索遍历该左节点，并与其他节点信息进行交互，而不必从根结点开始重复遍历。
同时，如果该节点x的右节点不是叶子结点，那么可以借助线索快速找到x的右节点，不需要通过先找到x的左节点才能找到右节点。
简述二叉树的五种形态二叉树是一种常用的数据结构，它由节点组成，每个节点最多有两个子节点。
根据节点的分布情况，二叉树可以分为五种形态，分别是满二叉树、完全二叉树、平衡二叉树、搜索二叉树和线索二叉树。
一、满二叉树满二叉树是指除了叶子节点外，每个节点都有两个子节点的二叉树。
也就是说，满二叉树的所有层都是满的，并且最后一层的叶子节点都靠左排列。
满二叉树的节点数可以通过公式计算得到，假设树的高度为h，则节点数为2^h - 1。
满二叉树的特点是结构简单，查找速度快。
在满二叉树中，任意两个节点的路径长度都相同。
二、完全二叉树完全二叉树是指除了最后一层之外，其他层都是满的，并且最后一层的叶子节点都靠左排列的二叉树。
完全二叉树的特点是节点数较少，结构相对简单。
完全二叉树通常用数组来表示，因为它的节点之间的关系可以通过数组的下标来表示。
在完全二叉树中，任意一个节点的左子节点的下标为2i，右子节点的下标为2i+1。
三、平衡二叉树平衡二叉树是指左右子树的高度差不超过1的二叉树。
平衡二叉树的特点是查找、插入和删除的时间复杂度都为O(logn)，其中n是节点的数量。
平衡二叉树的高度可以通过节点的平衡因子来计算，平衡因子定义为左子树的高度减去右子树的高度。
平衡因子的取值范围为-1、0和1，当平衡因子的绝对值大于1时，需要通过旋转操作来调整树的平衡性。
四、搜索二叉树搜索二叉树，也称为二叉搜索树或排序二叉树，是一种特殊的二叉树。
它的特点是对于树中的任意一个节点，其左子树中的所有节点都小于它，右子树中的所有节点都大于它。
搜索二叉树的中序遍历结果是一个递增的有序序列。
搜索二叉树的特点是可以快速地查找某个节点，时间复杂度为O(logn)，其中n是节点的数量。
但是，如果搜索二叉树不平衡，即左子树或右子树过深，则会导致查找的时间复杂度退化为O(n)。
五、线索二叉树线索二叉树是对二叉树进行了优化的数据结构，它通过添加指向前驱和后继节点的线索，使得遍历操作更加高效。
画出中序线索二叉树简单例题
假设有一个二叉树如下：
A
/ \
B C
/ \ / \
D E F G
根据中序遍历的顺序，节点的访问顺序应该为 D -> B -> E -> A -> F -> C -> G。
我们可以通过添加线索化标记，将每个节点的左右空指针改为指向其前驱和后继节点。
这样，递归遍历中序线索二叉树时不再需要通过递归调用访问左右子树，而可以直接跳转到前驱或后继节点。
线索化后的二叉树如下：
D
\
B
/ \
E A
\
F
/ \
G C
在中序线索二叉树中，对于每个节点，其指向前驱节点的指针称为"前驱线索"，指向后继节点
的指针称为"后继线索"。
这样，我们可以通过线索化标记快速找到任意节点的前驱和后继节点，而不需要遍历整棵树。
例如，节点 A 的后继节点为 F，前驱节点为空。
节点 C 的后继节点为尚未线索化的节点 G，
前驱节点为节点 A。
节点 D 的后继节点为节点 B，前驱节点为尚未线索化的节点 E。
通过线索化，我们可以利用中序线索二叉树实现快速查找任意节点的前驱和后继节点，而不需要进行递归遍历。
这样，我们可以在时间复杂度为O(1) 的情况下完成前驱和后继节点的查找，大大提高了效率。
总结起来，中序线索二叉树可以在原有二叉树的基础上添加线索化标记，从而实现快速查找任意节点的前驱和后继节点。
这一特性在某些需要频繁查找节点前驱和后继的应用场景中具有重要意义。
中序线索化二叉树数据结构.当用二叉链表作为二叉树的存储结构时，因为每个结点中只有指向其左、右孩子结点的指针，所以从任一结点出发只能直接找到该结点的左、右孩子。
在一般情况下靠它无法直接找到该结点在某种遍历次序下的前驱和后继结点。
如果在每个结点中增加指向其前驱和后继结点的指针，将降低存储空间的效率。
与此同时，我们可以证明：在n个结点的二叉链表中含有n+1个空指针。
因为含n个结点的二叉链表中含有2n个指针，除了根结点，每个结点都有一个从父结点指向该结点的指针，因此一共使用了n-1个指针，所以在n个结点的二叉链表中含有2n-(n-1)=n+1个空指针。
因此，可以利用这些空指针，存放指向结点在某种遍历次序下的前驱和后继结点的指针。
这种附加的指针称为线索，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。
为了区分一个结点的指针是指向其孩子的指针，还是指向其前驱或后继结点的线索，可在每个结点中增加两个线索标志。
这样，线索二叉树结点类型定义为：LchildLtagDataRtagRchild其中：1. Ltag=0时，表示Lchild指向该结点的左孩子；2. Ltag=1时，表示Lchild指向该结点的线性前驱结点；3. Rtag=0时，表示Rchild指向该结点的右孩子；4. Rtag=1时，表示Rchild指向该结点的线性后继结点；以二叉链表结点数据结构所构成的二叉链表作为二叉树的存储结构，叫做线索二叉链表；指向结点的线性前驱或者线性后继结点的指针叫做线索；加上线索的二叉树称为线索二叉树；对二叉树以某种次序遍历将其变为线索二叉树的过程叫做线索化。
中序线索化是指用二叉链表结点数据结构建立二叉树的二叉链表，然后按照中序遍历的方法访问结点时建立线索。
例如有如上图所示二叉树，则中序遍历的顺序是：O / J * I + H A G【参考程序】#include <stdio.h>#include <malloc.h>typedef enum{Link,Thread} PointerTag; /*指针标志*/typedef char DataType;typedef struct BiThreTree{ /*定义结点元素*/PointerTag LTag,RTag;DataType data;struct BiThreTree *lchild,*rchild;}BiThreTree;BiThreTree *pre; /*全局变量，用于二叉树的线索化*/BiThreTree *CreateT ree() /*按前序输入建立二叉树*/{BiThreTree *T;DataType ch;scanf("%c",&ch);if(ch==’#’)T=NULL;else{T=(BiThreTree *)malloc(sizeof(BiThreTree));T->data=ch;T->LTag=Link; /*初始化时指针标志均为Link*/T->RTag=Link;T->lchild=CreateTree();T->rchild=CreateTree();}return T;}void InThread(BiThreTree *T){BiThreTree *p;p=T;if(p){InThread(p->lchild);if(!p->lchild){ p->LTag=Thread;p->lchild=pre;}if(!pre->rchild){ pre->RTag=Thread;pre->rchild=p;}pre=p;InThread(p->rchild);}}BiThreTree *InOrderThrTree(BiThreTree *T) /*中序线索化二叉树*/ {BiThreTree *Thre; /*Thre为头结点的指针*/ Thre=(BiThreTree *)malloc(sizeof(BiThreTree));Thre->lchild=T;Thre->rchild=Thre;pre=Thre;InThread(T);pre->RTag=Thread;pre->rchild=Thre;Thre->rchild=pre;return Thre;}void InThrTravel(BiThreTree *Thre) /*中序遍历二叉树*/{BiThreTree *p;p=Thre->lchild;while(p!=Thre) /*指针回指向头结点时结束*/ {while(p->LTag==Link)p=p->lchild;printf("%4c",p->data);while(p->RTag==Thread&&p->rchild!=Thre){p=p->rchild;printf("%4c",p->data);}p=p->rchild;}}void main(){BiThreTree *T,*Thre;printf(“PreOrder Create Binary Tree:\n”);T=CreateTree();Thre=InOrderThrTree(T);printf(“InOrder Traverse Binary Tree:\n”);InThrTravel(Thre);system("pause");}【调试举例】（1）建立二叉树时，按先序遍历方式输入：“ABD##EH##I##CF##G##”，其中“#”表示空指针。
（2）建立的二叉树为：AB CD E F GH I（3）程序输出为中序遍历线索化二叉树的结果：DBHEIAFCG已知A、B和C为三个递增有序的线性表，现要求对A表作如下操作：删除那些既在B表中出现又在C表中出现的元素。
【实验步骤】1.试对顺序表编写实现上述操作的算法并上机编写代码，要求算法尽可能高效。
在实验报告中分析你的算法的时间复杂度。
2.A表中要删除的元素实际上就是在三个表中都存在的元素。
注意这三个线性表都是递增有序的线性表！可以利用这一性质减少对线性表“扫描”的趟数。
3.改用单链表作为存储结构编写算法，请释放A表中无用的结点空间，并上机编程实现。
【算法思想】先从B和C中找出共有元素same，再从A中从当前位置开始，凡小于same的元素均保留，等于same的就跳过，大于same时就再找下一个same。
【顺序存储结构算法描述】void SqList_Delete(SqList&A, SqList B, SqList C){i=0;j=0;m=0;/*i指示A中元素原来的位置，m为移动后的位置*/while(i<A.length&&j<B.length&&k<C.length){if(B.elem[j]<C.elem[k]) j++;else if(B.elem[j]>C.elem[k])k++;else{same= B.elem[j];/*找到了相同元素same*/while(B.elem[j]==same)j++;while(C.elem[k])==same)k++;/*j,k后移到新的元素*/while(i<A.length&&A.elem[i]<same)A.elem[m++]=A.elem[i++];/*需要保留的元素移动到新位置*/while( i<A.length&&A.elem[i]==same)i++;}/*else*/}/*while*/while(i<A.length)A.elem[m++]=A.elem[i++];/*A的剩余元素重新存储*/A.length=m;}/*SqList_Delete*/【顺序存储结构参考程序】#include<stdio.h>main(){#define N 3/*宏定义,代表数组维数*/#define M 4#define T 5int i,j,k,r,m,same;/*定义变量分别指向数组a,b,c*/int a[N],b[M],c[T];printf(“please input numbers:\n”);for (i=0;i<N;i++) scanf("%d",&a[i]);for (j=0;j<M;j++) scanf("%d",&b[j]);for (k=0;k<T;k++) scanf("%d",&c[k]);i=0;j=0;m=0;k=0;/*分别赋值为0，即指向数组的第一元素*/ while(i<N&&j<M&&k<T){if(b[j]<c[k])j++;else if(b[j]>c[k]) k++;else{same=b[j];while(b[j]==same)j++;while(c[k]==same)k++;while(i<N&&a[i]<same)a[m++]=a[i++];while(i<N&&a[i]==same) i++;}}while(i<N)a[m++]=a[i++];printf("a[%d]={",m);/*输出删除元素后的数组a/*for (r=0;r<m-1;r++)printf("%d,",a[r]);printf("%d",a[m-1]);printf("}\n");return;}【程序调试】程序运行是屏幕显示：please input numbers: 此时输入三组测试数据，数据间用空格隔开：2 3 4回车3 4 5 6 回车4 5 6 7 8 回车程序输出结果：a[3]={2,3}，即删除了数组a中即在b和c中都出现的元素。
【单链表存储结构参考程序】# include <stdio.h># include <stdlib.h>Typedef struct LNode{int data;struct LNode *next;}Lnode,*LinkList;/*定义链表节点的结构*/void main ( ){/*功能：建立单链表A,B,C，并且删除A中均在B和C中出现的数据。
