(C/C++)基础数据结构（二叉树,图）以及基础算法------下篇
本文的主要内容是讲解基础的一些数据结构，如：二叉树,图。以及与其有关的一些基础算法（二叉树的便利,图的最短路径），这里使用的语言为C++。
在讲解数据结构之前，这里先对一些常用的值使用宏进行定义，方便后续的程序编写
#define MAXSIZE 65536 #define MAX_GRAPH_LENGTH 16 #define ElemType int #define VertexType char首先要讲解的数据结构是二叉树，二叉树是一种树形结构，使用二叉链表进行存储，其形状大致如下图所示：
如上图，一颗二叉树有且只有一个根节点，每个节点有两个子节点，分别为左孩节点和右孩节点，左孩节点与右孩节点本身也是一颗二叉树，可见，二叉树的定义是递归的。
接下来我们来看如何使用C++语言描述二叉树的节点，这里我们使用链式表示法，其代码如下：
typedef struct BTNode { ElemType data; BTNode * lchild,//左孩子指针 * rchild;//右孩子指针 }BTNode, * BTree;这里的BTNode类型就是一颗二叉树的节点，而BTree类型就是一个指向这种节点的指针，只需要知道BTNode是节点，BTree是指针即可。而lchild与rchild是当前节点指向其左右孩子的指针，通过指针将把子节点的地址记录到父节点当中，形成一颗二叉树。
接下来是二叉树的四大便利：先根遍历（DLR）、中根遍历（LDR）、后根遍历（LRD）、层次遍历。先根遍历，中根便利，后根便利都分为递归式与非递归式，下面提供示例代码的时候都会把递归式和非递归式都提供出来。一般来说递归式更加简单和常见，非递归式要借助栈的数据结构，相对来说更加复杂，但是非递归式我们也要掌握。
先根遍历（DLR）
void _DLR(BTree T)//递归式先根遍历二叉树 { if (T == NULL)return; visit(T);//访问根节点 _DLR(T->lchild);//递归式便利左子树 _DLR(T->rchild);//递归式便利右子树 } //-------------------------------------------------------------------// void DLR(BTree T)//非递归式先根遍历二叉树 { if (T == NULL)return; BTree p = T;//工作指针 BTStack S;//定义栈 Init(S);//初始化栈 visit(p);//访问根节点 Push(S, p);//根节点进栈 int tag = 0;//记录进出栈操作，0为出栈，1为入栈 while (!IsEmpty(S)) { if (tag == 0 && p->lchild)//上一次为入栈操作,并且入栈元素有左子树 { p = p->lchild; visit(p);//访问左子树 Push(S, p);//左子树进栈 } else//当前元素没有左子树了 { Pop(S, p);//出栈 tag = 1; if (p->rchild)//如果出栈元素有右子树 { p = p->rchild;// visit(p); Push(S, p); tag = 0; } } } cout << endl; }非递归式遍历相对复杂，与之前学习的栈这种数据结构有所联动，需要读者精通前面的知识，在学习后面的知识的时候会轻松很多。
中根便利
void _LDR(BTree T)//递归式 { if (T == NULL)return; _LDR(T->lchild); visit(T); _LDR(T->rchild); } //====================================================================// void LDR(BTree T)//非递归式 { if (T == NULL)return; BTStack S;//声明栈 Init(S);//初始化栈 BTree p = T;//临时指针 Push(S, p);//根节点入栈 while (!IsEmpty(S)) { if (p->lchild)//如果当前节点有左子树，直接入栈即可 { p = p->lchild; Push(S, p); } else// { Pop(S, p);//出栈 visit(p);//访问出栈元素 if (p->rchild)//如果出栈元素有右子树，让出栈元素的右子树入栈 { p = p->rchild; Push(S, p); } } } cout<<endl; }后根便利:
void _LRD(BTree T) { if (T == NULL)return; _LRD(T->lchild); _LRD(T->rchild); visit(T); } //===========================================================// void LRD(BTree T) { if (T == NULL)return; BTStack S; Init(S); BTree p = T;//工作指针 BTree pre = NULL;//上一个访问的元素 int tag = 0;//0表示进栈,1表示退栈 Push(S, p); while (!IsEmpty(S)) { p = GetTop(S);//p为栈顶元素 if (p->lchild && p->lchild != pre&&tag==0)//如果栈顶元素有左子树，并且上一个访问的元素不是左子树，并且上一次的操作是进栈操作 { p = p->lchild; Push(S, p); } else if (p->rchild && p->rchild != pre&&tag==1)//如果栈顶元素有右子树，并且右子树不是上一个访问的节点，并且上一次为出栈操作 { p = p->rchild; Push(S, p); tag = 0; } else//如果栈顶元素没有左右子树 { Pop(S, p);//出栈 visit(p); pre = p;//记录访问节点 tag = 1;//出栈 } } cout << endl; }以上就是二叉树的三大遍历操作，递归式是相对来说比较简单，只需要更改递归函数的调用顺序即可，而非递归式遍历涉及到数据结构栈，这大大增加了非递归算法的理解难度，需要读者耐心观看，耐心理解，或者可以将上述代码直接复制到VS当中，使用调试来理解算法的执行过程，这里不再过多赘述。
二叉树的最后一种遍历方式是层次遍历（LevelReverse），需要使用队列的数据结构，其原理就是：根节点入队列，然后出队列并且访问它，若访问的元素有左孩子，则将它的左孩子入队列，若访问的元素有右孩子，则将它的右孩子入队列（先左后右，这个相对顺序不能改变）。然后继续从队列当中取出一个元素，并且访问它，以此类推，直到队列为空，代码如下：
void LevelReverse(BTree T) { BTQueue Q;//二叉树节点队列 Init(Q);//初始化 BTree p = T;//临时指针 EnQueue(Q, p);//根节点入队 while (!IsEmpty(Q))//当队列不为空的时候 { DeQueue(Q, p);//出队列 visit(p);//访问出队列元素 if (p->lchild)EnQueue(Q, p->lchild);//如果出队列元素有左孩子，则左孩子入队列 if (p->rchild)EnQueue(Q, p->rchild);//如果出队列元素有右孩子，则右孩子入队列 } cout << endl; }这里再提供一些有关于树的常见的一些简单算法：
int CountNode(BTree T)//统计树当中节点数目 { if (T == NULL)return 0; return 1 + CountNode(T->lchild) + CountNode(T->rchild); } int GetTreeHeight(BTree T)//得到树的高度并且返回 { if (T == NULL)return 0; int LHeight = GetTreeHeight(T->lchild);//左子树高度 int RHeight = GetTreeHeight(T->rchild);//右子树高度 return 1 + (LHeight > RHeight ? LHeight : RHeight); } int CountLeaves(BTree T)//计算树的叶子节点数目 { if (T == NULL)return 0; if (T->lchild == NULL && T->rchild == NULL)return 1; return CountLeaves(T->lchild) + CountLeaves(T->rchild); }下面是数据结构当中最难的数据结构图，一般来说，图有两种表示形式，邻接矩阵（Adjacent Martrix）与邻接表（Ajacent List）,下面为代码C++表示：
//=====================================================// typedef struct AMGraph { int arcs[MAX_GRAPH_LENGTH][MAX_GRAPH_LENGTH];//边表 VertexType vetices[MAX_GRAPH_LENGTH];//顶点表 int ArcsNum;//边数 int VertexNum;//顶点数 }; //======================================================// typedef struct ArcNode//边节点 { int val;//当前边所邻接的另一顶点在顶点表当中的下表 ArcNode* next;//下一条边 }ArcNode; typedef struct Vertex { VertexType data; ArcNode* FirstArc;//第一条边 }Vertex,Vertices[MAX_GRAPH_LENGTH];//顶点表 typedef struct ALGraph//邻接表 { Vertices vertices;//顶点表 int ArcsNum, VertexNum;//边数，顶点数 };可以看到邻接矩阵表示法其实就是一个二维数组用于存放边，一个一维数组存放顶点，然后使用两个整形变量用于存放顶点数目和边的数目。
而邻接表看上去稍微复杂一点，其实本质就是一个一维数组用于存放顶点，而顶点在存储了本身的值val之外，还有一个指针指向第一个以当前节点为起点的边节点，而边节点在存放邻接点在顶点表当中的位置之外，还有一个指针指向以当前节点为起点的下一条边的边节点。图示大致是这样的：
0 1 2 3就是顶点数组，而firstedge指针指向的是当前节点的第一条边节点，而边节点除了存储当前节点邻接的节点在顶点表当中的位置外，还存储了当前节点的下一条边节点的位置，直到没有边节点为止。这里也是稍微难理解一些，需要结合图示，耐心观看。
接下来要介绍的是图的遍历算法，图有两种遍历方式，一种是深度优先遍历DFS，一种是广度优先便利BDS。
DFS算法如下：
//AMGraph void AMDFS(AMGraph G, int start_pos) { bool* IsVisit = (bool*)malloc(G.VertexNum * sizeof(bool));//申请一块空间用于记录顶点是否被访问过 if (IsVisit == NULL)return;//申请内存失败 for (int i = 0; i < G.VertexNum; i++)IsVisit[i] = false;//初始化visit数组 DFS(G, start_pos, IsVisit);//DFS } void DFS(AMGraph G, int start_pos, bool* IsVisit) { visit(G.vetices[start_pos]);//访问当前节点 IsVisit[start_pos] = true;//当前节点已经被访问过 for (int i = 0; i < G.VertexNum; i++) if ( G.arcs[start_pos][i] != 0 && G.arcs[start_pos][i] != MAXSIZE && IsVisit[i] == false)//找寻与当前节点邻接并且没有被访问过的节点 { DFS(G, i,IsVisit);//对找到的节点进行深度优先便利 } } //ALGraph void ALDFS(ALGraph G, int start_pos) { bool* IsVisit = (bool*)malloc(G.VertexNum * sizeof(bool));//申请内存记录每个节点是否被访问过 if (IsVisit == NULL)return;//如果申请失败则直接返回 for (int i = 0; i < G.VertexNum; i++)IsVisit[i] = false;//初始化IsVisit数组 DFS(G, start_pos, IsVisit);//DFS } void DFS(ALGraph G, int start_pos, bool* IsVisit) { visit(G.vertices[start_pos].data);//访问当前元素 IsVisit[start_pos] = true;//标记已访问 ArcNode* p = G.vertices[start_pos].FirstArc;//从第一条边开始 while (p) { if(IsVisit[p->val]==false) DFS(G, p->val, IsVisit);//递归进行DFS p = p->next; } }BFS算法如下（如果你能理解DFS，相信BFS对你来说也不是什么太大的问题，所以下面的代码我不再提供注释，如果觉得不理解，可以复制下来到编译器当中慢慢阅读）：
//邻接矩阵的广度优先便利 void AMBFS(AMGraph G, int start_pos) { bool* IsVisit = (bool*)malloc(G.VertexNum * sizeof(bool)); if (IsVisit == NULL)return; for (int i = 0; i < G.VertexNum; i++)IsVisit[i] = false; Queue Q; Init(Q); BFS(G, start_pos, IsVisit,Q); } void BFS(AMGraph G, int start_pos, bool* IsVisit,Queue &Q) { EnQueue(Q, start_pos); IsVisit[start_pos] = true; while (!IsEmpty(Q)) { int row; DeQueue(Q, row); visit(G.vetices[row]); for (int col = 0; col < G.VertexNum; col++) if ( G.arcs[row][col] != 0 && G.arcs[row][col] != MAXSIZE && IsVisit[col] == false ) { IsVisit[col] = true; EnQueue(Q, col); } } } //-----------------------------------------------------------// //邻接表的广度优先便利 void ALBFS(ALGraph G, int start_pos) { bool* IsVisit = (bool*)malloc(G.VertexNum * sizeof(bool)); if (IsVisit == NULL)return; for (int i = 0; i < G.VertexNum; i++)IsVisit[i] = false; Queue Q; Init(Q); BFS(G, start_pos, IsVisit, Q); } void BFS(ALGraph G, int start_pos, bool* IsVisit, Queue& Q) { EnQueue(Q, start_pos); IsVisit[start_pos] = true; while (!IsEmpty(Q)) { int output; DeQueue(Q, output); visit(G.vertices[output].data); ArcNode* p = G.vertices[output].FirstArc; while (p) { if (IsVisit[p->val] == false) { IsVisit[p->val] = true; EnQueue(Q, p->val); } p = p->next; } } }上述代码可能难以理解，建议读者直接复制代码到编译器当中，并且自己构建一张图，使用该算法进行调试遍历，通过调试遍历来理解算法的实现过程。
下面介绍的是树的查找算法，如：最小生成树的算法，最短路径算法。
最小生成树，就是在一张有n个顶点的无向图当中选出n-1条边，让任意两个点之间都有路径，并且边的权值之和最小。这样选出来的边与原来的顶点就构成了一颗最小生成树。从一张图当中获得最小生成树最常用的算法就是Prim算法。
Prim算法代码如下：
void Prim(AMGraph G, AMGraph &minCreateTree) { minCreateTree.ArcsNum = G.VertexNum-1;//找n-1条边 minCreateTree.VertexNum = G.VertexNum;//有n个顶点 bool* IsVisit = (bool*)malloc(G.VertexNum * sizeof(bool)); for (int i = 0; i < G.VertexNum; i++) { minCreateTree.vetices[i] = G.vetices[i];//复制顶点表 IsVisit[i] = false; } IsVisit[0] = true;//从第一个顶点开始找 for (int i = 0; i < G.VertexNum - 1; i++)//要找顶点数-1次 { int dst = -1;//新边的终点 int MinArc = MAXSIZE;//边的权值 int src= -1;//新边的起点 for (int j = 0; j < G.VertexNum; j++) if (IsVisit[j] == true) for (int k = 0; k < G.VertexNum; k++) if ( IsVisit[k] == false && G.arcs[j][k] != 0 && G.arcs[j][k] != MAXSIZE ) { if (MinArc > G.arcs[j][k]) { MinArc = G.arcs[j][k]; dst = k; src = j; } } IsVisit[dst] = true;//把顶点加入最小树 minCreateTree.arcs[src][dst] = MinArc; } }最短路径就是在图当中找到两点之间的最短距离，常用的算法是迪杰斯特拉和弗洛伊德算法
迪杰斯特拉是找单源最短路径的算法，其算法如下：
int Dijkstra(AMGraph G, int src, int dst) { bool* IsVisit = (bool*)malloc(G.VertexNum * sizeof(bool));//记录每个顶点是否访问过 int* Dist = (int*)malloc(G.VertexNum * sizeof(int));//原点到每个顶点的最短距离 int* parent = (int*)malloc(G.VertexNum * sizeof(int));//从原点到该顶点的前驱顶点位置 for (int i = 0; i < G.VertexNum; i++) { IsVisit[i] = false; Dist[i] = MAXSIZE; parent[i] = i; }//初始化各数组 //访问源顶点 IsVisit[src] = true; Dist[src] = 0; for (int i = 0; i < G.VertexNum; i++) if (G.arcs[src][i] != 0 && G.arcs[src][i] != MAXSIZE) { Dist[i] = G.arcs[src][i]; parent[i] = src; }//把源顶点加入已经访问的顶点 for (int i = 0; i < G.VertexNum - 1; i++)//依次访问剩下的顶点 { int min_dist_point = -1; int min_dist = MAXSIZE;//到原点的最小距离 for (int j = 0; j < G.VertexNum; j++) { if (IsVisit[j] == false&&Dist[j]<min_dist)//找到距离原点最短，并且没有访问过的节点min_dist_point { min_dist = Dist[j]; min_dist_point = j; } }//找到与原点最近，并且没有访问过的顶点 IsVisit[min_dist_point] = true;//访问该节点 for (int j = 0; j < G.VertexNum; j++) { if (Dist[min_dist_point] + G.arcs[min_dist_point][j] < Dist[j]) { Dist[j] = Dist[min_dist_point] + G.arcs[min_dist_point][j]; parent[j] = min_dist_point; } } } return Dist[dst]; }Floyd算法是一种暴力算法，其核心思想是任意找三个点A,B,C，看AB+BC的距离是否小于AC的距离，如果是，则AC的距离更新为AB+BC，这种算法及其暴力，其代码如下：
int Floyd(AMGraph G, int src, int dst) { for (int i = 0; i < G.VertexNum; i++) for (int j = 0; j < G.VertexNum; j++) for (int k = 0; k < G.VertexNum; k++) if (G.arcs[i][j] + G.arcs[i][k] < G.arcs[j][k]) G.arcs[j][k]=G.arcs[i][j] + G.arcs[i][k] ; return G.arcs[src][dst]; }以上就是有关于二叉树和图这两种数据结构的定义和有关算法，难度较大，需要耐心观看，同时也需要一定的基础认识。
好了，以上就是本文的全部内容了，如果你喜欢的话不妨给我点一个大大的赞~~~您的支持和鼓励，就是我学习和更新的最大动力，这里是站长李蔚，一个专注于C/C++的新人程序员，如果想学习更多有关于C/C++的知识或者是数据结构有关的知识，不妨关注我一下，虽然本人正在备考研究生，但是也会常更新哟！！感谢您的观看！
