树与图c++

1.树

前言

本文主要介绍的数据结构之树型结构的相关知识，树型数据结构是面试官面试的时候非常喜欢考的一种数据结构，树形结构的遍历也是大厂笔试非常喜欢设置的考点，这些内容都会在本篇文章中进行详细的介绍，并且还会介绍一些常用的算法。

一、树的基本概念

层次结构的数据在现实世界中大量存在。例如，一个国家有若干省，一个省有若干市县，一个市县有若干区乡。又如，一本书包含若干章，一章包含若干节，一节包含若干段。例如，下图是数组的层次关系，这种描述树形数据的形式称为倒置的树形表示法。
在这里插入图片描述

线性数据结构一般不适合用来表示层次数据。为了组织层次数据，需要对树形数据的结构进行研究。

1.1树的定义

在上图1中，我们采用倒置树来描述树状结构。一棵倒置树的顶端是根，根有几个分枝，称为子树，每棵子树再分成几个小分枝，小分枝再分成更小的分枝，每个分枝也都是树，一个结点也是树。由此，我们可以给树下一个递归定义。

树（Tree）是包括n个结点的有限非空集合T，其中，一个特定的结点r称为根（Root），其余结点T-{r}划分成m个互不相交的子集T1，T2，Tm其中，每个子集都是树，称为树根r的子树。

根据树的定义，一个结点的树是仅有根结点的树，这时m=0，这棵树没有子树。

1.2基本术语

图1可以抽象成图2，它形象地反映了树的逻辑结构。下面，参照图2，给出树结构讨论中常用的术语。

树中元素称为结点（Node），如A、B等。

如果某结点到另一结点之间存在着连线，则称此连线为一条边（Edge），如<A,B>、<B,E>等。

如果从某个结点沿着树中的边可到达另一个结点，则称这两个结点间存在一条路径（Path），如结点A到结点J，存在路径{<A,C>，<C,J>}。

如果一个结点有子树，则称该结点为子树的双亲（Parent），子树的根称为该结点的孩子（Child），如结点A是结点B、C、D的双亲，而结点B、C、D是结点A的孩子。具有相同双亲的结点称为兄弟（Sibling），如结点B、C、D是兄弟。

结点拥有的子树数目称为结点的度（Degree），如结点A的度为3，结点D的度为0，结点J的度为0。

度为零的结点称为叶子(Leaf)。

规定根结点的层次为1，树中结点的最大层次称为该树的高度(Hight)，如图2所表示的树的高度为3。

如果树中结点的各子树是从左至右有次序的，则称该树为有序树，否则称为无序树。

二、二叉树

树结构和自然界的树一样，具有各种各样的形态，这样就使我们对树结构的研究比较困难。为此，我们首先研究最为常见的二叉树，以及二叉树的性质、存储结构和运算，然后给出二叉树和一般树之间的转换。

2.1二叉树的定义
二叉树（Binary Tree）是由有限个结点组成的集合，它或者为空集合，或者仅含一个根结点，或者由一个根结点和两棵互不相交的左、右子树组成。

上述定义表明，二叉树有如图3所示的五种基本形态。
在这里插入图片描述

必须指出，树定义与二叉树定义稍有区别。首先，树不能是空树，却可以有空二叉树。其次，一般树的子树的不分次序，而二叉树的子树却分左、右子树，即使在仅有一棵子树的情况下也要指明是左子树还是右子树。最后，一般树中结点的度(子树数目)可以大于2，但二叉树中结点的度均不超过2。

2.2二叉树的性质
若二叉树高为h，树的结点总数为2^h-1，称此二叉树为满二叉树。

h=3，那么结点总数7(包含根节点)

【性质1】高度为h的二叉树的结点总数n<=2^h-1。

这个性质很容易理解：

证明：对于高度为h的满二叉树，其结点总数为

它是高度为h的二叉树结点总数的最大值，故。

对于高度为h的二叉树，如果第1~h-1层构成满二叉树，而第h层的叶子结点严格按从左至右依次排列，称此二叉树为完全二叉树（如图5(a)所示）。

图5 完全二叉树与非完全二叉树

在图5(b)中，双亲结点C仅有右孩子G无左孩子，故它不是完全二叉树。

【性质2】对于含n(n>=1)个结点的完全二叉树(区分满二叉树)，其高度 $h=\lceil log2(n+1) \rceil$ 。

eg：上述图a，n=6，那么

$h = [l o g 2 (6 + 1)] = l o g 2 (8) = 3$

【性质3】对于一棵非空二叉树，如果度为0的结点数为，度为2的结点数为，则

=+1。（即零度结点数总比2度结点数大1）

证设二叉树的结点数为n，度为1的结点数为n1，边数为e，则

$e = n - 1$

$e = 2 \times n 2 + n 1$

$n = n 0 + n 1 + n 2$

边数等于结点数n-1 ，等于2倍的度为2的结点数+度为1的结点数。

画个树的逻辑结构图就很容易看出来。

于是n0=n2+1。

【性质4】对于含个结点的完全二叉树(区分满二叉树)，按从上到下、从左到右的顺序，从0到n-1编号（如图6所示）。对于树中编号为 $i （ 0 =< i <= n - 1 ）$ 的结点，有

（1）如果 $i = 0$ ，则该结点为二叉树的根；

（2）如果 $2_i+1<n$ ，则其左孩子为 $2_i+1$ ，否则不存在左孩子；

（3）结点的双亲为[(i-1)/2]向下取整。(求双亲注意双亲只有一个)

图6 带序号的完全二叉树

2.3二叉树的ADT
ADT BinTree

数据：

0个或有限个结点组成的集合。

运算：

Create()

创建一棵空二叉树或二叉树。

IsEmpty()

若二叉树为空，则返回1，否则返回0。

PreOrder()

前序遍历二叉树。

InOrder()

中序遍历二叉树。

PostOrder()

后序遍历二叉树。

Display():

输出二叉树。

三、二叉树的存储表示

3.1二叉树的数组表示
用一维数组来存储二叉树，首先将二叉树想象成一棵完全二叉树，对于没有左孩子或右孩子的结点，用特殊字符（或数字）替代，再依从上至下、从左至右的次序，依次将结点值存放到一维数组之中。

【例1】：将图7(a)所示的二叉树，用一维字符数组表示。
在这里插入图片描述

解：

首先将图7(a)所示的二叉树，想象成一棵完全二叉树（如图7(b)所示），再用表8-1所示的一维字符型数组存储。

这种表示法的实现程序如下：示法的实现程序如下：

#include <bits/stdc++.h>
using namespace std;
const int MaxSize 64//为了树的显示效果,结点数不超过63,即二叉树高不超过6
//创建二叉树
void Create(char Node[], int& n)
{cout << "按完全二叉树输入结点字符,空字符用替代" << endl;cin >> Node;//计算字符数组含字符个数n = 0;while (Node[n] != '\0')//当Node[n]不等于结束符时n++;
}
//输出二叉树
void Display(char Node[], int n)
{int hight, layer, num; //hight树高,layer树层,num结点编号hight = ceil(log(n + 1) / log(2));//确定完全二叉树高度//求下限接近整数ceil//自然对数 log//求上限接近整数 floorcout << hight << endl;num = 0;//从结点Node[0]开始输出for (layer = 1; layer <= hight; layer++)//输出1层—hight层{	//每层前面空格的输出控制for (int i = 1; i <= pow(2, hight - layer)-1; i++)cout << " ";//每层结点的输出控制for (int j = 1; j <= pow(2, layer - 1); j++, num++){if (Node[num] != '' && Node[num] != '\0')cout << Node[num];//遇到结点,输出结点else if (Node[num] == '')cout << " ";//遇到号,输出空格elsebreak;//遇到结束符,跳出输出//每层结点间空格的输出控制for (int k = 1; k <= pow(2, hight - layer + 1) - 1; k++)cout << " ";}cout << endl;//输完一层,换行}
}
//主函数
int main()
{int n;//完全二叉树所含结点数char Node[MaxSize];//定义字符型的结点数组Create(Node, n);//创建二叉树结点的一维数组cout << "二叉树为" << endl;Display(Node, n);//输出二叉树return 0;
}

程序运行的结果如图8所示：

创建这棵5结点二叉树，用了6颗星号替代缺失的左、右孩子，这显然是这种表示法的一个缺点。

但当二叉树为完全二叉树时，该表示法具有建树简便，输出直观的优点。

3.2二叉树的链表表示
用一维数组表示的二叉树，不便实现二叉树的一些规定运算。因此，二叉树一般采用链表来创建。

链式二叉树结点的逻辑结构如图9所示，其中，data用来存储结点值，*lChild、*rChild分别用来存储左、右孩子的地址。

图9 树节点的逻辑结构
【例2】创建图7(a)所示的链式二叉树。

用链表表示图7(a)，其逻辑结构如图10所示，其中Λ代表NULL。

具体的创建过程如下：

（1）首先创建第4层结点，并用结点指针Kp指向其根结点，如图11所示。

图11
（2）再创建第3层结点，并用结点指针Ep指向其根结点，如图12所示。

图12
（3）再创建第2层结点，并用结点指针Bp、Cp分别指向其根结点，如图13所示。

图13
（4）最后创建第1层结点，并用结点指针Ap指向其根结点，如图14所示。

图14
如果用程序来描述上述过程，其程序如下：

#include<iostream>
using namespace std;
//二叉树结点定义
struct Node
{	char data;//数据域Node *lChild,*rChild;//指针域
};
//二叉树定义
struct BinTree
{	Node *root;
};
//创建二叉树
void Create(BinTree &T,char x,Node *left,Node *right)
{	Node *NewNode;//新结点NewNode=new Node;//为新结点申请内存NewNode->data=x;//为新结点数据域赋值NewNode->lChild=left;//为新结点左指针域赋值NewNode->rChild=right;//为新结点右指针域赋值T.root=NewNode;//让新结点成为该子树根结点
}
//主函数
int main()
{	BinTree K,E,B,C,A;Create(K,'K',NULL,NULL);//创建结点K的子树Create(E,'E',NULL,K.root);//创建结点E的子树Create(B,'B',NULL,E.root);//创建结点B的子树Create(C,'C',NULL,NULL);//创建结点C的子树Create(A,'A',B.root,C.root);//创建结点A的子树return 0;
}

上述链式二叉树的创建过程是，先创建最底层的叶子结点，然后向上逐层创建子树，直至最顶层的根结点。该方法的优点是直观易懂，缺点是无法给出通用程序。一般链式二叉树的创建方法与通用程序如下。

用广义表构建二叉树。

二叉树的广义表表示法

尽管构建二叉树的方法并不复杂，但对于结点多、结构复杂的二叉树，却不易用程序来实现。因此，有必要寻找更具一般性的二叉树的构建方法。

图1所示的二叉树，可以用以下方式重新表示它。

用A(B)表示A有左孩子B，无右孩子；

用B(C,D)表示B有左孩子C，右孩子D；

用C(,E)表示C无左孩子，但有右孩子E；

用D(F,G)表示D有左孩子F，右孩子G。

将它们复合起来，有A(B(C(,E),D(F,G)))。这是一个字符数组，它是上述二叉树的另一种表示法，称这种二叉树的表示法为广义表法。

用广义表来表示二叉树，其具体规定如下：

树的根结点放在最前面。

每个结点的左子树和右子树用逗号隔开。若仅有左子树没有右子树，逗号可省略；若仅有右子树没有左子树，逗号不能省略。

约定，广义表用字符型数组 GenList[] 来存储。

广义表构建二叉树的算法

设结点值均用字母来替代，先建一棵空二叉树T，借助一个简易结点顺序栈 stack ，广义表A(B(C(,E),D(F,G)))创建二叉树的具体过程如下：

（1）读A，创建新结点A，T为空，让T.root=A结点。

（2）读（，让新结点A入栈，置k=1，栈stack状态为：

（3）读B，创建新结点B，因k=1，让栈顶结点A的左指针指向B，即B←A。

（4）读（，让新结点B入栈，置k=1，栈stack状态为：

（5）读C，创建新结点C，因k=1，让栈顶结点B的左指针指向C，即C←B。

（6）读（，让新结点C入栈，置k=1，栈stack状态为：A B C

（7）读，号，置k=2。

（8）读E，创建新结点E，因k=2，让栈顶结点C的右指针指向E，即C→E。

（9）读），栈顶结点C出栈，栈stack状态为：A B

（10）读，号，置k=2。

（11）读D，创建新结点D，因k=2，让栈顶结点B的右指针指向D，即B→D。

（12）读（，让新结点D入栈，置k=1，栈stack状态为：A B D

（13）读F，创建新结点F，因k=1，让栈顶结点D的左指针指向F，即F←D。

（14）读，号，置k=2。

（15）读G，创建新结点G，因k=2，让栈顶结点D的右指针指向G，即D→G。

（16）读），栈顶结点D出栈，栈stack状态为：A B

（17）读），栈顶结点B出栈，栈stack状态为：A

（18）读），栈顶结点A出栈，栈stack状态为：

至此，二叉树创建完毕。

由T.root=A，B←A，C←B，C→E，可构建如下图2所示的二叉树。

图2 二叉树的构建过程1
由B→D，F←D，D→G，可构建如图3所示的二叉树。

图3 二叉树的构建过程2
3. 广义表构建二叉树算法的程序实现

#include<iostream>
using namespace std;
const int MaxSize 100//顺序栈的最大容量
//结点定义
struct Node
{	char data;//数据域Node *lChild,*rChild;//指针域
};
//二叉树定义
struct BinTree
{	Node *root;
};
//创建空二叉树
void Create(BinTree &T)
{	T.root=NULL;
}
//树判空
int IsEmpty(BinTree T)
{	if(T.root==NULL) return 1;else return 0;
}
//广义表创建二叉树
void Create(char GenList[],BinTree &T)
{	Node *stack[MaxSize],*NewNode,*p;//简易结点顺序栈,新结点,探测指针int top=-1;//置栈空int k,i=0;//k=1链接左子树,k=2链接右子树,i广义表字符下标char ch;do{	ch=GenList[i];//读取广义表第i个字符switch(ch){	case '('://读到左括号stack[++top]=NewNode;//新结点入栈k=1;break;case ')'://读到右括号top--;break;//栈顶结点出栈case ','://读到逗号k=2;break;default://读到字符NewNode=new Node;//新结点申请内存NewNode->data=ch;//新结点数据域赋值NewNode->lChild=NULL;//新结点左指针域赋值NewNode->rChild=NULL;//新结点右指针域赋值if(IsEmpty(T))//如果树为空T.root=NewNode;//新结点作为根结点if(k==1){	p=stack[top];//获取栈顶结点p->lChild=NewNode;//让栈顶结点左孩子指向新结点}else if(k==2){p=stack[top];//获取栈顶结点p->rChild=NewNode;//让栈顶结点左孩子指向新结点}}i++;//i增1}while(GenList[i]!='\0');//逐一读完整个广义表
}
//非递归前序遍历算法
void PreOrder(Node *p)
{	Node *stack[MaxSize];// 简易结点顺序栈int top=-1;//置栈空while(p||top!=-1)//当p结点所指非空或栈非空时{	if(p)//如果p所指结点非空{	cout<<p->data;//输出p的值stack[++top]=p;//p所指结点入栈p=p->lChild;//p向左下移}else//如果p结点所指结点为空{	p=stack[top--];//p指向栈顶结点,栈顶结点出栈p=p->rChild;//p向右下移}}
}
//非递归中序遍历算法
void InOrder(Node *p)
{	Node *stack[MaxSize];//简易结点顺序栈int top=-1;//置栈空while(p||top!=-1)//当p结点所指非空或栈非空时{	if(p)//如果p所指结点非空{	stack[++top]=p;//p所指结点入栈p=p->lChild;//p向左下移}else//如果p所指结点为空{	p=stack[top--];//p指向栈顶结点,栈顶结点出栈cout<<p->data;//输出p的值p=p->rChild;//p向右下移}}
}
//主函数
int main()
{	char GenList[]="A(B(C(,E),D(F,G)))";//定义广义表BinTree T;//定义二叉树Create(T);//创建空二叉树Create(GenList,T); //创建二叉树cout<<"前序遍历为 "; PreOrder(T.root); cout<<endl;cout<<"中序遍历为 "; InOrder(T.root); cout<<endl;return 0;
}

程序运行的结果如图4所示。

图4
四、二叉树的遍历
欲在屏幕上形象地输出链式二叉树是一件困难的事，一般采用输出它的三个线性序列VLR、LVR和LRV的方式，来解决这一问题。

VLR称为前序（PreOrder）遍历序列，它是按先树根，再左子树，后右子树的次序，输出二叉树的结点值。

LVR称为中序（InOrder）遍历序列，它是按先左子树，再树根，后右子树的次序，输出二叉树的结点值。

LRV称为后序（PostOrder）遍历序列，它是按先左子树，再右子树，后树根的次序，输出二叉树的结点值。

所谓前序、中序和后序遍历，是相对于根结点位置而言的。例如，在中序遍历中，根结点在中间；而前序遍历是根结点在前面，后序遍历是根结点在后面。三种遍历方式一定是先左子树后右子树。

4.1前序遍历
前序遍历的次序为：树根—左子树—右子树，即从根结点开始处理，根结点处理完后往左子树走，直到无法前进再处理右子树。

图10 链式二叉树的逻辑结构
【例2】的前序遍历为ABEKC，前序遍历的递归算法如下：

void PreOrder(Node *p)
{	if(p!=NULL){	cout<<p->data;//访问树根PreOrder(p->lChild);//遍历左子树PreOrder(p->rChild); //遍历右子树}
}

4.2中序遍历
中序遍历的次序为：左子树—树根—右子树，即沿树的左子树一直往下，直到无法前进时后退到双亲结点，而后再沿右子树一直往下。如果右子树也走完了就退回上层的左结点，重复左、中、右的顺序遍历。

【例2】的中序遍历为BEKAC，中序遍历的递归算法如下：

void InOrder(Node *p)
{	if(p!=NULL){	InOrder(p->lChild); //遍历左子树cout<<p->data; //访问树根InOrder(p->rChild);//遍历右子树}
}

【例2】的后序遍历为KEBCA，后序遍历的递归算法如下：

void PostOrder(Node *p)
{	if(p!=NULL){	PostOrder(p->lChild);//遍历左子树PostOrder(p->rChild); //遍历右子树cout<<p->data; //访问树根}
}

#include<iostream>
using namespace std;
//二叉树结点定义
struct Node
{char data;//数据域Node* lChild, * rChild;//指针域
};
//二叉树定义
struct BinTree
{Node* root;
};
//创建二叉树
void Create(BinTree& T, char x, Node* left, Node* right)
{Node* NewNode;//新结点NewNode = new Node;//新结点申请内存NewNode->data = x;//新结点数据域赋值NewNode->lChild = left;//新结点左指针域赋值NewNode->rChild = right;//新结点右指针域赋值T.root = NewNode;//让新结点成为该子树根结点
}
//前序遍历
void PreOrder(Node* p)
{if (p != NULL){cout << p->data;//访问树根PreOrder(p->lChild);//遍历左子树PreOrder(p->rChild); //遍历右子树}if (p == NULL){cout << "*";//输出空的节点，更清楚的理解PreOrder的调用过程}
}
//中序遍历
void InOrder(Node* p)
{if (p != NULL){InOrder(p->lChild); //遍历左子树cout << p->data; //访问树根InOrder(p->rChild);//遍历右子树}if (p == NULL){cout << "*";//输出空的节点，更清楚的理解PreOrder的调用过程}
}
//后序遍历
void PostOrder(Node* p)
{if (p != NULL){PostOrder(p->lChild);//遍历左子树PostOrder(p->rChild); //遍历右子树cout << p->data; //访问树根}if (p == NULL){cout << "*";//输出空的节点，更清楚的理解PreOrder的调用过程}
}
//主函数
int main()
{BinTree K, E, B, C, A;Create(K, 'K', NULL, NULL);//创建结点K的子树Create(E, 'E', NULL, K.root);//创建结点E的子树Create(B, 'B', NULL, E.root);//创建结点B的子树Create(C, 'C', NULL, NULL);//创建结点C的子树Create(A, 'A', B.root, C.root);//创建结点A的子树cout << "前序遍历为 "; PreOrder(A.root); cout << endl;cout << "中序遍历为 "; InOrder(A.root); cout << endl;cout << "后序遍历为 "; PostOrder(A.root); cout << endl;return 0;
}

程序运行的结果如图16所示：
在这里插入图片描述

【定理1】任意n(n>0)个不同结点的二叉树，都可由其前序遍历序列和中序遍历序列唯一确定。

【例4】画出前序遍历ABEKC，中序遍历BEKAC所确定的二叉树。

（1）由前序遍历ABEKC，A为根结点；由中序遍历BEKAC，BEK为左子树，C为右子树；其对应的二叉树如图17所示。
在这里插入图片描述

（2）对于左子树，由前序遍历BEK，B为根结点；由中序遍历BEK，EK为右子树，其对应的二叉树如图18所示。
在这里插入图片描述

（3）对于右子树，由前序遍历EK，E为根结点；由中序遍历EK，K为右子树，其对应的二叉树如图19所示。
在这里插入图片描述

五、常用二叉树
5.1排序二叉树
先给出排序二叉树的定义。

设二叉树的所有结点值互异，排序二叉树或者是一棵空树，或者是满足以下条件的树：

（1）若左子树不空，则左子树上所有结点的值均小于根结点的值；（左小于根）

（2）若右子树不空，则右子树上所有结点的值均大于根结点的值；（右大于根）

（3）左、右子树也分别是排序二叉树。(递归定义)

排序二叉树定义是由递归方式给出的，据此定义，可给出排序二叉树的创建方法：

首次输入的数据作为此二叉树的根，其后输入的数据与根进行比较，小于树根的放置到左子树，大于树根的放置到右子树。

【例5】依次输入数据32，25，16，35，27，创建一棵排序二叉树。

排序二叉树的创建过程如图20所示：

图20 排序二叉树的创建过程

创建排序二叉树的程序如下：

#include <bits/stdc++.h>
using namespace std;
//二叉树结点定义
struct Node
{	int data;//数据域Node *lChild,*rChild;//指针域
};
//二叉树定义
struct BinTree
{	Node *root;
};
//创建空二叉树
void Create(BinTree &T)
{	T.root=NULL;
}//判空
int IsEmpty(BinTree T)
{	if(T.root==NULL) return 1;else return 0;
}
//创建排序二叉树
void Create(BinTree &T,int x)
{	Node *NewNode,*p;NewNode=new Node; //新结点申请内存NewNode->data=x;//新结点数据域赋值NewNode->lChild=NULL;//新结点左指针域赋值NewNode->rChild=NULL;//新结点右指针域赋值int flag=0;//新结点入树标识,flag=0表示未入树if(IsEmpty(T))//如果二叉树为空{T.root=NewNode;}else//如果二叉树非空{	p=T.root;//探测指针指向根结点while(!flag)//当新结点未入树时//理解江老师说的兑奖劵问题{	if(x<p->data)//如果新结点的值小于双亲结点的值{ //进入左子树if(p->lChild==NULL)//如果左子树为空{	p->lChild=NewNode;//新结点成为左子树flag=1;//新结点入树}else//如果左子树非空{p=p->lChild;//探测指针向左下移}}else//如果新结点的值大于双亲结点的值{  //进入右子树if(p->rChild==NULL)//如果右子树为空{	p->rChild=NewNode;//新结点成为右子树flag=1;//新结点入树}else{p=p->rChild;//探测指针向右下移}}}}
}
//前序遍历
void PreOrder(Node *p)
{	if(p!=NULL){	cout<<p->data<<" ";//访问树根PreOrder(p->lChild);//遍历左子树PreOrder(p->rChild);//遍历右子树}
}
//中序遍历
void InOrder(Node *p)
{	if(p!=NULL){	InOrder(p->lChild);//遍历左子树cout<<p->data<<" ";//访问树根InOrder(p->rChild);//遍历右子树}
}
//主函数
int main()
{	BinTree T;//定义二叉树Create(T);//创建空二叉树char c;int x;printf("输入二叉树结点值(用空格隔开,回车结束)\n");while(scanf("%d%c",&x,&c))//while键盘输入的第一种用法{Create (T,x);//创建排序二叉树if(c=='\n') break;}cout<<"前序遍历为 "; PreOrder(T.root); cout<<endl;cout<<"中序遍历为 "; InOrder(T.root); cout<<endl;return 0;
}