資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學科
時尚研究
法律研究用 C++ 列印二叉樹中兩給定層次之間的所有節點
在這個問題中，我們給定一個二叉樹和樹中的兩個層次（上層和下層），並且必須列印該樹上層和下層之間的所有節點。
二叉樹是一種特殊樹，其每個節點最多有兩個節點（一個/兩個/沒有）。
讓我們舉個例子來理解這個問題 −
上層 − 1
下層 − 3
輸出 −
6 3 9 7 4 8 10
為了解決這個問題，我們必須列印樹中特定層次的節點。我們將使用一個迴圈從樹中的上層 到下層 呼叫遞迴函式。
此演算法很簡單但是更復雜，順序為 n2 。
一種更有效的解決方案是執行中序遍歷並使用佇列。並列印給定的上層和下層內的節點。
實現我們解決方案的程式 −
示例
#include <iostream>
#include <queue>
using namespace std;
struct Node{
int key;
struct Node* left, *right;
};
void printNodesAtLevel(Node* root, int low, int high){
queue <Node *> Q;
Node *marker = new Node;
int level = 1;
Q.push(root);
Q.push(marker);
while (Q.empty() == false){
Node *n = Q.front();
Q.pop();
if (n == marker){
cout << endl;
level++;
if (Q.empty() == true || level > high) break;
Q.push(marker);
continue;
}
if (level >= low)
cout<<n->key<<" ";
if (n->left != NULL) Q.push(n->left);
if (n->right != NULL) Q.push(n->right);
}
}
Node* insertNode(int key){
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
int main() {
struct Node *root = insertNode(6);
root->left = insertNode(3);
root->right = insertNode(9);
root->left->left = insertNode(7);
root->left->right = insertNode(4);
root->left->right->left = insertNode(8);
root->left->right->right = insertNode(10);
root->left->right->right->left = insertNode(5);
root->left->right->right->right = insertNode(1);
root->left->right->left->left = insertNode(14);
root->left->right->left->right = insertNode(26);
int upper = 3;
int lower = 1;
cout << "Level wise Nodes between level "<<lower<<" and "<<upper<<" are \n";
printNodesAtLevel(root, lower, upper);
return 0;
}輸出
Level wise Nodes between level 1 and 3 are 6 3 9 7 4
更新於：22-Jan-2020
161 瀏覽次數
廣告