门户网站建设与运行,灌南网页设计,网站设计中新闻版块怎么做,手机上如何写html网页深度优先搜索算法(Depth First Search)DFS是搜索算法的一种。它沿着树的深度遍历树的节点#xff0c;尽可能深的搜索树的分支。当节点v的所有边都己被探寻过#xff0c;搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还…深度优先搜索算法(Depth First Search)DFS是搜索算法的一种。它沿着树的深度遍历树的节点尽可能深的搜索树的分支。当节点v的所有边都己被探寻过搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点则选择其中一个作为源节点并重复以上过程整个进程反复进行直到所有节点都被访问为止。图片.png如上图所示的二叉树A 是第一个访问的然后顺序是 B、D然后是 E。接着再是 C、F、G。那么怎么样才能来保证这个访问的顺序呢分析一下在遍历了根结点后就开始遍历左子树最后才是右子树。因此可以借助堆栈的数据结构由于堆栈是后进先出的顺序由此可以先将右子树压栈然后再对左子树压栈这样一来左子树结点就存在了栈顶上因此某结点的左子树能在它的右子树遍历之前被遍历。广度优先搜索算法(Breadth First Search)又叫宽度优先搜索或横向优先搜索。是从根节点开始沿着树的宽度遍历树的节点。如果所有节点均被访问则算法中止。图片.png如上图所示的二叉树A 是第一个访问的然后顺序是 B、C然后再是 D、E、F、G。那么怎样才能来保证这个访问的顺序呢借助队列数据结构由于队列是先进先出的顺序因此可以先将左子树入队然后再将右子树入队。这样一来左子树结点就存在队头可以先被访问到。代码实现#include#include #includeusing namespace std;struct Node{int nVal;Node *pLeft;Node *pRight;Node(int val,Node* leftNULL,Node * rightNULL):nVal(val),pLeft(left),pRight(right){}; //构造};// 析构void DestroyTree(Node *pRoot){if (pRootNULL)return;Node* pLeftpRoot-pLeft;Node* pRightpRoot-pRight;delete pRoot;pRoot NULL;DestroyTree(pLeft);DestroyTree(pRight);}// 用queue实现的BFSvoid BFS(Node *pRoot){if (pRootNULL)return;queue Q;Q.push(pRoot);while(!Q.empty()){Node *node Q.front();coutnVal;if (node-pLeft!NULL){Q.push(node-pLeft);}if (node-pRight!NULL){Q.push(node-pRight);}Q.pop();}cout}// DFS的递归实现void DFS_Recursive(Node* pRoot){if (pRootNULL)return;coutnValif (pRoot-pLeft!NULL)DFS_Recursive(pRoot-pLeft);if (pRoot-pRight!NULL)DFS_Recursive(pRoot-pRight);}// DFS的迭代实现版本(stack)void DFS_Iterative(Node* pRoot){if (pRootNULL)return;stack S;S.push(pRoot);while (!S.empty()){Node *nodeS.top();coutnValS.pop();if (node-pRight!NULL){S.push(node-pRight);}if (node-pLeft!NULL){S.push(node-pLeft);}}}// 打印树的信息void PrintTree(Node* pRoot){if (pRootNULL)return;coutnValif (pRoot-pLeft!NULL){PrintTree(pRoot-pLeft);}if (pRoot-pRight!NULL){PrintTree(pRoot-pRight);}}int main(){Node *node1new Node(4);Node *node2new Node(5);Node *node3new Node(6);Node* node4new Node(2,node1,node2);Node* node5new Node(3,node3);Node* node6new Node(1,node4,node5);Node* pRoot node6;//PrintTree(pRoot);//DFS_Recursive(pRoot);DFS_Iterative(pRoot);DestroyTree(pRoot);return 0;}
