采用非递归深度优先遍历算法

深度优先遍历的算法深度优先遍历（Depth-First Search，DFS）是一种用来遍历或树或图的算法。

它以一个起始节点开始，沿着路径尽可能深地，直到到达最深处或无法继续为止，然后回溯到上一个节点，继续其他路径。

DFS通过栈来实现，每次访问一个节点时，将其标记为已访问，并将其相邻的未访问节点压入栈中。

然后从栈中弹出节点，重复这个过程，直到栈为空为止。

1.创建一个栈，用来存储待访问的节点。

2.将起始节点标记为已访问，并将其压入栈中。

3.当栈不为空时，执行以下步骤：-弹出栈顶节点，并输出该节点的值。

-将该节点的未访问的相邻节点标记为已访问，并将其压入栈中。

4.重复步骤3，直到栈为空为止。

-深度优先遍历是一种先序遍历，即先访问节点本身，然后访问其子节点。

-深度优先遍历可以用来求解连通图、查找路径等问题。

-深度优先遍历的时间复杂度为O(V+E)，其中V为节点数，E为边数。

1.求解连通图：深度优先遍历可以用来判断一个图是否连通，即从一个节点是否能够访问到所有其他节点。

2.查找路径：深度优先遍历可以找到两个节点之间的路径。

当遇到目标节点时，即可停止遍历，返回路径结果。

3.拓扑排序：深度优先遍历可以进行拓扑排序，即将有依赖关系的任务按一定的顺序排列。

深度优先遍历的实现可以通过递归或迭代方式来完成。

递归方式更加简洁，但在处理大规模图时可能导致栈溢出。

迭代方式则可以采用栈来避免栈溢出问题。

无论是递归方式还是迭代方式，其核心思想都是通过访问节点的相邻节点来进行深入，直至遍历完整个图或树的节点。

总而言之，深度优先遍历是一种常用的图遍历算法，它以一种深入优先的方式遍历路径。

在实际应用中，深度优先遍历可以用来求解连通图、查找路径和拓扑排序等问题，是图算法中的重要工具之一。

图的深度优先遍历（DFS）c++⾮递归实现深搜算法对于程序员来讲是必会的基础，不仅要会，更要熟练。

ACM竞赛中，深搜也牢牢占据着很重要的⼀部分。

本⽂⽤显式栈（⾮递归）实现了图的深度优先遍历，希望⼤家可以相互学习。

　栈实现的基本思路是将⼀个节点所有未被访问的“邻居”（即“⼀层邻居节点”）踹⼊栈中“待⽤”，然后围绕顶部节点猛攻，每个节点被访问后被踹出。

读者可以⾃⼰画图分析⼀下，难度并不⼤。

代码写的⽐较随意，仅供参考。

~#include <iostream>#include <stack>using namespace std;#define MaxNode 20#define MAX 2000#define StartNode 1int map[MaxNode+1][MaxNode+1];void dfs_stack(int start, int n){int visited[MaxNode],s_top;for(int i = 0;i <= MaxNode; i++){visited[i] = 0;}visited[start] = 1;stack <int> s;cout<<start<<"";for(int i = 1; i <= n; i++){if(map[i][start] == 1 && !visited[i] ){visited[i] = 1;s.push(i);}}while(!s.empty()){s_top = s.top();visited[s_top] = 1;cout<<s_top<<"";s.pop();for(int i = 1; i <= n; i++){if(map[i][s_top] == 1 && !visited[i] ){visited[i] = 1;s.push(i);}}}}int main(int argc, const char * argv[]) {int num_edge,num_node;int x,y;cout<<"Input number of nodes and edges >"<<endl;cin>>num_node>>num_edge;for(int i =0;i<num_node;i++){for(int j=0;j<num_node;j++){map[i][j] = 0;}}for(int i = 1; i <= num_edge; i++){cin>>x>>y;map[x][y] = map[y][x] = 1;}dfs_stack(StartNode, num_node);return0;}。

深度优先和⼴度优先⽐较区别：1）⼆叉树的深度优先遍历的⾮递归的通⽤做法是采⽤栈，⼴度优先遍历的⾮递归的通⽤做法是采⽤队列。

2）深度优先遍历：对每⼀个可能的分⽀路径深⼊到不能再深⼊为⽌，⽽且每个结点只能访问⼀次。

要特别注意的是，⼆叉树的深度优先遍历⽐较特殊，可以细分为先序遍历、中序遍历、后序遍历。

具体说明如下：先序遍历：对任⼀⼦树，先访问根，然后遍历其左⼦树，最后遍历其右⼦树。

中序遍历：对任⼀⼦树，先遍历其左⼦树，然后访问根，最后遍历其右⼦树。

后序遍历：对任⼀⼦树，先遍历其左⼦树，然后遍历其右⼦树，最后访问根。

⼴度优先遍历：⼜叫层次遍历，从上往下对每⼀层依次访问，在每⼀层中，从左往右（也可以从右往左）访问结点，访问完⼀层就进⼊下⼀层，直到没有结点可以访问为⽌。

3）深度优先搜素算法：不全部保留结点，占⽤空间少；有回溯操作(即有⼊栈、出栈操作)，运⾏速度慢。

⼴度优先搜索算法：保留全部结点，占⽤空间⼤；⽆回溯操作(即⽆⼊栈、出栈操作)，运⾏速度快。

通常深度优先搜索法不全部保留结点，扩展完的结点从数据库中弹出删去，这样，⼀般在数据库中存储的结点数就是深度值，因此它占⽤空间较少。

所以，当搜索树的结点较多，⽤其它⽅法易产⽣内存溢出时，深度优先搜索不失为⼀种有效的求解⽅法。

　⼴度优先搜索算法，⼀般需存储产⽣的所有结点，占⽤的存储空间要⽐深度优先搜索⼤得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。

但⼴度优先搜索法⼀般⽆回溯操作，即⼊栈和出栈的操作，所以运⾏速度⽐深度优先搜索要快些深度优先：前序遍历：35,20,15,16,29,28,30,40,50,45,55中序遍历：15,16,20,28,29,30,35,40,45,50,55后序遍历：16,15,28,30,29,20,45,55,50,40,35⼴度优先遍历：35 20 40 15 29 50 16 28 30 45 55代码：package www.hhy;import java.beans.beancontext.BeanContextChild;import java.util.*;class Binarytree {class TreeNode{int value;TreeNode left;TreeNode right;public TreeNode(int value) {this.value = value;}}//⽤递归创建⼆叉树public int i = 0;TreeNode creatTesttree(String s){TreeNode root = null;if (s.charAt(i)!='#') {root = new TreeNode(s.charAt(i));i++;root.left = creatTesttree(s);root.right = creatTesttree(s);}else{i++;}return root;}//⼆叉树的前序遍历递归void binaryTreePrevOrder(TreeNode root){if(root==null){return;}System.out.println(root.value+" ");binaryTreePrevOrder(root.left);binaryTreePrevOrder(root.right);}//⼆叉树的中序遍历递归void binaryTreeInOrder(TreeNode root){if(root==null){return;}binaryTreeInOrder(root.left);System.out.println(root.value+" ");binaryTreeInOrder(root.right);}//⼆叉树的后续遍历递归void binaryTreePostOrder(TreeNode root){if(root==null){return;}binaryTreePostOrder(root.left);binaryTreePostOrder(root.right);System.out.println(root.value+" ");}//层序遍历void binaryTreeLevelOrder(TreeNode root,int level){if(root ==null||level<1){return;}if(level==1){System.out.print(root.value+" ");}binaryTreeLevelOrder(root.left,level-1);binaryTreeLevelOrder(root.right,level-1);}void BTreeLevelOrder(TreeNode root){if (root == null)return;int dep = getHeight(root);for (int i = 1; i <= dep; i++){binaryTreeLevelOrder(root,i);}}//⼆叉树的层序遍历⾮递归void binaryTreeLevelOrder(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();if(root != null) {queue.offer(root);//LinkedList offer add}while (!queue.isEmpty()) {//1、拿到队头的元素把队头元素的左右⼦树⼊队 TreeNode cur = queue.poll();System.out.print(cur.value+" ");//2、不为空的时候才能⼊队if(cur.left != null) {queue.offer(cur.left);}if(cur.right != null) {queue.offer(cur.right);}}}//⼆叉树的前序遍历⾮递归void binaryTreePrevOrderNonR(TreeNode root){Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode top = null;while (cur != null || !stack.empty()) {while (cur != null) {stack.push(cur);System.out.print(cur.value + " ");cur = cur.left;}top = stack.pop();cur = top.right;}System.out.println();}//⼆叉树的中序遍历⾮递归void binaryTreeInOrderNonR(TreeNode root){Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode top = null;while (cur != null || !stack.empty()) {while (cur != null) {stack.push(cur);cur = cur.left;}top = stack.pop();System.out.print(top.value+" ");cur = top.right;}System.out.println();}//⼆叉树的后序遍历⾮递归void binaryTreePostOrderNonR(TreeNode root) {Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode prev = null;while (cur != null || !stack.empty()) {while (cur != null) {stack.push(cur);cur = cur.left;}cur = stack.peek();//L D//cur.right == prev 代表的是 cur的右边已经打印过了if(cur.right == null || cur.right == prev) {stack.pop();System.out.println(cur.value);prev = cur;cur = null;}else {cur = cur.right;}}}//⼆叉树的节点个数递归int getSize(TreeNode root){if(root==null){return 0;}return getSize(root.left)+getSize(root.right)+1;}//⼆叉树的叶⼦节点的个数递归int getLeafSize(TreeNode root){if(root==null){return 0;}if(root.left==null && root.right==null){return 1;}return getLeafSize(root.left)+getLeafSize(root.right); }//⼆叉树得到第K层结点的个数int getKlevelSize(TreeNode root ,int k){if(root==null){return 0;}if(k == 1){return 1;}return getKlevelSize(root.left,k-1)+getKlevelSize(root.right,k-1);}//⼆叉树查找并返回该结点递归// 查找，依次在⼆叉树的根、左⼦树、// 右⼦树中查找 value，如果找到，返回结点，否则返回 nullTreeNode find(TreeNode root, int value){if(root == null) {return null;}if(root.value == value){return root;}TreeNode ret = find(root.left,value);if(ret != null) {return ret;}ret = find(root.right,value);if(ret != null) {return ret;}return null;}//⼆叉树的⾼度int getHeight(TreeNode root){if(root==null){return 0;}int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);return leftHeight>rightHeight ? leftHeight+1:rightHeight+1;}//判断⼀个树是不是完全⼆叉树public int binaryTreeComplete(TreeNode root) {Queue<TreeNode> queue = new LinkedList<TreeNode>();if(root != null) {queue.add(root);//offer}while(!queue.isEmpty()) {TreeNode cur = queue.peek();queue.poll();if(cur != null) {queue.add(cur.left);queue.add(cur.right);}else {break;}}while(!queue.isEmpty()) {TreeNode cur = queue.peek();if (cur != null){//说明不是满⼆叉树return -1;}else{queue.poll();}}return 0;//代表是完全⼆叉树}//检查两棵树是否是相同的，如果两棵树结构相同，并且在结点上的值相同，那么这两棵树是相同返回true public boolean isSameTree(TreeNode p,TreeNode q){if((p==null&&q!=null)||(p!=null&&q==null)){}if(p==null && q==null){return true;}if(p.value!=q.value){return false;}return isSameTree(p.left,q.left)&&isSameTree(p.right,q.left);}//检查是否为⼦树public boolean isSubTree(TreeNode s,TreeNode t){if(s==null||t==null){return false;}if(isSameTree(s,t)){return true;}else if (isSubTree(s.left,t)){return true;}else if(isSubTree(s.right,t)){return true;}else{return false;}}//1.判断是否为平衡⼆叉树，左右⼦树的⾼度之差不超过 "1"(⼤根本⾝是平衡⼆叉树，左右⼦树也必须是平衡⼆叉树) // 时间复杂度为n^2//2.求复杂度为O(n)的解法public boolean isBanlanced(TreeNode root){if(root==null){return true;}else{int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);return Math.abs(leftHeight-rightHeight)<2&&isBanlanced(root.left)&&isBanlanced(root.right);}}//判断是否为对称⼆叉树public boolean isSymmetric(TreeNode root){if(root==null){return true;}return isSymmetric(root.left,root.right);}public boolean isSymmetric(TreeNode lefttree,TreeNode righttree){if((lefttree==null && righttree!=null)||(lefttree!=null && righttree ==null)){return false;}if(lefttree == null && righttree == null){return true;}return lefttree.value == righttree.value && isSymmetric(lefttree.left,righttree.right)&& isSymmetric(lefttree.right,righttree.left);}//⼆叉树创建字符串⾮递归写法public String tree2str(TreeNode t){StringBuilder sb = new StringBuilder();tree2strchild(t,sb);return sb.toString();}public void tree2strchild(TreeNode t ,StringBuilder sb){if (t==null){}sb.append(t.value);if (t.left!=null){sb.append("(");tree2strchild(t.left,sb);sb.append(")");}else {if (t.right==null){}}}//⼆叉树字符串递归写法public String CreateStr(TreeNode t){if(t==null){return "";}if(t.left==null&&t.right==null){return t.value+"";}if(t.left==null){return t.value+"()"+"("+CreateStr(t.right)+")";}if(t.right==null){return t.value+"("+CreateStr(t.left)+")";}return t.value+"("+CreateStr(t.left)+")"+"("+CreateStr(t.right)+")";}public int rob(TreeNode root) {if (root == null) return 0;return Math.max(robOK(root), robNG(root));}private int robOK(TreeNode root) {if (root == null) return 0;return root.value + robNG(root.left) + robNG(root.right);}private int robNG(TreeNode root) {if (root == null) return 0;return rob(root.left) + rob(root.right);}//⼆叉树的公共祖先public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root==null){return null;}if(root==p||root==q){return root;}TreeNode leftTree = lowestCommonAncestor(root.left,p,q);//p||q nullTreeNode rightTree = lowestCommonAncestor(root.right,p,q);//p||q null//3if(leftTree!=null && rightTree!=null){return root;}//左边找到else if (leftTree!=null ){return leftTree;}//右边找到else if(rightTree!=null){return rightTree;}//都没找到的情况下return null;}//⼆叉搜索树，若他的左⼦树不为空，左⼦树上的所有节点都⼩于根节点，//如果他的右⼦树不为空，右⼦树上的所有节点都⼤于根节点//最终他的中序排列都是有序结果//输⼊⼀棵⼆叉搜索树，将该⼆叉搜索树转换成⼀个排序的双向链表。

n 后问题1 问题描述：N 皇后问题是一个古老而著名的问题。

该问题是十九世纪著名的数学家高斯1850年提出的。

八皇后问题要求在一个N ＊N 的棋盘上放上N 个皇后，使得每一个皇后既攻击不到另外N-1个皇后，也不被另外N-1个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子，问有多少种不同的摆法？并找出所有的摆法。

因此，N 皇后问题等于要求N 个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。

2 回朔法回溯法有“通用的题解法”之称。

从问题的某种可能情况出发，搜索所有能到达的可能情况，然后以其中一种可能的情况为新的出发点，继续向下探索，当所有可能情况1 2 3 4 5 6 7 8 1 2 3 4 5 6 78都探索过且都无法到达目标的时候，再回退到上一个出发点，继续探索另一个可能情况，这种不断回头寻找目标的方法称为“回溯法”。

适用于解组合是较大的问题。

回朔法思想：1针对所给问题，定义问题的解空间。

2.确定易于搜索的解空间结构。

3.以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

在搜索过程中，通常采用两种策略避免无效搜索：一是用约束函数剪去得不到可行解的子树；二是用限界函数剪去得不到最优解的子树。

这两类函数统称为剪枝函数。

回溯算法的一个显著的特性是在搜索过程中动态产生问题的解空间。

在任何时刻，只保存从根结点到当前扩展结点的路径。

因此，回溯算法的空间需求为o（n），（n为从根结点起最长路径的长度）。

而显式地存储整个解空间则需要o（2n）或o（n!）内存空间。

回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。

void backtrack (int t){if (t>n) output(x);elsefor (int i=f(n,t);i<=g(n,t);i++){x[t]=h(i);if (constraint(t)&&bound(t)) backtrack(t+1);}}采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。

实现图的遍历算法实验报告实现图的遍历算法实验报告⼀实验题⽬: 实现图的遍历算法⼆实验要求:2.1:（1）建⽴如图（p126 8.1）所⽰的有向图 G 的邻接矩阵，并输出之（2）由有向图G的邻接矩阵产⽣邻接表，并输出之（3）再由（2）的邻接表产⽣对应的邻接矩阵，并输出之2.2 （1）输出如图8.1所⽰的有向图G从顶点0开始的深度优先遍历序列（递归算法）（2）输出如图8.1所⽰的有向图G从顶点0开始的深度优先遍历序列（⾮递归算法）（3）输出如图8.1所⽰的有向图G从顶点0开始的⼴度优先遍历序列三实验内容:3.1 图的抽象数据类型:ADT Graph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。

数据关系R：R={VR}VR={|v,w∈V且P(v,w)，表⽰从v到w的弧，谓词P(v,w)定义了弧的意义或信息}基本操作：CreateGraph( &G, V, VR )初始条件：V是图的顶点集，VR是图中弧的集合。

操作结果：按V和VR的定义构造图G。

DestroyGraph( &G )初始条件：图G存在。

操作结果：销毁图G。

LocateVex( G, u )初始条件：图G存在，u和G中顶点有相同特征。

操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其它信息。

GetVex( G, v )初始条件：图G存在，v是G中某个顶点。

操作结果：返回v的值。

PutVex( &G, v, value )初始条件：图G存在，v是G中某个顶点。

初始条件：图G存在，v是G中某个顶点。

操作结果：返回v的第⼀个邻接顶点。

若顶点在G中没有邻接顶点，则返回“空”。

NextAdjVex( G, v, w )初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。

操作结果：返回v的（相对于w的）下⼀个邻接顶点。

若w是v 的最后⼀个邻接点，则返回“空”。

InsertVex( &G, v )初始条件：图G存在，v和图中顶点有相同特征。

数据结构1、先序遍历的非递归算法。

用c语言写。

void PreOrderUnrec(Bitree t){SqStack s;StackInit(s);p=t;while (p!=null || !StackEmpty(s)){while (p!=null) //遍历左子树{visite(p->data);push(s,p);p=p->lchild;}//endwhileif (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历{ p=pop(s);p=p->rchild;}//endif}//endwhile}//PreOrderUnrec/////////////////////////////////#include "stdio.h"#include "stdlib.h"#include "string.h"#define null 0struct node{char data;struct node *lchild;struct node *rchild;};//先序,中序建树struct node *create(char *pre,char *ord,int n){struct node * head;int ordsit;head=null;if(n<=0){return null;}else{head=(struct node *)malloc(sizeof(struct node)); head->data=*pre;head->lchild=head->rchild=null;ordsit=0;while(ord[ordsit]!=*pre){ordsit++;}head->lchild=create(pre+1,ord,ordsit);head->rchild=create (pre+ordsit+1,ord+ordsit+1,n-ordsit-1); return head;}}//中序递归遍历void inorder(struct node *head){if(!head)return;else{inorder(head->lchild );printf("%c",head->data );inorder(head->rchild );}}//中序非递归遍历void inorder1(struct node *head) {struct node *p;struct node *stack[20];int top=0;p=head;while(p||top!=0){while (p){stack[top++]=p;p=p->lchild ;}p=stack[--top];printf("%c ",p->data );p=p->rchild ;}}/////////////////////////////////////////////////////////////////// ////////////////////二叉树前序、中序、后序三种遍历的非递归算法1.先序遍历非递归算法void PreOrderUnrec(Bitree *t){Stack s;StackInit(s);Bitree *p=t;while (p!=NULL || !StackEmpty(s)){while (p!=NULL) //遍历左子树{visite(p->data);push(s,p);p=p->lchild;}if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历{p=pop(s);p=p->rchild;}//endif}//endwhile}2.中序遍历非递归算法void InOrderUnrec(Bitree *t){Stack s;StackInit(s);Bitree *p=t;while (p!=NULL || !StackEmpty(s)){while (p!=NULL) //遍历左子树{push(s,p);p=p->lchild;}if (!StackEmpty(s)){p=pop(s);visite(p->data); //访问根结点p=p->rchild; //通过下一次循环实现右子树遍历}//endif }//endwhile}3.后序遍历非递归算法typedef enum{L,R} tagtype;typedef struct{Bitree ptr;tagtype tag;}stacknode;typedef struct{stacknode Elem[maxsize];int top;}SqStack;void PostOrderUnrec(Bitree t) {SqStack s;stacknode x;StackInit(s);p=t;do{while (p!=null) //遍历左子树{x.ptr = p;x.tag = L; //标记为左子树push(s,x);p=p->lchild;}while (!StackEmpty(s) && s.Elem[s.top].tag==R){x = pop(s);p = x.ptr;visite(p->data); //tag为R,表示右子树访问完毕,故访问根结点} if (!StackEmpty(s)){s.Elem[s.top].tag =R; //遍历右子树p=s.Elem[s.top].ptr->rchild;}}while (!StackEmpty(s));}//PostOrderUnrec二。

浅析深度优先和⼴度优先遍历实现过程、区别及使⽤场景⼀、什么是深度/⼴度优先遍历？ 深度优先遍历简称DFS（Depth First Search），⼴度优先遍历简称BFS（Breadth First Search），它们是遍历图当中所有顶点的两种⽅式。

这两种遍历⽅式有什么不同呢？我们来举个栗⼦： 我们来到⼀个游乐场，游乐场⾥有11个景点。

我们从景点0开始，要玩遍游乐场的所有景点，可以有什么样的游玩次序呢？1、深度优先遍历 第⼀种是⼀头扎到底的玩法。

我们选择⼀条⽀路，尽可能不断地深⼊，如果遇到死路就往回退，回退过程中如果遇到没探索过的⽀路，就进⼊该⽀路继续深⼊。

在图中，我们⾸先选择景点1的这条路，继续深⼊到景点7、景点8，终于发现⾛不动了： 于是，我们退回到景点7，然后探索景点10，⼜⾛到了死胡同。

于是，退回到景点1，探索景点9： 按照这个思路，我们再退回到景点0，后续依次探索景点2、3、5、4、发现相邻的都玩过了，再回退到3，再接着玩6，终于玩遍了整个游乐场： 具体次序如下图，景点旁边的数字代表探索次序。

当然还可以有别的排法。

像这样先深⼊探索，⾛到头再回退寻找其他出路的遍历⽅式，就叫做深度优先遍历（DFS）。

这⽅式看起来很像⼆叉树的前序遍历。

没错，其实⼆叉树的前序、中序、后序遍历，本质上也可以认为是深度优先遍历。

2、⼴度优先遍历 除了像深度优先遍历这样⼀头扎到底的玩法以外，我们还有另⼀种玩法：⾸先把起点相邻的⼏个景点玩遍，然后去玩距离起点稍远⼀些（隔⼀层）的景点，然后再去玩距离起点更远⼀些（隔两层）的景点… 在图中，我们⾸先探索景点0的相邻景点1、2、3、4： 接着，我们探索与景点0相隔⼀层的景点7、9、5、6： 最后，我们探索与景点0相隔两层的景点8、10： 像这样⼀层⼀层由内⽽外的遍历⽅式，就叫做⼴度优先遍历（BFS）。

这⽅式看起来很像⼆叉树的层序遍历。

没错，其实⼆叉树的层序遍历，本质上也可以认为是⼴度优先遍历。

dfs求树高度的非递归算法深度优先搜索（DFS）求树的高度的非递归算法是一种基于栈的迭代算法。

树的高度指的是从根节点到最远叶子节点的最长路径上所经过的节点个数。

首先，我们可以选择一个根节点开始遍历树。

我们将根节点入栈，并初始化高度为0。

接下来，我们进入一个循环，在循环中执行以下操作：1. 如果栈为空，则遍历结束，返回高度。

2. 弹出栈顶节点，将其设为当前节点。

3. 如果当前节点有子节点，则将其所有子节点入栈，并将高度加1。

4. 继续循环。

在迭代过程中，我们不断更新高度的最大值，直到栈为空。

最后，我们返回最大高度作为树的高度。

下面是一个具体的示例算法实现：```int getTreeHeight(TreeNode* root) {if(root == nullptr) {return 0;}stack<pair<TreeNode*, int>> st;int maxHeight = 0;st.push(make_pair(root, 1));while(!st.empty()) {TreeNode* currNode = st.top().first;int currHeight = st.top().second;st.pop();maxHeight = max(maxHeight, currHeight);if(currNode->left != nullptr) {st.push(make_pair(currNode->left, currHeight + 1));}if(currNode->right != nullptr) {st.push(make_pair(currNode->right, currHeight + 1));}}return maxHeight;}```以上是DFS求树高度的非递归算法的实现。

通过使用栈来模拟递归的调用栈，我们可以遍历整个树并找到最长路径上的节点个数。

基于栈的非递归深度优先遍历算法设计与实现作者：李光杰王聪来源：《电脑知识与技术》2014年第03期摘要：深度优先遍历是图的一种重要遍历方法，该文主要介绍在邻接矩阵存储方式下，利用栈实现对稠密图进行深度优先非递归遍历的算法设计及实现过程。

关键词：深度优先；算法；非递归；栈中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）03-0470-03图是一种重要的数据结构，在实际生活中应用非常广泛，如计算机网络、电力网络、交通信号网路等。

图可分为有向图，无向图，连通图，非联通图，稠密图，稀疏图等，该文仅以图1为例介绍无向连通稠密图的存储以及基于栈的非递归深度优先遍历算法。

1 图的存储表示图在计算机中的物理存储方式主要有邻接矩阵和邻接表两种，其中邻接矩阵适用于稠密图，邻接表适用于稀疏图。

该文例图可视为稠密图，因此图的物理存储采用邻接矩阵（二维数组adj[][]）实现，下面是创建邻接矩阵adj[][]的C语言代码：void create_matrix（int adj[V+1][V+1]）{int E，u，v，wgt；//表示边的条数printf（"请输入边数："）；scanf（"%d"，&E）；for（int i=1；i{printf（"请输入第%d条边"，i）；scanf（"%d %d %d"，&u，&v，&wgt）；adj[u][v]=adj[v][u]=wgt；}}图1利用create_matrix函数建立的邻接矩阵存储示意图如图2所示，我们可以发现图的邻接矩阵是对称矩阵。

2 图的深度优先遍历思想深度优先搜索是图的重要遍历方法之一，遍历过程的实质是对每个顶点查找其邻接点的过程，类似于树的先根遍历，具体思路为：1）从图中任一顶点v开始，当顶点v未被访问过时，做访问标记；2）遍历v的所有邻接点：如果邻接点u未被访问过：①输出顶点u；②做访问标记；③遍历u的所有邻接点；为了保证图中的各顶点在遍历过程中访问且仅访问一次，需要为每个顶点设一个访问标记，该文利用数组visited[V]实现，数组初始值设置为0，表示所有顶点均未被访问。

先序遍历的非递归算法C语言先序遍历是二叉树遍历的一种方式，它的遍历顺序是根节点、左子树、右子树。

非递归算法利用栈的数据结构来实现。

具体算法步骤如下：1.定义一个栈，用于存储节点。

2.将根节点入栈。

3.当栈不为空时，执行步骤4-6，否则结束遍历。

4.弹出栈顶节点，并访问该节点。

5.若该节点有右孩子，将右孩子入栈。

6.若该节点有左孩子，将左孩子入栈。

7.返回步骤3下面是使用C语言实现先序遍历的非递归算法的示例代码：```c#include <stdio.h>#include <stdlib.h>//定义二叉树节点结构typedef struct TreeNodeint data;struct TreeNode* left;struct TreeNode* right;} TreeNode;//定义栈结构typedef struct StackTreeNode* data[100]; // 栈的最大容量int top; // 栈顶指针} Stack;Stack* createStacStack* stack = (Stack*)malloc(sizeof(Stack)); stack->top = -1;return stack;void push(Stack* stack, TreeNode* node)stack->data[++stack->top] = node;TreeNode* pop(Stack* stack)return stack->data[stack->top--];int isEmpty(Stack* stack)return stack->top == -1;//先序遍历的非递归算法void preorderTraversal(TreeNode* root)if (root == NULL)return;}Stack* stack = createStack(; // 创建栈push(stack, root); // 根节点入栈while (!isEmpty(stack))TreeNode* node = pop(stack); // 弹出栈顶节点printf("%d ", node->data); // 访问节点//右孩子先入栈，保证左孩子会在右孩子之前被访问if (node->right != NULL)push(stack, node->right);}//左孩子入栈if (node->left != NULL)push(stack, node->left);}}free(stack); // 释放栈的内存int mai//构建二叉树TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); root->data = 1;TreeNode* node2 = (TreeNode*)malloc(sizeof(TreeNode)); node2->data = 2;TreeNode* node3 = (TreeNode*)malloc(sizeof(TreeNode)); node3->data = 3;TreeNode* node4 = (TreeNode*)malloc(sizeof(TreeNode)); node4->data = 4;TreeNode* node5 = (TreeNode*)malloc(sizeof(TreeNode)); node5->data = 5;root->left = node2;root->right = node3;node2->left = node4;node2->right = NULL;node3->left = NULL;node3->right = node5;node4->left = NULL;node4->right = NULL;node5->left = NULL;node5->right = NULL;//先序遍历printf("先序遍历结果：");preorderTraversal(root);//释放二叉树的内存free(root);free(node2);free(node3);free(node4);free(node5);return 0;```以上代码实现了二叉树先序遍历的非递归算法。

（转载）图的深度优先遍历⾮递归算法纠结图的深度优先搜索算法好久，⾮递归算法需要⽤到栈来记录上⼀次访问的结果，但是⼤脑中反应不出来。

这⾥做⼀个记录：栈的⽤处：在这⼀步执⾏完成之后，下⼀步需要⽤到上⼀步执⾏的结果，⽤栈来实现往往是最有效的。

以下是转载的内容：深度优先遍历算法的⾮递归实现需要了解深度优先遍历的执⾏过程，设计⼀个栈来模拟递归实现中系统设置的⼯作栈，算法的伪代码描述为：假设图采⽤邻接矩阵作为存储结构，具体算法如下：[cpp]1. 深度优先遍历算法的⾮递归实现需要了解深度优先遍历的执⾏过程，设计⼀个栈来模拟递归实现中系统设置的⼯作栈，算法的伪代码描述为：2.3.4. 假设图采⽤邻接矩阵作为存储结构，具体算法如下：5.6.7. <PRE class=cpp name="code">#include<iostream>8. #include <queue>9. using namespace std;10. #define MAX_NODE 1211. bool visited[MAX_NODE] ;12. int stack[ MAX_NODE] ;13. queue<int> q;14. int Matric[MAX_NODE][MAX_NODE] =15. {16. {-1,1,1,0,0,0,0,0,0,0,0,0},17. {1,-1,1,0,1,1,0,0,0,0,0,0},18. {1,1,-1,1,0,0,0,0,0,0,0,0},19. {0,0,1,-1,1,0,0,0,0,0,1,1},20. {0,1,0,1,-1,0,0,0,0,0,0,0},21. {0,1,0,0,0,-1,0,0,0,0,1,0},22. {0,0,0,0,0,0,-1,1,1,1,0,0},23. {0,0,0,0,0,0,1,-1,0,0,0,0},24. {0,0,0,0,0,0,1,0,-1,1,1,0},25. {0,0,0,0,0,0,1,0,1,-1,0,1},26. {0,0,0,1,0,1,0,0,1,0,-1,0},27. {0,0,0,1,0,0,0,0,0,1,0,-1},28. };29. void DFS( int v)30. {31. cout << " v"<< v ;32. int top = -1 ;33. visited[v] = true ;34. stack[++top] = v ;35. while ( top != -1)36. {37. v = stack[top] ;38. for (int i = 0 ; i < MAX_NODE ; i++)39. {40. if (Matric[v][i] == 1 &&!visited[i])41. {42. cout << " v" << i ;43. visited[i] = true ;44. stack[ ++top ] = i ;45. break ;46. }47. }48. if( i == MAX_NODE)49. {50. top -- ;51. }52. }53.54. }55.56.57. void BFS( int v)58. {59. int node = 0;60. q.push(v);61. visited[v] = true;62. while( !q.empty())63. {64. node = q.front();65. for ( int i = 0; i < MAX_NODE; i++ )66. {67. if ( Matric[node][i] == 1 && !visited[i])68. {69. visited[i] = true;70. q.push(i);71. }72. }73. cout <<" v" << node;74. q.pop();75. }76.77.78. }79. void Init()80. {81.82. int i = 0;83. for ( i = 0; i < MAX_NODE; i++)84. {85. visited[i] = false;86. }87. }88. int main()89. {90. Init();91. DFS( 1 ) ;92. cout << endl ;93. Init();94. BFS( 1 );95. cout << endl;96. Init();97. DFS( 6 );98. cout <<endl;99. return 0 ;100. }</PRE>101. <PRE></PRE>102. <PRE class=cpp name="code"></PRE>　深度优先遍历算法的⾮递归实现需要了解深度优先遍历的执⾏过程，设计⼀个栈来模拟递归实现中系统设置的⼯作栈，算法的伪代码描述为： 假设图采⽤邻接矩阵作为存储结构，具体算法如下：[cpp]1. #include<iostream>2. #include <queue>3. using namespace std;4. #define MAX_NODE 125. bool visited[MAX_NODE] ;6. int stack[ MAX_NODE] ;7. queue<int> q;8. int Matric[MAX_NODE][MAX_NODE] =9. {10. {-1,1,1,0,0,0,0,0,0,0,0,0},11. {1,-1,1,0,1,1,0,0,0,0,0,0},12. {1,1,-1,1,0,0,0,0,0,0,0,0},13. {0,0,1,-1,1,0,0,0,0,0,1,1},14. {0,1,0,1,-1,0,0,0,0,0,0,0},15. {0,1,0,0,0,-1,0,0,0,0,1,0},16. {0,0,0,0,0,0,-1,1,1,1,0,0},17. {0,0,0,0,0,0,1,-1,0,0,0,0},18. {0,0,0,0,0,0,1,0,-1,1,1,0},19. {0,0,0,0,0,0,1,0,1,-1,0,1},20. {0,0,0,1,0,1,0,0,1,0,-1,0},21. {0,0,0,1,0,0,0,0,0,1,0,-1},22. };23. void DFS( int v)24. {25. cout << " v"<< v ;26. int top = -1 ;27. visited[v] = true ;28. stack[++top] = v ;29. while ( top != -1)30. {31. v = stack[top] ;32. for (int i = 0 ; i < MAX_NODE ; i++)33. {34. if (Matric[v][i] == 1 &&!visited[i])35. {36. cout << " v" << i ;37. visited[i] = true ;38. stack[ ++top ] = i ;39. break ;40. }41. }42. if( i == MAX_NODE)43. {44. top -- ;45. }46. }47.48. }49.50.51. void BFS( int v)52. {53. int node = 0;54. q.push(v);55. visited[v] = true;56. while( !q.empty())57. {58. node = q.front();59. for ( int i = 0; i < MAX_NODE; i++ )60. {61. if ( Matric[node][i] == 1 && !visited[i])62. {63. visited[i] = true;64. q.push(i);65. }66. }67. cout <<" v" << node;68. q.pop();69. }70.71.72. }73. void Init()74. {75.76. int i = 0;77. for ( i = 0; i < MAX_NODE; i++)78. {79. visited[i] = false;80. }81. }82. int main()83. {84. Init();85. DFS( 1 ) ;86. cout << endl ;87. Init();88. BFS( 1 );89. cout << endl;90. Init();91. DFS( 6 );92. cout <<endl;93. return 0 ;94. }。

先序遍历的非递归算法先序遍历是二叉树的一种遍历方式，它的步骤是先访问根节点，然后递归地先序遍历左子树，最后递归地先序遍历右子树。

在非递归算法中，我们使用栈来辅助实现遍历。

首先，我们创建一个空栈，将根节点压入栈中。

然后进入循环，循环条件是栈不为空。

在循环中，首先将栈顶元素出栈并访问，然后将其右子节点（如果存在）压入栈中，再将其左子节点（如果存在）压入栈中。

这样可以保证在遍历的过程中，左子树总是先于右子树被访问。

详细的步骤如下：1.创建一个空栈，将根节点压入栈中。

2.进入循环，循环条件为栈不为空。

在循环中执行以下步骤：1.弹出栈顶元素并访问。

2.如果存在右子节点，将右子节点压入栈中。

3.如果存在左子节点，将左子节点压入栈中。

3.循环结束后，遍历完成。

下面是使用非递归算法实现先序遍历的代码：```pythonclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef preorderTraversal(root):if not root:return []stack = [] # 创建空栈result = [] # 用于存储遍历结果stack.append(root) # 将根节点压入栈中while stack: # 当栈不为空时循环node = stack.pop( # 弹出栈顶元素并访问result.append(node.val)if node.right: # 如果存在右子节点，将右子节点压入栈中stack.append(node.right)if node.left: # 如果存在左子节点，将左子节点压入栈中stack.append(node.left)return result#测试代码#创建二叉树root = TreeNode(1)root.left = TreeNode(2)root.right = TreeNode(3)root.left.left = TreeNode(4)root.left.right = TreeNode(5)#执行先序遍历并输出结果result = preorderTraversal(root)print(result)```运行上述代码可以得到先序遍历的结果：[1,2,4,5,3]。

三种遍历树的⽅法树的概念在开发⾥⾯是很重要的⼀部分，xml的⽂档对象模型(DOM)就是⼀棵树，⽂件夹⽂件的结构也是⼀棵树。

遍历树是开发中经常要遇到的⼀个问题，⽐如，要找出DOM⾥⾯的img 标签的个数，就要遍历⼀棵DOM树。

要在⼀个⽬录⾥⾯查找是否有⼀个⽂件也要⽤到遍历这个⽬录。

在这⾥我们以遍历⽂件为例，说明遍历树的三种基本的⽅法：递归深度优先算法，⾮递归深度优先算法，⾮递归⼴度优先算法。

这些算法是我们在项⽬中经常重复的⼀些算法，我感觉我写程序以来，我做的⼤多数算法都⽤了⼤⼆学的那本数据结构，有些时候，只是改装⼀些⼀些算法，有些时候也只是把⼏种算法合并⼀下，也许这是为什么数据结构这本书这样重要的原因。

先看代码：<?phpdefine('DS', DIRECTORY_SEPARATOR);function rec_list_files($from = '.'){if(!is_dir($from)) {return array();}$files = array();if($dh = opendir($from)){while(false !== ($file = readdir($dh))) {if($file == '.' || $file == '..') {continue;}$path = $from . DS . $file;if (is_file($path)) {$files[] = $path;}$files = array_merge($files, rec_list_files($path));}closedir($dh);}return$files;}function deep_first_list_files($from = '.'){if(!is_dir($from)) {return false;}$files = array();$dirs = array($from);while(NULL !== ($dir = array_pop($dirs))) {if( $dh = opendir($dir)) {while( false !== ($file = readdir($dh))) {if($file == '.' || $file == '..') {continue;}$path = $dir . DS . $file;if(is_dir($path)) {$dirs[] = $path;} else {$files[] = $path;}}closedir($dh);}}return$files;}function breadth_first_files($from = '.') {$queue = array(rtrim($from, DS).DS);// normalize all paths$files = array();while($base = array_shift($queue )) {if (($handle = opendir($base))) {while (($child = readdir($handle)) !== false) {if( $child == '.' || $child == '..') {continue;}if (is_dir($base.$child)) {$combined_path = $base.$child.DS;array_push($queue, $combined_path);} else {$files[] = $base.$child;}}closedir($handle);} // else unable to open directory => NEXT CHILD}return$files; // end of tree, file not found}function profile($func, $trydir){$mem1 = memory_get_usage();echo '<pre>----------------------- Test run for '.$func.'() ';flush();$time_start = microtime(true);$list = $func($trydir);//print_r($list);$time = microtime(true) - $time_start;echo 'Finished : '.count($list).' files</pre>';$mem2 = memory_get_peak_usage();printf('<pre>Max memory for '.$func.'() : %0.2f kbytes Running time for '.$func.'() : %0.f s</pre>',($mem2-$mem1)/1024.0, $time);return$list;}profile('rec_list_files', "D:\www\server");profile('deep_first_list_files', "D:\www\server");profile('breadth_first_files', "D:\www\server");>rec_list_files 是递归的深度优先的算法，这个是⽤⼀个简单的函数递归来实现，⽤array_merge 来合并数组deep_first_list_files 是⾮递归的深度优先的算法,⽤了⼀个栈来实现。

第5章习题解答2- 9, 0-6, 4-9, 2-6, 6-4；(1) 请确定图中各个顶点的度； (2) 给出图的连通分量；(3)列出至少有三个顶点的简单路径。

［解答］由题意得到的图如图5-1所示。

［解答］如图5-2所示，分别为1个顶点，2个顶点，3个顶点，4个顶点，5个顶点和6个顶点 的无向完全图。

5. 1 已知一个图有。

到9 一共10个顶点, 图中边为：3-7,1-4, 7-8, 0-5, 5-2, 3-8,(1)顶点:0 12 3 4 顶点的度：213232⑵连通分量1： 连通分量2： (3)连通分量1：连通分量2中:4-6-0, 4-6-2, 6-2-5, 6-2-9, 9-2-6, 0-5-2,如图5-1 (b)所示。

如图5-1 (a)所示。

3- 7-8； 1-4-6, 1-4-9 4- 9-2, 6-0-5, 6-4一9, 9—2-5,共有13条。

5.2向完全图。

请分别画出1个顶点，2个顶点, 3个顶点，4个顶点，5个顶点和6个顶点的无图5-15.3 若无向图G有15条边，有3个度为4的顶点，其余顶点的度不大于3,图G至少有多少个顶点？［解答］设图G至少有x个顶点，根据握手定理有：3 X4 + 3 (x-3) =2X15, x=9(个)5.4 试证明有/个顶点的任何无环连通图均有V -1条边。

［解答］无环连通图即为树。

根据树的性质，有V个顶点的树均有V-1条边。

5.5对于一个有r个顶点和的无向完全图，请问一共有多少个子图？［解答］V 2一共有个子图。

i=05.6对于一个有V个顶点和E条边的无向图，请给出其连通分量个数的上界和下界。

［解答］根据无向图中顶点和边的关系可知，E必然满足0WEWK(片1)/2,由分析可得到：V-E if E<V-1 c = dmin［1 if E>V-1M=V-(l + Jl + 8E)/2 E<V(V-1)/2提示：在不形成环的情况下，连通分量数目达到最小值；当某个连通分量为完全图时, 连通分量数目达到最大值。