树的广度(深度）优先遍历算法

曾经终败给现在 2023-10-17 16:19 18阅读 0赞

1 树的广度优先遍历算法 
    广度优先遍历算法，又叫宽度优先遍历，或横向优先遍历，是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。 
     
    如上图所示的二叉树，A 是第一个访问的，然后顺序是 B、C，然后再是 D、E、F、G。借助队列数据结构，由于队列是先进先出的顺序，因此可以先将左子树入队，然后再将右子树入队。 
    这样一来，左子树结点就存在队头，可以先被访问到。

2 树的深度优先遍历算法 
    深度优先遍历算法是遍历算法的一种。是沿着树的深度遍历树的节点。 当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。 如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。 
     
    如上图所示的二叉树： A 是第一个访问的，然后顺序是 B、D，然后是 E。接着再是 C、F、G。 在遍历了根结点后，就开始遍历左子树，最后才是右子树。 因此可以借助堆栈的数据结构，由于堆栈是后进先出的顺序，由此可以先将右子树压栈，然后再对左子树压栈， 这样一来，左子树结点就存在了栈顶上，因此某结点的左子树能在它的右子树遍历之前被遍历。

1 #include <vector>
     2 #include <iostream>
     3 #include <stack>
     4 #include <queue>
     5 using namespace std;
     6 
     7 struct BitNode
     8 {
     9     int data;
    10     BitNode *left, *right;
    11     BitNode(int x) :data(x), left(0), right(0){}
    12 };
    13 
    14 void Create(BitNode *&root)
    15 {
    16     int key;
    17     cin >> key;
    18     if (key == -1)
    19         root = NULL;
    20     else
    21     {
    22         root = new BitNode(key);
    23         Create(root->left);
    24         Create(root->right);
    25     }
    26 }
    27 
    28 void PreOrderTraversal(BitNode *root)
    29 {
    30     if (root)
    31     {
    32         cout << root->data << " ";
    33         PreOrderTraversal(root->left);
    34         PreOrderTraversal(root->right);
    35     }
    36 }
    37 
    38 //深度优先搜索
    39 //利用栈，现将右子树压栈再将左子树压栈
    40 void DepthFirstSearch(BitNode *root)
    41 {
    42     stack<BitNode*> nodeStack;
    43     nodeStack.push(root);
    44     while (!nodeStack.empty())
    45     {
    46         BitNode *node = nodeStack.top();
    47         cout << node->data << ' ';
    48         nodeStack.pop();
    49         if (node->right)
    50         {
    51             nodeStack.push(node->right);
    52         }
    53         if (node->left)
    54         {
    55             nodeStack.push(node->left);
    56         }
    57     }
    58 }
    59 
    60 //广度优先搜索
    61 void BreadthFirstSearch(BitNode *root)
    62 {
    63     queue<BitNode*> nodeQueue;
    64     nodeQueue.push(root);
    65     while (!nodeQueue.empty())
    66     {
    67         BitNode *node = nodeQueue.front();
    68         cout << node->data << ' ';
    69         nodeQueue.pop();
    70         if (node->left)
    71         {
    72             nodeQueue.push(node->left);
    73         }
    74         if (node->right)
    75         {
    76             nodeQueue.push(node->right);
    77         }
    78     }
    79 }
    80 
    81 int  main()
    82 {
    83     BitNode *root = NULL;
    84     Create(root);
    85     //前序遍历
    86     PreOrderTraversal(root);
    87     //深度优先遍历
    88     cout << endl << "dfs" << endl;
    89     DepthFirstSearch(root);
    90     //广度优先搜索
    91     cout << endl << "bfs" << endl;
    92     BreadthFirstSearch(root);
    93 }