資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會科學
時尚藝術
法律研究使用 C++ 中的單個佇列實現之字形層次遍歷樹
在此問題中，給出了一個二叉樹。我們的任務是列印樹的之字形層次遍歷。對於此遍歷，我們將只使用一個佇列。
讓我們舉個例子來理解這個問題，
輸出 −
3 1 7 2 8 9 5
要使用單個佇列解決此問題，我們將使用額外的分離標記以及佇列和方向標記。
現在，我們將逐級遍歷樹，插入根元素，現在為佇列的每個元素插入其子節點。如果遇到 NULL，我們將檢查方向，然後按照給定的方向遍歷元素。然後，我們將繼續插入，直到訪問最後一個 NULL。
示例
程式說明我們的解決方案，
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
struct Node* insertNode(int data) {
struct Node* node = new struct Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
void zigZagTraversal(struct Node* root, int n){
struct Node* queue[2 * n];
int top = -1;
int front = 1;
queue[++top] = NULL;
queue[++top] = root;
queue[++top] = NULL;
int prevFront = 0, count = 1;
while (1) {
struct Node* curr = queue[front];
if (curr == NULL) {
if (front == top)
break;
else {
if (count % 2 == 0) {
for (int i = prevFront + 1; i < front; i++)
cout<<queue[i]->data<<"\t";
}
else {
for (int i = front - 1; i > prevFront; i--)
cout<<queue[i]->data<<"\t";
}
prevFront = front;
count++;
front++;
queue[++top] = NULL;
continue;
}
}
if (curr->left != NULL)
queue[++top] = curr->left;
if (curr->right != NULL)
queue[++top] = curr->right;
front++;
}
if (count % 2 == 0) {
for (int i = prevFront + 1; i < top; i++)
cout<<queue[i]->data<<"\t";
}
else {
for (int i = top - 1; i > prevFront; i--)
cout<<queue[i]->data<<"\t";
}
}
int main() {
struct Node* root = insertNode(3);
root->left = insertNode(1);
root->right = insertNode(7);
root->left->left = insertNode(5);
root->left->right = insertNode(9);
root->right->left = insertNode(8);
root->right->right = insertNode(2);
cout<<"Zig Zag traversal of the tree is :\n";
zigZagTraversal(root, 7);
return 0;
}輸出
Zig Zag traversal of the tree is : 3 1 7 2 8 9 5
更新時間： 2020 年 4 月 17 日
206 次瀏覽
廣告