二叉树的深度优先遍历(DFS)与广度优先遍历(BFS)

首先给大家推荐一下我老师大神的人工智能教学网站。教学不仅零基础,通俗易懂,而且非常风趣幽默,还时不时有内涵黄段子!点这里可以跳转到网站

二叉树的深度优先遍历(DFS)与广度优先遍历(BFS)

深度优先遍历:从根节点出发,沿着左子树方向进行纵向遍历,直到找到叶子节点为止。然后回溯到前一个节点,进行右子树节点的遍历,直到遍历完所有可达节点为止。

广度优先遍历:从根节点出发,在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次。

DFS:ABDECFG

BFS:ABCDEFG

DFS实现:

数据结构:栈

父节点入栈,父节点出栈,先右子节点入栈,后左子节点入栈。递归遍历全部节点即可

BFS实现:

数据结构:队列

父节点入队,父节点出队列,先左子节点入队,后右子节点入队。递归遍历全部节点即可

#include <iostream>#include <stdlib.h>#include <malloc.h>#include <Stack>#include <Queue>using namespace std; typedef struct Node {    char data;    struct Node *lchild;    struct Node *rchild;} *Tree;//Tree 是一个node指针的类型定义 int index = 0;  //全局索引变量//二叉树构造器,按先序遍历顺序构造二叉树//无左子树或右子树用'#'表示void treeNodeConstructor(Tree &root, char data[]){    char e = data[index++];    if(e == '#'){        root = NULL;    }else{        root = (Node *)malloc(sizeof(Node));        root->data = e;        treeNodeConstructor(root->lchild, data);  //递归构建左子树        treeNodeConstructor(root->rchild, data);  //递归构建右子树    }}//深度优先遍历void depthFirstSearch(Tree root){    stack<Node *> nodeStack;  //使用C++的STL标准模板库    nodeStack.push(root);    Node *node;    while(!nodeStack.empty()){	    node = nodeStack.top();		cout<<node->data;//遍历根结点        nodeStack.pop();        if(node->rchild){            nodeStack.push(node->rchild);  //先将右子树压栈        }        if(node->lchild){            nodeStack.push(node->lchild);  //再将左子树压栈        }    }} //广度优先遍历void breadthFirstSearch(Tree root){    queue<Node *> nodeQueue;  //使用C++的STL标准模板库    nodeQueue.push(root);    Node *node;    while(!nodeQueue.empty()){        node = nodeQueue.front();        nodeQueue.pop();        cout<<node->data;//遍历根结点        if(node->lchild){            nodeQueue.push(node->lchild);  //先将左子树入队        }        if(node->rchild){            nodeQueue.push(node->rchild);  //再将右子树入队        }    }} int main() {    //上图所示的二叉树先序遍历序列,其中用'#'表示结点无左子树或无右子树    char data[15] = {'A', 'B', 'D', '#', '#', 'E', '#', '#', 'C', 'F','#', '#', 'G', '#', '#'};    Tree tree;    treeNodeConstructor(tree, data);    printf("深度优先遍历二叉树结果: ");    depthFirstSearch(tree);    printf("\n\n广度优先遍历二叉树结果: ");    breadthFirstSearch(tree);    return 0;} 

点这里可以跳转到人工智能网站

发表评论