数据结构
网络
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 次浏览
广告