数据结构

文章目录

• 一、基本数据结构
• 二、线型表

• 2.1、链表的类别
• 2.2、链表操作

• 2.2.1、单链表操作
• 2.2.2、双链表操作

• 2.3、顺序表和链表的比较
• 2.4、栈
• 2.5、队列

• 三、树和二叉树

• 3.1、树的定义
• 3.1、树的一些基本术语和概念
• 3.2、树的性质
• 3.3、树的存储结构

• 3.3.1、父节点表示法
• 3.3.2、孩子表示法
• 3.3.3、孩子兄弟表示法

• 3.4、二叉树

• 3.4.1、二叉树的定义
• 3.4.2、几种特殊的二叉树

• 3.4.2.1、斜树
• 3.4.2.2、满二叉树
• 3.4.2.3、完全二叉树
• 3.4.2.4、二叉排序树
• 3.4.2.3、平衡二叉树

• 3.4.3、二叉树的性质
• 3.4.4、二叉树的存储结构

• 3.4.4.1、顺序存储结构
• 3.4.4.2、链式存储结构

• 3.4.5、二叉树的递归遍历

• 3.4.5.1、先序遍历
• 3.4.5.2、中序遍历
• 3.4.5.3、后序遍历

• 3.4.6、二叉树的非递归遍历

• 3.4.6.1、中序遍历的非递归算法
• 3.4.6.2、先序遍历的非递归算法
• 3.4.6.2、后序遍历的非递归算法

• 3.4.7、二叉树的层序遍历
• 3.4.8、由遍历序列构造二叉树

• 3.5、线索二叉树

• 3.5.1、线索二叉树概念
• 3.5.2、线索二叉树的结构实现
• 3.5.3、二叉树的线索化

• 3.5.3.1、中序线索二叉树
• 3.5.3.2、先序和后序线索二叉树

• 3.6、树、森林和二叉树的转化

• 3.6.1、树转换为二叉树
• 3.6.2、森林转换为二叉树

• 3.7、树和森林的遍历

• 3.7.1、树的遍历
• 3.7.2、森林的遍历

• 3.8、树与二叉树的应用

• 3.8.1、二叉排序树

• 3.8.1.1、定义
• 3.8.1.2、二叉排序树的常见操作
• 3.8.1.3、二叉排序树小结

• 3.8.2、平衡二叉树

• 3.8.2.1、定义
• 3.8.2.2、平衡二叉树的查找
• 3.8.2.3、平衡二叉树的插入

• 3.8.3、红黑树
• 3.8.4、哈夫曼树和哈夫曼编码

• 3.8.3.1、哈夫曼树的定义和原理
• 3.8.3.2、哈夫曼树的构造
• 3.8.3.3、哈夫曼编码

• 四、图

• 4.1、图的定义
• 4.2、图的基本概念和术语

一、基本数据结构

二、线型表

2.1、链表的类别

2.2、链表操作

2.2.1、单链表操作

2.2.2、双链表操作

2.3、顺序表和链表的比较

2.4、栈

2.5、队列

三、树和二叉树

3.1、树的定义

树是n（n>=0）个结点的有限集。当n=0时，称为空树；

在任意一颗非空树中应满足：

• 有且仅有一个特定的称为根的结点；
• 当n>1时，其余节点可分为m（m>0）个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树。

显然，树的定义是递归的，即在树的定义中又用到了自身，树是一种递归的数据结构。树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：

• 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。
• 树中所有结点可以有零个或多个后继。

3.1、树的一些基本术语和概念

• 祖先：从根结点到叶子结点的路径上的任意结点，都是叶子结点的祖先；例如结点B是结点K的祖先，结点K是结点B的子孙；
• 父结点：从根结点到叶子结点的路径上，最接近的结点称为父节点，例如结点E是结点K的父节点；
• 子节点：结点K是结点E的子节点；
• 兄弟结点：有相同父节点的结点称为兄弟结点，例如结点K和结点L有相同的父节点E，所以结点K和结点L是兄弟结点；
• 结点的度：一个结点的孩子个数称为结点的度，例如结点E的度为2，结点H的度为1，结点K的度为0；
• 树的度：树中结点的最大度数称为树的度，例如上面这棵树的度为3；
• 分支结点：度大于0的结点称为分支结点（又称为非终端结点），在分支结点中，每个结点的分支数就是该结点的度；
• 叶子结点：度为0（没有子节点）的结点称为叶子结点（又称为终端结点）；
• 结点的深度：从根节点开始自顶向下逐层累加；
• 结点的高度：从叶子结点开始自底向上逐层累加；
• 结点的层次：从树根开始定义，根结点为第1层，它的子节点为第2层，依此类推；
• 树的高度（或深度）：书中结点的最大层数，例如上面这棵树的高度为4；
• 有序树和无序树：树中结点的各子树从左到右是有次序的，不能互换，称该树为有序树，否则称为无序树；假设上面这棵树为有序树,若将子结点位置互换，则变成一棵不同的树；
• 路径和路径长度：树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数，例如A–>K的路径为【A - B - E - K】，路径长度为3；
• 森林：森林是m（m>=0）棵互不相交的树的集合。森林的概念与树的概念十分相近，因为只要把树的根结点删去就成了森林。反之，只要给m棵独立的树加上一个结点，并把这m棵树作为该结点的子树，则森林就变成了树。

3.2、树的性质

• 树中的结点数等于所有结点的度数加1；
• 度为m的树中第i层至多有m^i-1个结点（i>=1）;
• 高度为h的m叉树至多有（m^h - 1）/（m - 1）个结点；
• 具有n个结点的m叉树d的最小高度为[log_m^(n(m-1)+1)] ；

3.3、树的存储结构

在介绍以下三种存储结构的过程中，都以下面这棵树为例；

3.3.1、父节点表示法

我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。也就是说，每个结点除了知道自已是谁以外，还知道它的父节点在哪里。

其中data是数据域，存储结点的数据信息。而parent是指针域，存储该结点的双亲在数组中的下标

/*树的双亲表示法结点结构定义*/
#define MAX_TREE_SIZE 100
typedef int TElemType;	//树结点的数据类型，目前暂定为整型
/*结点结构*/
typedef struct PTNode{
	TElemType data;	//结点数据
	int parent;	//父节点位置
}PTNode;
/*树结构*/
typedef struct{
	PTNode nodes[MAX_TREE_SIZE];	//结点数组
	int r, n;	//根的位置和结点数
}PTree;

这样的存储结构，我们可以根据结点的parent指针很容易找到它的父结点，所用的时间复杂度为0(1)，直到parent为-1时，表示找到了树结点的根。

可如果我们要知道结点的孩子是什么，对不起，请遍历整个结构才行。

3.3.2、孩子表示法

把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中，如图所示：

为此，设计两种结点结构，一个是孩子链表的孩子结点：

• child：是数据域，用来存储某个结点在表头数组中的下标；
• next：是指针域，用来存储指向某结点的下一个孩子结点的指针；

另一个是表头数组的表头结点：

• data：是数据域，存储某结点的数据信息；
• firstchild：是头指针域，存储该结点的孩子链表的头指针；

/*树的孩子表示法结构定义*/
#define MAX_TREE_SIZE 100
/*孩子结点*/
typedef struct CTNode{
	int child;
	struct CTNode *next;
}*ChildPtr;
/*表头结点*/
typedef struct{
	TElemType data;
	ChildPtr firstchild;
}CTBox;
/*树结构*/
typedef struct{
	CTBox nodes[MAX_TREE_SIZE];	//结点数组
	int r, n;	//根的位置和结点数
}

这样的结构对于我们要查找某个结点的某个孩子，或者找某个结点的兄弟，只需要查找这个结点的孩子单链表即可。对于遍历整棵树也是很方便的，对头结点的数组循环即可。

但是，这也存在着问题，我如何知道某个结点的双亲是谁呢?比较麻烦，需要整棵树遍历才行；

3.3.3、孩子兄弟表示法

刚才我们分别从双亲的角度和从孩子的角度研究树的存储结构，如果我们从树结点的兄弟的角度又会如何呢?当然，对于树这样的层级结构来说，只研究结点的兄弟是不行的，我们观察后发现，任意一棵树， 它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。 因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

结点的结构如下：

• data：是数据域；
• firstchild： 为指针域，存储该结点的第一个孩子结点的存储地址；
• rightsib：是指针域，存储该结点的右兄弟结点的存储地址；

这种表示法，给查找某个结点的某个孩子带来了方便

/*树的孩子兄弟表示法结构定义*/
typedef struct CSNode{
	TElemtype data;
	struct CSNode *firstchild, *rightsib;
} CSNode, *CSTree;

于是通过这种结构，我们就把原来的树变成了这个样子：

这不就是个二叉树么？

没错，其实这个表示法的最大好处就是它把一棵复杂的树变成了一棵二叉树。

接下来，我们详细介绍二叉树

3.4、二叉树

3.4.1、二叉树的定义

二叉树是另一种树形结构，其特点是每个结点至多只有两棵子树( 即二叉树中不存在度大于2的结点)，并且二叉树的子树有左右之分，其次序不能任意颠倒。

与树相似，二叉树也以递归的形式定义。二叉树是n (n≥0) 个结点的有限集合:

• 或者为空二叉树，即n=0。
• 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

二叉树是有序树，若将其左、右子树颠倒，则成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。

二叉树的5种基本形态如图所示：

3.4.2、几种特殊的二叉树

3.4.2.1、斜树

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

3.4.2.2、满二叉树

• 一棵高度为h，且含有2^h − 1个结点的二叉树称为满二叉树，即树中的每层都含有最多的结点。
• 满二叉树的叶子结点都集中在二叉树的最下一层，并且除叶子结点之外的每个结点度数均为2 。
• 可以对满二叉树按层序编号: 约定编号从根结点(根结点编号为1)起，自上而下，自左向右。这样，每个结点对应一个编号,对于编号为i的结点，若有双亲，则其双亲为i/2,若有左孩子，则左孩子为2i;若有右孩子，则右孩子为2i + 1。

3.4.2.3、完全二叉树

• 高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树；
• 若i <= n/2，则结点i为分支结点，否则为叶子结点；
• 叶子结点只可能在层次最大的两层上出现。对于最大层次中的叶子结点，都依次排列在该层最左边的位置上；
• 若有度为1的结点，则只可能有一个，且该结点只有左孩子而无右孩子(重要特征)；
• 按层序编号后，一旦出现某结点(编号为i)为叶子结点或只有左孩子，则编号大于i的结点均为叶子结点；
• 若n为奇数，则每个分支结点都有左孩子和右孩子;
• 若n 为偶数，则编号最大的分支结点(编号为n / 2)只有左孩子，没有右孩子，其余分支结点左、右孩子都有；

3.4.2.4、二叉排序树

• 左子树上所有结点的关键字均小于根结点的关键字；
• 右子树上的所有结点的关键字均大于根结点的关键字；
• 左子树和右子树又各是一棵二叉排序树；

3.4.2.3、平衡二叉树

• 树上任一结点的左子树和右子树的深度之差不超过1

3.4.3、二叉树的性质

• 任意一棵树，若结点数量为n，则边的数量为n-1；
• 非空二叉树的叶子结点数等于度为2的结点数加1，即n₀ = n₂ + 1;
• 非空二叉树上第K层至多有2^k-1个结点（K>=1）；
• 高度为h的二叉树至多有2^h-1个结点（h>=1）;
• 对完全二叉树按从上到下，从左到右的顺序依次编号1、2、…、n，则有以下关系：

• i>1时，结点i的父节点编号为i/2，即当i为偶数时，它是双亲的左孩子；当i为奇数时，它是双亲的右孩子；
• 当2i<=n时，结点i的左孩子编号为2i，否则无左孩子；
• 当2i+1<=n时，结点i的有孩子编号为2i+1，否则无右孩子；
• 结点i所在层次（深度）为{log₂ⁿ} + 1；

• 具有n个（n>0）结点的完全二叉树的高度为{log₂ⁿ}+1；

3.4.4、二叉树的存储结构

3.4.4.1、顺序存储结构

二叉树的顺序存储是指用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i ii的结点元素存储在一维数组下标为i − 1 i-1i−1的分量中。

依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映结点之间的逻辑关系，这样既能最大可能地节省存储空间，又能利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。

但对于一般的二叉树，为了让数组下标能反映二叉树中结点之间的逻辑关系，只能添加一些并不存在的空结点，让其每个结点与完全二叉树上的结点相对照，再存储到一维数组的相应分量中。然而，在最坏情况下，一个高度为h且只有h个结点的单支树却需要占据近2 h − 1个存储单元。

二叉树的顺序存储结构如图所示，其中0表示并不存在的空结点：

3.4.4.2、链式存储结构

既然顺序存储适用性不强，我们就要考虑链式存储结构。二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。

• data是数据域；
• lchild 和rchild：都是指针域，分别存放指向左孩子和右孩子的指针；

/*二叉树的二叉链表结点构造定义*/
/*结点结构*/
typedef struct BiTNode{
	TElemType data;	//结点数据
	struct BiTNode *lchild, *rchild;	//左右孩子指针
} BiTNode, *BiTree;

容易验证，在含有n个结点的二叉链表中，含有n + 1个空链域。

3.4.5、二叉树的递归遍历

3.4.5.1、先序遍历

若二叉树为空，则什么也不做，否则，
1)访问根结点;
2)先序遍历左子树;
3)先序遍历右子树。

先序遍历：A、B、D、G、H、C、E、I、F

对应的递归算法如下：

void PreOrder(BiTree T){
	if(T != NULL){
		visit(T);	//访问根节点
		PreOrder(T->lchild);	//递归遍历左子树
		PreOrder(T->rchild);	//递归遍历右子树
	}
}

3.4.5.2、中序遍历

若二叉树为空，则什么也不做，否则，
1)中序遍历左子树;
2)访问根结点;
3)中序遍历右子树。

中序遍历：G、D、H、B、A、E、I、C、F

对应的递归算法如下:

void InOrder(BiTree T){
	if(T != NULL){
		InOrder(T->lchild);	//递归遍历左子树
		visit(T);	//访问根结点
		InOrder(T->rchild);	//递归遍历右子树
	}
}

3.4.5.3、后序遍历

若二叉树为空，则什么也不做，否则，
1)后序遍历左子树;
2)后序遍历右子树;
3)访问根结点。

后序遍历：G、H、D、B、I、E、F、C、A

对应的递归算法如下:

void PostOrder(BiTree T){
	if(T != NULL){
		PostOrder(T->lchild);	//递归遍历左子树
		PostOrder(T->rchild);	//递归遍历右子树
		visit(T);	//访问根结点
	}
}

三种遍历算法中,递归遍历左、右子树的顺序都是固定的，只是访问根结点的顺序不同。不管采用哪种遍历算法，每个结点都访问一次且仅访问一次，故时间复杂度都是O(n)。在递归遍历中，递归工作栈的栈深恰好为树的深度，所以在最坏情况下，二叉树是有n个结点且深度为n的单支树，遍历算法的空间复杂度为O(n)。

3.4.6、二叉树的非递归遍历

以下图的树为例：

3.4.6.1、中序遍历的非递归算法

借助栈，我们来分析中序遍历的访问过程：

• 沿着根的左孩子，依次入栈，直到左孩子为空，说明已找到可以输出的结点，此时栈内元素依次为ABD；
• 栈顶元素出栈并访问；若其右孩子为空，继续执行步骤2；若其右孩子不空,将右子树转执行步骤1；

栈顶D出栈并访问，它是中序序列的第一个结点; D右孩子为空，栈顶B出栈并访问; B右孩子不空，将其右孩子E入栈，E左孩子为空，栈顶E出栈并访问; E右孩子为空，栈顶A出栈并访问; A右孩子不空，将其右孩子C入栈，C左孩子为空，栈顶C出栈并访问。由此得到中序序列【D、B、E、A、C】

中序遍历的非递归算法如下：

void InOrder2(BiTree T){
	InitStack(S);	//初始化栈S
	BiTree p = T;	//p是遍历指针
	while(p || !IsEmpty(S)){	//栈不空或p不空时循环
		if(p){
			Push(S, p);	//当前节点入栈
			p = p->lchild;	//左孩子不空，一直向左走
		}else{
			Pop(S, p);	//栈顶元素出栈
			visit(p);	//访问出栈结点
			p = p->rchild;	//向右子树走，p赋值为当前结点的右孩子
		}
	}
}

3.4.6.2、先序遍历的非递归算法

先序遍历和中序遍历的基本思想是类似的，只需把访问结点操作放在入栈操作的前面。

先序遍历的非递归算法如下:

void PreOrder2(BiTree T){
	InitStack(S);	//初始化栈S
	BiTree p = T;	//p是遍历指针
	while(p || !IsEmpty(S)){	//栈不空或p不空时循环
		if(p){
			visit(p);	//访问出栈结点
			Push(S, p);	//当前节点入栈
			p = p->lchild;	//左孩子不空，一直向左走
		}else{
			Pop(S, p);	//栈顶元素出栈
			p = p->rchild;	//向右子树走，p赋值为当前结点的右孩子
		}
	}
}

3.4.6.2、后序遍历的非递归算法

后序遍历的非递归实现是三种遍历方法中最难的。因为在后序遍历中，要保证左孩了和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。

算法思想:后序非递归遍历二叉树是先访问左子树，再访问右子树，最后访问根结点。

• 沿着根的左孩子，依次入栈，直到左孩子为空。此时栈内元素依次为ABD；
• 读栈顶元素:若其右孩子不空且未被访问过，将右子树转执行①；否则，栈顶元素出栈并访问；

栈顶D的右孩子为空，出栈并访问，它是后序序列的第一个结点;栈顶B的右孩子不空且未被访问过，E入栈，栈顶E的左右孩子均为空，出栈并访问;栈顶B的右孩子不空但已被访问，B出栈并访问;栈项A的右孩子不空且未被访问过，C入栈,栈项C的左右孩子均为空，出栈并访问;栈顶A的右孩子不空但已被访问，A出栈并访问。由此得到后序序列【D、E、B、C、A】

在上述思想的第②步中，必须分清返回时是从左子树返回的还是从右子树返回的，因此设定一个辅助指针r,指向最近访问过的结点。也可在结点中增加一个标志域，记录是否已被访问；

后序遍历的非递归算法如下：

void PostOrder2(BiTree T){
	InitStack(S);
	p = T;
	r = NULL;
	while(p || !IsEmpty(S)){
		if(p){	//走到最左边
			push(S, p);
			p = p->lchild;
		}else{	//向右
			GetTop(S, p);	//读栈顶元素（非出栈）
			//若右子树存在，且未被访问过
			if(p->rchild && p->rchild != r){
				p = p->rchild;	//转向右
				push(S, p);	//压入栈
				p = p->lchild;	//再走到最左
			}else{	//否则，弹出结点并访问
				pop(S, p);	//将结点弹出
				visit(p->data);	//访问该结点
				r = p;	//记录最近访问过的结点
				p = NULL;
			}
		}
	}
}

3.4.7、二叉树的层序遍历

下图为二叉树的层次遍历，即按照箭头所指方向，按照1,2,3, 4的层次顺序，对二叉树中的各个结点进行访问。

要进行层次遍历，需要借助一个队列。先将二叉树根结点入队，然后出队，访问出队结点，若它有左子树，则将左子树根结点入队;若它有右子树，则将右子树根结点入队。然后出队，访问出队结…如此反复，直至队列为空。

二叉树的层序遍历算法如下：

void LevelOrder(BiTree T){
	InitQueue(Q);	//初始化辅助队列
	BiTree p;
	EnQueue(Q, T);	//将根节点入队
	while(!IsEmpty(Q)){	//队列不空则循环
		DeQueue(Q, p);	//队头结点出队
		visit(p);	//访问出队结点
		if(p->lchild != NULL){
			EnQueue(Q, p->lchild);	//左子树不空，则左子树根节点入队
		}
		if(p->rchild != NULL){
			EnQueue(Q, p->rchild);	//右子树不空，则右子树根节点入队
		}
	}
}

3.4.8、由遍历序列构造二叉树

1、由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树

• 在先序遍历序列中，第一个结点一定是二叉树的根结点；
• 而在中序遍历中，根结点必然将中序序列分割成两个子序列；
• 前一个子序列是根结点的左子树的中序序列，后一个子序列是根结点的右子树的中序序列；
• 根据这两个子序列，在先序序列中找到对应的左子序列和右子序列；
• 在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点；
• 如此递归地进行下去,便能唯一地确定这棵二叉树

以下图的树为例：

先序遍历：A、B、D、E、C

中序遍历：D、B、E、A、C

• 根据先序遍历序列，可以确定A是根结点；
• 根据中序遍历序列，可以确定D、B、E属于左子树，C输入右子树；
• D、B、E属于左子树，再根据先序遍历序列，可以确定B是左子树的根节点；
• 确定B是左子树的根节点之后，再根据中序遍历序列，可以确定D输入左子树，E输入右子树；
• 然后二叉树就还原出来了；

2、由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树
因为后序序列的最后一个结点就如同先序序列的第一个结点，可以将中序序列分割成两个子序列，然后采用类似的方法递归地进行划分，进而得到一棵二叉树。

3、由二叉树的层序序列和中序序列也可以唯一地确定一棵二叉树

4、注意：若只知道二叉树的先序序列和后序序列，则无法唯一确定一棵二叉树

3.5、线索二叉树

3.5.1、线索二叉树概念

遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序列，使得该序列中的每个结点(第一个和最后一个结点除外)都有一个直接前驱和直接后继。

传统的二叉链表存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继。

首先我们要来看看这空指针有多少个呢?对于一个有n个结点的二叉链表，每个结点有指向左右孩子的两个指针域，所以一共是2n个指针域。而n个结点的二叉树一共有n-1 条分支线数，也就是说，其实是存在2n- (n-1) =n+1个空指针域。

由此设想能否利用这些空指针来存放指向其前驱或后继的指针?这样就可以像遍历单链表那样方便地遍历二叉树。引入线索二叉树正是为了加快查找结点前驱和后继的速度；

我们把这种指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树(Threaded Binary Tree)。

其结点结构如下所示：

• ltag为0时指向该结点的左孩子，为1时指向该结点的前驱。
• rtag为0时指向该结点的右孩子，为1时指向该结点的后继。

因此对于上图的二叉链表图可以修改为下图的样子：

3.5.2、线索二叉树的结构实现

typedef struct ThreadNode{
	ElemType data;	//数据元素
	struct ThreadNode *lchild, *rchild;	//左、右孩子指针
	int ltag, rtag;	//左、右线索标志
}ThreadNode, *ThreadTree;

3.5.3、二叉树的线索化

二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。

前驱或后继的信息只有在遍历时才能得到，因此线索化的实质就是遍历一次二叉树，线索化的过程就是在遍历的过程中修改空指针的过程。

3.5.3.1、中序线索二叉树

以中序线索二叉树的建立为例。附设指针pre指向刚刚访问过的结点，指针p指向正在访问的结点即pre指向p的前驱。

在中序遍历的过程中，检查p的左指针是否为空，若为空就将它指向pre；检查pre的右指针是否为空，若为空就将它指向p，如下图所示。

BDAEC

通过中序遍历对二叉树线索化的递归算法如下：

void InThread(ThreadTree p, ThreadTree pre){
	if(p != NULL){
		InThread(p->lchild, pre);	//递归，线索化左子树
		if(p->lchild == NULL){	//左子树为空，建立前驱线索
			p->lchild = pre;
			p->ltag = 1;
		}
		if(pre != NULL && pre->rchild == NULL){
			pre->rchild = p;	//建立前驱结点的后继线索
			pre->rtag = 1;
		}
		pre = p;	//标记当前结点成为刚刚访问过的结点
		InThread(p->rchild, pre);	//递归，线索化右子树
	}
}

你会发现，除了中间的代码，和二叉树中序遍历的递归代码几乎完全一样。只不过将本是访问结点的功能改成了线索化的功能。

通过中序遍历建立中序线索二叉树的主过程算法如下：

void CreateInThread(ThreadTree T){
	ThreadTree pre = NULL;
	if(T != NULL){
		InThread(T, pre);	//线索化二叉树
		pre->rchild = NULL;	//处理遍历的最后一个结点
		pre->rtag = 1;
	}
}

为了方便,可以在二叉树的线索链表上也添加一个头结点，令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最后一个结点；令二叉树中序序列中的第一个结点的lchild域指针和最后一个结点的rchild域指针均指向头结点。这好比为二叉树建立了一个双向线索链表，方便从前往后或从后往前对线索二叉树进行遍历，如下图所示。

遍历的代码如下：

/*T指向头结点，头结点左链lchild指向根结点，头结点右链rchild指向中序遍
的最后一个结点。中序遍历二叉线索链表表示的二叉树T*/
void InOrderTraverse_Thr(BiThrTree T){
	BiThrTree p;
	p = T->lchild;	//p指向根结点
	//空树或遍历结束时，p==T（最后一个结点指向根结点）
	while(p != T){	
		//当ltag==0时循环到中序序列第一个结点
		while(p->ltag == 0){	
			p = p->lchild;	//p指向p的左子树
		}
		visit(p);	//访问该结点
		//后继线索为1且不是指向头指针
		while(p->rtag == 1 && p->rchild != T){	
			p = p->rchild;	//p指向p的后继
			visit(p);	//访问该节点
		}
		//p进至其右子树根，开始对右子树根进行遍历
		p = p->rchild;	
	}
}

从这段代码也可以看出，它等于是一个链表的扫描,所以时间复杂度为0(n)。

由于它充分利用了空指针域的空间(这等于节省了空间)，又保证了创建时的一次遍历就可以终生受用前驱后继的信息(这意味着节省了时间)。所以在实际问题中，如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。

3.5.3.2、先序和后序线索二叉树

上面给出了建立中序线索二叉树的代码，建立先序线索二叉树和后序线索二叉树的代码类似，只需变动线索化改造的代码段与调用线索化左右子树递归函数的位置。

3.6、树、森林和二叉树的转化

3.6.1、树转换为二叉树

树转换为二义树的规则：每个结点左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟，这个规则又称“左孩子右兄弟”。由于根结点没有兄弟，所以对应的二叉树没有右子树。

树转换成二叉树的画法：

• 在兄弟结点之间加一连线；
• 对每个结点，只保留它与第一个孩子的连线，而与其他孩子的连线全部抹掉；
• 以树根为轴心，顺时针旋转45°；

3.6.2、森林转换为二叉树

森林是由若干棵树组成的，所以完全可以理解为,森林中的每一棵树都是兄弟，可以按照兄弟的处理办法来操作。

森林转换成二叉树的画法：

• 将森林中的每棵树转换成相应的二叉树；
• 每棵树的根也可视为兄弟关系，在每棵树的根之间加一根连线；
• 以第一棵树的根为轴心顺时针旋转45°；

3.7、树和森林的遍历

3.7.1、树的遍历

树的遍历是指用某种方式访问树中的每个结点，且仅访问一次。主要有两种方式：

• 先根遍历。若树非空，先访问根结点，再依次遍历根结点的每棵子树，遍历子树时仍遵循先根后子树的规则。其遍历序列与这棵树相应二叉树的先序序列相同。
• 后根遍历。若树非空，先依次遍历根结点的每棵子树，再访问根结点，遍历子树时仍遵循先子树后根的规则。其遍历序列与这棵树相应二叉树的中序序列相同。

下图的树的先根遍历序列为【A、B、E、F、C、D、G】,后根遍历序列为【E、F、B、C、G、D、A】。

另外，树也有层次遍历，与二叉树的层次遍历思想基本相同，即按层序依次访问各结点。

3.7.2、森林的遍历

按照森林和树相互递归的定义，可得到森林的两种遍历方法。
1、先序遍历森林。若森林为非空，则按如下规则进行遍历：

• 访问森林中第一棵树的根结点；
• 先序遍历第一棵树中根结点的子树森林；
• 先序遍历除去第一棵树之后剩余的树构成的森林；

2、后序遍历森林。森林为非空时，按如下规则进行遍历：

• 后序遍历森林中第一棵树的根结点的子树森林；
• 访问第一棵树的根结点：
• 后序遍历除去第一棵树之后剩余的树构成的森林：

例如下图森林的先序遍历序列为【A、B、C、D、E、F、G、H、I】，后序遍历序列为【B、C、D、A、F、E、H、I、G】

3.8、树与二叉树的应用

3.8.1、二叉排序树

3.8.1.1、定义

二叉排序树(也称二叉查找树)：或者是一棵空树，或者是具有下列特性的二叉树：

• 若左子树非空，则左子树上所有结点的值均小于根结点的值；
• 若右子树非空，则右子树上所有结点的值均大于根结点的值；
• 左、右子树也分别是一棵二叉排序树；

根据二叉排序树的定义，左子树结点值<根结点值<右子树结点值，所以对二叉排序树进行中序遍历，可以得到一个递增的有序序列。例如，下图所示二叉排序树的中序遍历序列为【1、2、3、4、6、8】

3.8.1.2、二叉排序树的常见操作

/*二叉树的二叉链表结点结构定义*/
typedef struct BiTNode
{
	int data;	//结点数据
	struct BiTNode *lchild, *rchild;	//左右孩子指针
} BiTNode, *BiTree;

（1）查找操作

/*
递归查找二叉排序树T中是否存在key
指针f指向T的双亲，其初始调用值为NULL
若查找成功，则指针p指向该数据元素结点，并返回TRUE
否则指针p指向查找路径上访问的最后一个结点并返回FALSE
*/
bool SearchBST(BiTree T, int key, BiTree f, BiTree *p){
	if(!T){
		*p = f;
		return FALSE;
	}else if(key == T->data){
		//查找成功
		*p = T;
		return TRUE;
	}else if(key < T->data){
		return SearchBST(T->lchild, key, T, p);	//在左子树继续查找
	}else{
		return SearchBST(T->rchild, key, T, p);	//在右子树继续查找
	}
}

（2）插入操作
有了二叉排序树的查找函数，那么所谓的二叉排序树的插入，其实也就是将关键字放到树中的合适位置而已。

/*
当二叉排序树T中不存在关键字等于key的数据元素时
插入key并返回TRUE，否则返回FALSE
*/
bool InsertBST(BiTree *T, int key){
	BiTree p, s;
	if(!SearchBST(*T, key, NULL, &p)){
		//查找不成功
		s = (BiTree)malloc(sizeof(BiTNode));
		s->data = key;
		s->lchild = s->rchild = NULL;
		if(!p){
			*T = s;	//插入s为新的根节点
		}else if(key < p->data){
			p->lchild = s;	//插入s为左孩子
		}else{
			p->rchild = s;	//插入s为右孩子
		}
		return TRUE;
		}else{
			return FALSE;	//树种已有关键字相同的结点，不再插入
		}
}

有了二叉排序树的插入代码，我们要实现二叉排序树的构建就非常容易了，几个例子：

int i;
int a[10] = {62, 88, 58, 47, 35, 73, 51, 99, 37, 93};
BiTree T = NULL;
for(i = 0; i<10; i++){
	InsertBST(&T, a[i]);
}

上面的代码就可以创建一棵下图这样的树：

（3）删除操作
二叉排序树的查找和插入都很简单，但是删除操作就要复杂一些，此时要删除的结点有三种情况：

• 叶子结点；
• 仅有左或右子树的结点；
• 左右子树都有的结点；

前两种情况都很简单，第一种只需删除该结点不需要做其他操作；第二种删除后需让被删除结点的直接后继接替它的位置；复杂就复杂在第三种，此时我们需要遍历得到被删除结点的直接前驱或者直接后继来接替它的位置，然后再删除

/*
若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点，
并返回TRUE;否则返回FALSE
*/
bool DeleteBST(BiTree *T, int key){
	if(!*T){
		return FALSE; 
	}else{
		if(key == (*T)->data){
			//找到关键字等于key的数据元素
			return Delete(T);
		}else if(key < (*T) -> data){
			return DeleteBST((*T) -> lchild, key);
		}else{
			return DeleteBST((*T) -> rchild, key);
		}
	}
}

/*从二叉排序树中删除结点p，并重接它的左或右子树。*/
bool Delete(BiTree *p){
	BiTree q, s;
	if(p->rchild == NULL){
		//右子树为空则只需重接它的左子树
		q = *p;
		*p = (*p)->lchild;
		free(q);
	}else if((*p)->lchild == NULL){
		//左子树为空则只需重接它的右子树
		q = *p;
		*p = (*p)->rchild;
		free(q);
	}else{
		//左右子树均不空
		q = *p;
		s = (*p)->lchild;	//先转左
		while(s->rchild){//然后向右到尽头，找待删结点的前驱
			q = s;
			s = s->rchild;
		}
		//此时s指向被删结点的直接前驱，p指向s的父母节点
		p->data = s->data;	//被删除结点的值替换成它的直接前驱的值
		if(q != *p){
			q->rchild = s->lchild;	//重接q的右子树
		}else{
			q->lchild = s->lchild;	//重接q的左子树
		}
		pree(s);
	}
	return TRUE;
}

3.8.1.3、二叉排序树小结

二叉排序树的优点明显，插入删除的时间性能比较好。而对于二叉排序树的查找，走的就是从根结点到要查找的结点的路径，其比较次数等于给定值的结点在二叉排序树的层数。极端情况，最少为1次，即根结点就是要找的结点，最多也不会超过树的深度。也就是说，二叉排序树的查找性能取决于二叉排序树的形状。可问题就在于，二叉排序树的形状是不确定的。

例如{ 62 , 88 , 58 , 47 , 35 , 73 , 51 , 99 , 37 , 93 } {62,88,58,47,35,73,51,99,37,93}{62,88,58,47,35,73,51,99,37,93}这样的数组，我们可以构建如下左图的二叉排序树。但如果数组元素的次序是从小到大有序，如{35,37,47,51,58,62,73,88,93,99},则二叉排序树就成了极端的右斜树，如下面右图的二叉排序树：

也就是说，我们希望二叉排序树是比较平衡的，即其深度与完全二叉树相同，那么查找的时间复杂也就为O ( l o g n ) O(logn)O(logn)，近似于折半查找。

不平衡的最坏情况就是像上面右图的斜树，查找时间复杂度为O ( n ) O(n)O(n)，这等同于顺序查找。
因此，如果我们希望对一个集合按二叉排序树查找，最好是把它构建成一棵平衡的二叉排序树

3.8.2、平衡二叉树

3.8.2.1、定义

平衡二叉树是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。

它是一种高度平衡的二叉排序树。它要么是一棵空树， 要么它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。

我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF (Balance Factor) ， 那么平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

3.8.2.2、平衡二叉树的查找

在平衡二叉树上进行查找的过程与二叉排序树的相同。因此，在查找过程中，与给定值进行比较的关键字个数不超过树的深度。假设以n_h表示深度为h的平衡树中含有的最少结点数。显然，有n₀ = 0 , n₁ = 1 , n₂ = 2，并且有n_h = n~h − 1~ + n~h − 2~ + 1；可以证明，含有n个结点的平衡二叉树的最大深度为O ( l o g ₂ⁿ ) ，因此平衡二叉树的平均查找长度为O ( l o g ₂ⁿ )

3.8.2.3、平衡二叉树的插入

二叉排序树保证平衡的基本思想如下：每当在二叉排序树中插入(或删除)一个结点时，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A，再对以A为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。

注意:每次调整的对象都是最小不平衡子树，即以插入路径上离插入结点最近的平衡因子的绝对值大于1的结点作为根的子树。下图中的虚线框内为最小不平衡子树。

平衡二叉树的插入过程的前半部分与二叉排序树相同，但在新结点插入后，若造成查找路径上的某个结点不再平衡，则需要做出相应的调整。可将调整的规律归纳为下列4种情况：（1）LL平衡旋转(右单旋转)

由于在结点A的左孩子（B）的左子树（BL）上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡；

需要一次向右的旋转操作：将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树。

（2）RR平衡旋转(左单旋转)

由于在结点A的右孩子B的右子树BR上插入了 新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡；

需要一次向左的旋转操作：将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树。

（3）LR平衡旋转(先左后右双旋转)

由于在A的左孩子(B)的右子树上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡；

需要进行两次旋转操作：先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置（即进行一次RR平衡旋转(左单旋转)），然后再把该C结点向右上旋转提升到A结点的位置（即进行一次LL平衡旋转(右单旋转)）。

（4）RL平衡旋转(先右后左双旋转)

由于在A的右孩子B的左子树上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡;

需要进行两次旋转操作：先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置（即进行一次LL平衡旋转(右单旋转)），然后再把该C结点向左上旋转提升到A结点的位置（即进行一次RR平衡旋转(左单旋转)）。

举例：假设关键字序列为15、3 、 7 、 10 、 9 、 8 ，通过该序列生成平衡二叉树的过程如下图所示：

3.8.3、红黑树

红黑树：是一棵自平衡的二叉排序树，树上的每一个结点都遵循下面的规则：

• 每一个结点都有一个颜色，要么为红色，要么为黑色；
• 树的根结点为黑色；
• 树中不存在两个相邻的红色结点（即红色结点的父结点和孩子结点均不能是红色）；
• 从任意一个结点（包括根结点）到其任何后代 NULL 结点（默认是黑色的）的每条路径都具有相同数量的黑色结点。

• 这就是一颗典型的红黑树，树中的每个结点的颜色要么是黑色，要么是红色；
• 根结点 6 为黑色结点；
• 树中不存在两个相邻的红色结点，比如结点 15 为红色结点，其父亲节点 6 与两个孩子结点就一定是黑色，而不能是红色；
• 从结点到其后代的 NULL结点 的每条路径上具有相同数目的黑色结点，比如根结点 6 到其左子树的 NULL结点 包含三个黑色结点，到其右子树所有的 NULL 结点也包含三个黑色结点；

红黑树的意义

大多数二叉排序树BST的操作（查找、最大值、最小值、插入、删除等等）都是 O(h) 的时间复杂度，h 为树的高度。
但是对于斜树而言（BST极端情况下出现），BST的这些操作的时间复杂度将达到 O(n) 。为了保证BST的所有操作的时间复杂度的上限为 O(logn) ，就要想办法把一颗BST树的高度一直维持在logn，而红黑树就做到了这一点，红黑树的高度始终都维持在logn，n 为树中的顶点数目。

红黑树与平衡二叉树的区别

• 平衡二叉树追求绝对的平衡，平衡二叉树比红黑树更加平衡，但是平衡二叉树在插入和删除的时候也会存在大量的旋转操作，所以当你的应用涉及到频繁的插入和删除操作，切记放弃AVL树，选择性能更好的红黑树；
• 如果你的应用中涉及的插入和删除操作并不频繁，而是查找操作相对更频繁，那么就优先选择 AVL 树进行实现；

3.8.4、哈夫曼树和哈夫曼编码

3.8.3.1、哈夫曼树的定义和原理

• 权：树中结点常常被赋予一个表示某种意义的数值，称为该结点的权；
• 带权路径长度：从树的根到任意结点的路径长度(经过的边数)与该结点上权值的乘积；
• 树的带权路径长度：树中所有叶结点的带权路径长度之和称为该树的带权路径长度，记为：

• w_i：是第i个叶结点所带的权值；
• l_i：是该叶结点到根结点的路径长度；

在含有n个带权叶结点的二叉树中，其中带权路径长度(WPL)最小的二叉树称为哈夫曼树，也称最优二叉树。例如，下图中的3棵二叉树都有4个叶子结点a、b、c、d，分别带权7、5、2、4，它们的带权路径长度分别为：

a. WPL = 7x2 + 5x2 + 2x2 + 4x2 = 36。
b. WPL = 4x2 + 7x3 + 5x3 + 2x1 = 46。
c. WPL = 7x1 + 5x2 + 2x3 + 4x3 = 35。
其中，图c树的WPL最小。可以验证，它恰好为哈夫曼树。

3.8.3.2、哈夫曼树的构造

• 先把有权值的叶子结点按照从大到小（从小到大也可以）的顺序排列成一个有序序列；
• 取最后两个最小权值的结点作为一个新节点的两个子结点，注意相对较小的是左孩子；
• 用第2步构造的新结点替掉它的两个子节点，插入有序序列中，保持从大到小排列；
• 重复步骤2到步骤3，直到根节点出现；

3.8.3.3、哈夫曼编码

赫夫曼当前研究这种最优树的目的是为了解决当年远距离通信(主要是电报)的数据传输的最优化问题。

哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码。

比如我们有一段文字内容为“ BADCADFEED”要网络传输给别人，显然用二进制的数字(0和1)来表示是很自然的想法。我们现在这段文字只有六个字母ABCDEF，那么我们可以用相应的二进制数据表示，如下表所示：

这样按照固定长度编码编码后就是“001000011010000011101100100011”，对方接收时可以按照3位一分来译码。如果一篇文章很长，这样的二进制串也将非常的可怕。而且事实上，不管是英文、中文或是其他语言，字母或汉字的出现频率是不相同的。假设六个字母的频率为A 27,B 8,C 15,D 15,E 30,F 5,合起来正好是

100%。那就意味着，我们完全可以重新按照赫夫曼树来规划它们。

下图左图为构造赫夫曼树的过程的权值显示。右图为将权值左分支改为0，右分支改为1后的赫夫曼树。

这棵哈夫曼树的WPL为:

WPL = 2 ∗ ( 15 + 27 + 30 ) + 3 ∗ 15 + 4 ∗ ( 5 + 8 ) = 241此时，我们对这六个字母用其从树根到叶子所经过路径的0或1来编码，可以得到如下表所示这样的定义。

若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。

我们将文字内容为“ BADCADFEED”再次编码，对比可以看到结果串变小了。

• 原编码二进制串: 000011000011101100100011 (共 30个字符)
• 新编码二进制串: 10100101010111100(共25个字符)

也就是说，我们的数据被压缩了，节约了大约17%的存储或传输成本

注意：0和1究竟是表示左子树还是右子树没有明确规定。左、右孩子结点的顺序是任意的，所以构造出的哈夫曼树并不唯一，但各哈夫曼树的带权路径长度WPL相同且为最优。此外，如有若干权值相同的结点，则构造出的哈夫曼树更可能不同，但WPL必然相同且是最优的

四、图

在线性表中，数据元素之间是被串起来的，仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。

在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关。

图是一种较线性表和树更加复杂的数据结构。在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。

4.1、图的定义

图(Graph)是由顶点的有穷非空集合V ( G )和顶点之间边的集合E ( G )组成，通常表示为: G = ( V , E ) ；

• G 表示个图；
• V 是图G中顶点的集合；
• E是图G中边的集合；
• V = { v 1 , v 2 , . . . , v n } ，则用∣ V ∣ 表示图G中顶点的个数，也称图G 的阶；
• E = { ( u , v ) ∣ u ∈ V , v ∈ V } ，用∣ E ∣表示图G中边的条数。

注意: 线性表可以是空表，树可以是空树，但图不可以是空图。就是说，图中不能一个顶点也没有，图的顶点集V一定非空，但边集E可以为空，此时图中只有顶点而没有边。

4.2、图的基本概念和术语

1、有向图

• 若E是有向边(也称弧)的有限集合时，则图G为有向图
• 弧是顶点的有序对，记为<v, w>，其中v,w是顶点；
• v称为弧尾，w称为弧头，<v,w>称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v；

有向图G₁可以如下表示：

G₁ = (v₁, E₁)
V₁ = {1, 2, 3}
E₁ = {<1, 2>, <2, 1>, <2, 3>}

2、无向图

• 若E是无向边(简称边)的有限集合时，则图G为无向图；
• 边是顶点的无序对，记为(v, w)或(w,v),因为(v,w)=(w,v), 其中v,w是顶点；
• 可以说顶点w和顶点v互为邻接点；
• 边(v, w)依附于顶点w和v，或者说边(v, w)和顶点v, w相关联；

无向图G₂可以如下表示：

G₂ = (v₂, E₂)
V₂ = {1, 2, 3, 4}
E₂ = {<1, 2>, <1, 3>, <1, 4>, <2, 3>, <2, 4>, ❤️, 4>}

3、简单图
一个图G若满足：

• 不存在重复边；
• 不存在顶点到自身的边；

则称图G GG为简单图，上图中G₁ 和G~2`均为简单图。数据结构中仅讨论简单图。

4、多重图
若图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则G为多重图。多重图的定义和简单图是相对的。

5、完全图（也称为简单完全图）

• 对于无向图，|E|的取值范围为0 ~ n(n-1)/2，有n(n-1)/2条边的无向图称为完全图，在完全图中任意两个顶点之间都存在边；
• 对于有向图，|E|的取值范围为0 ~ n(n-1)，有n(n-1)条弧的有向图称为有向完全图，在有向完全图中任意两个顶点之间都存在方向相反的两条弧；

上面的G2是无向完全图，下面的G3是有向完全图；

6、子图
设有两个图G = ( V , E ) 和G ′ = ( V ′ , E ′ ) ， 若V ′是V的子集，且E ′ 是E的子集，则称G ′ 是G的子图。若有满足V ( G ′ ) = V ( G ) 的子图G ′ ，则称其为G的生成子图。上图中G ₃ 为G ₁ 的子图。

注意：并非V和E的任何子集都能构成G的子图，因为这样的子集可能不是图，即E的子集中的某些边关联的顶点可能不在这个V的子集中。

7、连通、连通图和连通分量

• 在无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的；
• 若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图；
• 无向图中的极大连通子图称为连通分量；
• 若一个图有n个顶点，并且边数小于n − 1 ，则此图必是非连通图；

如下图(a)所示， 图G₄有3个连通分量，如图（b）所示：

8、强连通图、强连通分量

• 在有向图中，若从顶点v到顶点w和从顶点w到项点v之间都有路径，则称这两个顶点是强连通的；
• 若图中任何一对顶点都是强连通的，则称此图为强连通图；
• 有向图中的极大强连通子图称为有向图的强连通分量；

注意：强连通图、强连通分量只是针对有向图而言的。一般在无向图中讨论连通性，在有向图中考虑强连通性。

9、生成树、生成森林

• 连通图的生成树是包含图中全部顶点的一个极小连通子图；
• 若图中顶点数为n,则它的生成树含有n − 1条边；
• 对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路；
• 在非连通图中，连通分量的生成树构成了非连通图的生成森林；

图G₂的一个生成树，如下图所示：

10、顶点的度、入度和出度

• 图中每个顶点的度定义：以该顶点为一个端点的边的数目；
• 对于无向图，无向图的全部顶点的度之和等于边数的2倍，因为每条边和两个顶点相关联；
• 对于有向图，顶点v的度分为入度和出度，入度是以顶点v为终点的有向边的数目，而出度是以顶点v为起点的有向边的数目，顶点v的度等于其入度和出度之和；
• 有向图的全部顶点的入度之和与出度之和相等，并且等于边数，这是因为每条有向边都有一个起点和终点；

11、边的权和网
在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带有权值的图称为带权图，也称网。

12、稠密图、稀疏图
边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。一般当图G满足∣E∣ < ∣V∣log∣V∣时，可以将G视为稀疏图。

13、路径、路径长度和回路

• 顶点V_p到V_q之间的一条路径，是指顶点序列；
• 路径上边的数目称为路径长度；
• 第一个顶点和最后一个顶点相同的路径称为回路或环；
• 若有一个图有n个顶点，并且有大于n-1条边，则此图一定有环；

14、简单路径、简单回路

• 在路径序列中，顶点不重复出现的路径称为简单路径；
• 除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路；

15、距离

• 从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离；
• 若从u到v根本不存在路径，则记该距离为无穷( ∞ ) ；

16、有向树

• 一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树