資料結構
網路
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 次瀏覽
廣告