C++ 使用BFS从根节点计算二叉树中每个节点的距离

二叉树是一种非线性数据结构。它最多有两个子节点，每个节点包含数据值、左指针和右指针三个部分。顶部节点称为根节点，最后一个不含任何子节点的节点称为叶子节点。

在这个问题中，我们有一个二叉树。它有N个节点，节点范围从1到N（包括1和N），我们的任务是使用BFS找到二叉树中每个节点距离根节点的距离。

示例

让我们看看下面的例子和解释，以更好地理解这个问题。

输入

6 
      / \ 
    3    1 
   / \
  2   0 
      / \
    5   4

输出

2 1 2 1 3 3 0

解释

6是根节点，所以它的距离为0

3和1在第1层，所以它们的距离为1

2和0在接下来的一层，剩下的4和5在下一层。

BFS算法

在这种方法中，我们将实现传统的BFS算法来逐层遍历二叉树或树。

• 首先，我们要定义一个类来给二叉树提供一个结构，其中我们将定义一个整数数据类型来存储当前节点的值，并且有两个指针来存储左孩子和右孩子的地址。

• 接下来，我们将创建一个函数，该函数将以根节点为参数，并在其中定义一个队列来存储所有的元素以便按层获取它们。

• 之后，我们将使用嵌套的while循环来获取当前层的节点并将下一层的节点添加到其中。同时，我们将在数组中的当前节点的相应位置添加层号。

• 然后，我们将打印所有节点的值并返回到主函数。

示例

#include <bits/stdc++.h>
using namespace std;
class Node{
public:
   int data; // variable to store the data 
   Node* left; // variable to store the left child address 
   Node* right; // variable to store the right child address     
   // constructor to initialize the values 
   Node(int x){
      data = x;
      left = nullptr;
      right = nullptr;
   }
};
// function to get the required distance from the root 
void findDis(Node* root, int totalNodes){
   // if root is nullptr 
   if(root == nullptr){
      return; 
   }
   // defining queue and  insert root into it
   queue<Node*>q;
   q.push(root);
   // variable to count the distance from root 
   int countLevel = 0;
   // defining the array to store the total Nodes distance from the root 
   int arr[totalNodes];
   // using while loop traverse over the queue apply bfs algorithm 
   while(q.size() > 0){
      // variable to define the total number of elements in the current level 
      int cur = q.size();
      // using nested while loop to traverse the current level
      while(cur--){
         // get the front node of the queue remove the front node
         Node* cur = q.front();
         q.pop();
         // store the distance for the current node 
         arr[cur->data] = countLevel;    
         // if the left and right child are not null then add them to queue
         if(cur->left){
            q.push(cur->left);
         }
         if(cur->right){
            q.push(cur->right);
         }
      }
      // increase the level 
      countLevel += 1;
   }
   // print all the values of the current node 
   for(int i = 0; i < totalNodes; i++){
      cout<<arr[i] << " ";
   }
   cout<<endl;
}
int main(){
   // given inputs 
   int totalNodes = 7;
   Node* root = new Node(6);
   root->left = new Node(3);
   root->right = new Node(1);
   root->left->left = new Node(2);
   root->left->right = new Node(0);
   root->left->right->left = new Node(5);
   root->left->right->right = new Node(4);
   // calling the function 
   cout<<"The distance of all the nodes from the root node is: "<<endl;
   findDis(root, totalNodes);
   return 0;
}

输出

The distance of all the nodes from the root node is: 
2 1 2 1 3 3 0

时间和空间复杂度

以上代码的时间复杂度为O(N)，因为我们使用BFS方法遍历了树的每个节点，其中N是总节点数。

以上代码的空间复杂度为O(N)，因为我们将每个节点距离根节点的距离存储为总节点数N，而且我们使用了额外的空间，形式是一个队列。

结论

在本教程中，我们使用BFS实现了一个C++程序，通过根节点找到二叉树的每个节点距离。我们将程序实现为传统的BFS方式，使用队列遍历每一层，并将下一层的所有值再次添加到队列中以获取全部结果。该程序的时间复杂度是O(N)，与空间复杂度相同，都为线性复杂度，因为我们只访问每个节点一次。