資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究用 C++ 列印樹中節點數為奇數和偶數的所有層
在這個問題中，我們給定一棵樹。我們需要列印所有節點數為偶數和奇數的層。
讓我們舉個例子來更好地理解這個概念。
輸出 -
Levels with odd number of nodes: 1, 3, 4 Levels with even number of nodes: 2
解釋 - 第 1 層只有一個元素（奇數），第 2 層包含兩個元素（偶數），第 3 層包含 3 個元素（奇數），第 4 層包含 1 個元素（偶數）。
現在，為了解決這個問題，我們需要找到每一層的節點數量，並相應地列印奇偶層。
我們將按照以下步驟找到解決方案 -
步驟 1 - 使用 height[node]=1+height[parent] 對每一層執行搜尋演算法。
步驟 2 - 對於每一層，儲存該層上的節點數量。
步驟 3 - 遍歷包含元素的陣列，並列印奇偶層。
示例
#include <bits/stdc++.h>
using namespace std;
void traversal(int node, int parent, int height[], int vis[], vector<int> tree[]){
height[node] = 1 + height[parent];
vis[node] = 1;
for (auto it : tree[node]) {
if (!vis[it]) {
traversal(it, node, height, vis, tree);
}
}
}
void insert(int x, int y, vector<int> tree[]){
tree[x].push_back(y);
tree[y].push_back(x);
}
void evenOddLevels(int N, int vis[], int height[]){
int mark[N + 1];
memset(mark, 0, sizeof mark);
int maxLevel = 0;
for (int i = 1; i <= N; i++) {
if (vis[i])
mark[height[i]]++;
maxLevel = max(height[i], maxLevel);
}
cout << "The levels with odd number of nodes are: ";
for (int i = 1; i <= maxLevel; i++) {
if (mark[i] % 2)
cout << i << " ";
}
cout << "\nThe levels with even number of nodes are: ";
for (int i = 1; i <= maxLevel; i++) {
if (mark[i] % 2 == 0)
cout << i << " ";
}
}
int main(){
const int N = 9;
vector<int> tree[N + 1];
insert(1, 2, tree);
insert(1, 3, tree);
insert(2, 4, tree);
insert(2, 5, tree);
insert(5, 7, tree);
insert(5, 8, tree);
insert(3, 6, tree);
insert(6, 9, tree);
int height[N + 1];
int vis[N + 1] = { 0 };
height[0] = 0;
traversal(1, 0, height, vis, tree);
evenOddLevels(N, vis, height);
return 0;
}輸出
The levels with odd number of nodes are: 1 3 4 The levels with even number of nodes are: 2
更新於: 2020年1月17日
153 次檢視
廣告