数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会科学
时尚研究
法律研究二叉树的逆时针螺旋遍历，C++实现？
逆时针螺旋遍历二叉树是找到一颗树的元素，这些元素遍历之后会形成螺旋，但顺序相反。下图展示了二叉树的逆时针螺旋遍历。
在二叉树中进行螺旋遍历的算法以以下方式工作：
初始化变量 i 和 j，并使值等于 i = 0 且 j 等于变量高度。使用一个标记来检查要打印哪部分。标记最初设置为假。一个循环一直运行到 i < j 为止，打印前半部分，否则打印后半部分，并翻转标记值。此过程一直持续到打印整颗二叉树。
示例
#include <bits/stdc++.h>
using namespace std;
struct Node {
struct Node* left;
struct Node* right;
int data;
Node(int data) {
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
int height(struct Node* root) {
if (root == NULL)
return 0;
int lheight = height(root->left);
int rheight = height(root->right);
return max(1 + lheight, 1 + rheight);
}
void leftToRight(struct Node* root, int level) {
if (root == NULL)
return;
if (level == 1)
cout << root->data << " ";
else if (level > 1) {
leftToRight(root->left, level - 1);
leftToRight(root->right, level - 1);
}
}
void rightToLeft(struct Node* root, int level) {
if (root == NULL)
return;
if (level == 1)
cout << root->data << " ";
else if (level > 1) {
rightToLeft(root->right, level - 1);
rightToLeft(root->left, level - 1);
}
}
int main() {
struct Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->right->left = new Node(5);
root->right->right = new Node(7);
root->left->left->left = new Node(10);
root->left->left->right = new Node(11);
root->right->right->left = new Node(8);
int i = 1;
int j = height(root);
int flag = 0;
while (i <= j) {
if (flag == 0) {
rightToLeft(root, i);
flag = 1;
i++;
} else {
leftToRight(root, j);
flag = 0;
j--;
}
}
return 0;
}输出
1 10 11 8 3 2 4 5 7
更新日期：2019-10-03
123 次浏览
广告