資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的 Z 字形樹遍歷
在這個問題中，給定一棵二叉樹。我們的任務是以 Z 字形形式列印二叉樹。
我們舉一個例子來理解這個問題，
上述二叉樹的 Z 字形遍歷為
3 5 1 8 7 0 4
要解決這個問題，我們需要逐層遍歷二叉樹。遍歷順序將在每一層之後進行翻轉。
現在，我們將使用兩個棧（當前和下一個）和一個表示順序的值。首先，我們將從當前層遍歷節點，並將節點從左子節點饋送到右子節點，以便反向返回。再次從當前節點反向。順序變數在顯示要列印的哪一側起著至關重要的作用。
示例
程式演示了我們解決方案的實現，
#include <iostream>
#include <stack>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
void zigZagTreeTraversal(struct Node* root){
if (!root)
return;
stack<struct Node*> currentlevel;
stack<struct Node*> nextlevel;
currentlevel.push(root);
bool LtR = true;
while (!currentlevel.empty()) {
struct Node* temp = currentlevel.top();
currentlevel.pop();
if (temp) {
cout<<temp->data<<"\t";
if (LtR) {
if (temp->left)
nextlevel.push(temp->left);
if (temp->right)
nextlevel.push(temp->right);
}
else {
if (temp->right)
nextlevel.push(temp->right);
if (temp->left)
nextlevel.push(temp->left);
}
}
if (currentlevel.empty()) {
LtR = !LtR;
swap(currentlevel, nextlevel);
}
}
}
struct Node* insertNode(int data){
struct Node* node = new struct Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int main() {
struct Node* root = insertNode(3);
root->left = insertNode(1);
root->right = insertNode(5);
root->left->left = insertNode(8);
root->left->right = insertNode(7);
root->right->left = insertNode(0);
root->right->right = insertNode(4);
cout << "ZigZag traversal of the given binary tree is \n";
zigZagTreeTraversal(root);
return 0;
}輸出
ZigZag traversal of the given binary tree is 3 5 1 8 7 0 4
更新於：17-04-2020
501 次瀏覽
廣告