資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
