- 博客(5)
- 收藏
- 关注
RSS订阅原创 图的DFS(深度优先)算法的非递归方式(使用邻接矩阵存储)
首先明白，要用非递归算法模拟递归，必须要使用到栈来实现这个过程。算法的主题实际上就是尽可能深的往图内部走，遇到可以往下走的顶点就先进栈，然后下一次循环再pop出来，进行访问。void DFS_Non_RC(AGraph& G, int v){ int w; //存储当前访问节点的临时变量 InitStack(S); //初始化栈 for(i = 0;i<G.vexnum; i++) visit[i] = false; //初始化标记数组 Push(S,v); visit
2020-09-20 22:07:26
1829
3
原创 判断一个无向图图是否是一棵树（判断是否是无环连通图）
首先理解无环连通图的概念：①无环连通图一定只有n-1条边②图中任意两个点均有可将其连通的边根据这两点概念就可以写出算法，算法必须满足两点：①可以统计得到一个图是否连通②一个图中边的个数代码部分：int visited[MAXNUM];//主算法入口bool isTree(Graph& G){ for(i=1;i<G.vexnum;i++) visited[i] = false; //初始化记录已访问顶点的数组 int Vnum = 0, Enum = 0; //用来记
2020-09-20 17:44:21
3258
原创 二叉树非递归先序中序遍历
先序遍历首先先序遍历规律是：根左右根节点必定是第一个访问的结点，齐次，以根节点的左孩子为根节点的子树，必定也是先访问根节点。得到结论：如果当前结点不为空则对其访问并无脑进栈（这个结论对中序遍历也可用，只是访问结点的操作不同而已）代码：void PreOrder(BiTree t){ Stack S;//定义一个栈 InitStack(S);//初始化栈 BiNode *p = t;//p是用来记录当前访问到的结点 //栈当前不为空或者当前访问结点不为空时，继续循环 while(P!=NU
2020-08-14 23:52:06
303
原创 递归判断二叉树是否是平衡二叉树的算法
代码讲解：https://www.bilibili.com/video/BV1Ga4y1J7hx/平衡二叉树的要点：①左子树平衡②右子树平衡③左右子树高度差绝对值不超过1掌握这三个要点就可以开始写递归程序的出入口出口①：空树，则高度为0，平衡因子为1出口②：只有根节点，高度为1，平衡因子为1出口③：递归完左右子树以后，得到左右子树的平衡因子，判断平衡因子是否都为1（即都平衡，都平衡则以当前节点为根的树都平衡），把当前树的高度保存在h变量中，结束这一层的递归算法。入口①：递归左子树入口②：
2020-08-12 12:12:29
952
原创 二叉树非递归后序遍历算法(C语言)
二叉树非递归后序遍历算法(C语言)二叉树后序遍历的规律：左右根后序非递归遍历中，访问根（子根）结点有两种情况①：遍历完左子树，需要遍历右子树，需要从栈中访问最顶上的根（子根）结点从而得到右子树的指针。②遍历完右子树，需要访问根（子根）结点。基于这个特性，我们需要区分，到底这个根结点，是访问完了左子树还是右子树，所以需要添加一个变量帮助辨认。void Postorder(BiTree T){ Stack S; //用于记录根和字根结点 InitStack(S);//初始化栈 BiNode
2020-07-23 16:17:55
3406
2
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人