数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 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，并且我们使用了队列这种额外空间。
结论
在本教程中，我们实现了 C++ 程序来使用 BFS 查找二叉树中每个节点到根节点的距离。我们实现了程序，就像传统的 BFS 使用队列工作一样，我们遍历了每一层并将下一层的所有值再次添加到队列中以获取所有值。程序的时间复杂度为 O(N)，是线性的，因为我们只访问每个节点一次，空间复杂度也是一样的。
105 次查看
