C++ 二叉树的逆时针螺旋遍历

2025年3月21日 | 阅读 9 分钟

引言

遍历二叉树涉及以系统化的顺序访问所有给定的节点。逆时针螺旋遍历是遍历二叉树的一种方式。该遍历从根节点开始，然后到最左侧的叶子节点，再到最右侧的叶子节点，以此类推，形成螺旋图案。这种遍历方法为树的遍历技术增添了独特的风格。

历史

二叉树及其遍历的概念在计算机科学早期就已出现。树形数据结构在表示二叉树元素之间的层级关系方面至关重要。遍历树的主要主题是为了高效执行任务和处理其中存储的元素。

逆时针螺旋遍历的概念为我们探索二叉树提供了一种独特的方式。而像中序、前序和后序这样的传统树遍历方法也可以进行遍历，但这种螺旋遍历为树遍历带来了不同的方式。这种遍历方法在诸如树形结构与其它遍历技术的线性方式不同的模式时非常有用。

方法

其概念是使用两个变量，其中i初始化为1，j初始化为树的高度，并运行一个while循环，直到i大于j才停止。我们将使用另一个变量flag并将其初始化为0。在while循环中，我们将检查一个条件，即如果flag == 0，我们将从右到左遍历树，将flag设置为1，然后递增i的值，以便下次访问当前层下面的层。此外，当我们将层从底部向上跨越时，我们将flag设置为0，以便下次我们可以从左到右遍历树，然后递减j的值以到达当前层上面的层。重复整个过程，直到二叉树完全被探索。

C++ 中的实现

示例 1

让我们用一个例子来说明C++中二叉树的逆时针螺旋遍历。

#include <iostream>
#include <deque>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void antiClockwiseSpiralTraversal(TreeNode* root) {
    if (!root) return;

    deque<TreeNode*> nodes;
    nodes.push_back(root);
    bool leftToRight = true;

    while (!nodes.empty()) {
        int levelSize = nodes.size();

        for (int i = 0; i < levelSize; ++i) {
            if (leftToRight) {
                TreeNode* current = nodes.front();
                nodes.pop_front();
                cout << current->val << " ";

                if (current->left) nodes.push_back(current->left);
                if (current->right) nodes.push_back(current->right);
            } else {
                TreeNode* current = nodes.back();
                nodes.pop_back();
                cout << current->val << " ";

                if (current->right) nodes.push_front(current->right);
                if (current->left) nodes.push_front(current->left);
            }
        }

        leftToRight = !leftToRight;
    }
}

int main() {

    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    cout << "Anti-clockwise Spiral Traversal: ";
    antiClockwiseSpiralTraversal(root);

    return 0;
}

输出

Anti-clockwise Spiral Traversal: 1 3 2 4 5 6 7

说明

1. 包含头文件

该代码包含输入/输出操作以及deque容器的必要头文件。

2. 二叉树节点定义

我们有一个名为TreeNode的结构体，表示二叉树中的节点。
每个节点都有一个整数值（val）以及指向其左右子节点的指针。

3. 逆时针螺旋遍历函数

antiClockwiseSpiralTraversal函数帮助我们以逆时针螺旋模式遍历二叉树。
它使用一个deque（双端队列）来存储每一层的节点。
遍历就像在每一层从左到右和从右到左进行。
节点根据从deque的 front 或 back 打印。

4. 主函数

main函数创建了一个具有特定结构的二叉树。
然后，它调用antiClockwiseSpiralTraversal函数以逆时针螺旋模式打印树的节点。
该遍历通过在每一层遵循从左到右和从右到左的方向来创建螺旋图案。

时间和空间复杂度

1. 时间复杂度

时间复杂度为O(N)，其中N是二叉树中的节点数。
在遍历过程中，每个节点只涉及一次。
在最坏的情况下，我们需要遍历所有节点。

2. 空间复杂度

空间复杂度为O(W)，其中W表示二叉树的最大宽度
所需的空间与节点的最大数量成正比。
在最坏的情况下，deque可能存储了当前层的所有节点，那么空间复杂度就与最宽层的宽度成正比。

示例 2

让我们用另一个例子来说明C++中二叉树的逆时针螺旋遍历。

#include <iostream>
#include <deque>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void antiClockwiseSpiralTraversal(TreeNode* root) {
    if (!root) return;

    deque<TreeNode*> nodes;
    nodes.push_back(root);
    bool leftToRight = true;

    while (!nodes.empty()) {
        int levelSize = nodes.size();

        for (int i = 0; i < levelSize; ++i) {
            if (leftToRight) {
                TreeNode* current = nodes.front();
                nodes.pop_front();
                cout << current->val << " ";

                if (current->left) nodes.push_back(current->left);
                if (current->right) nodes.push_back(current->right);
            } else {
                TreeNode* current = nodes.back();
                nodes.pop_back();
                cout << current->val << " ";

                if (current->right) nodes.push_front(current->right);
                if (current->left) nodes.push_front(current->left);
            }
        }

        leftToRight = !leftToRight;
    }
}

int main() {
    // Construct a more complex binary tree
    //               1
    //              / \
    //             2   3
    //            / \   \
    //           4   5   6
    //          / \
    //         7   8
    //        /     \
    //       9       10

    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);
    root->left->left->left = new TreeNode(7);
    root->left->left->right = new TreeNode(8);
    root->left->left->left->left = new TreeNode(9);
    root->left->left->right->right = new TreeNode(10);

    cout << "Anti-clockwise Spiral Traversal: ";
    antiClockwiseSpiralTraversal(root);

    return 0;
}

输出

Anti-clockwise Spiral Traversal: 1 3 2 4 5 6 8 7 9 10

说明

在这个例子中，代码给出了一个名为TreeNode的结构体来表示二叉树中的单个节点。每个节点都有一个数字，并与其左、右“子节点”相连。
遍历逻辑包含一个名为antiClockwiseSpiralTraversal的函数。该函数充当向导，通过以螺旋模式移动来帮助我们以独特的方式探索二叉树。
然后，我们使用“deque”函数，它类似于队列，允许我们从两端添加或删除元素。
该函数遍历每一层，从树的顶部（根）开始。
它以之字形模式移动，从左到右，在向下移动时产生螺旋。

时间和空间复杂度

1. 时间复杂度

时间复杂度为O(N)，其中N是二叉树中的节点数。
在遍历过程中，每个节点只涉及一次。
在最坏的情况下，我们需要遍历所有节点。

2. 空间复杂度

空间复杂度为O(W)，其中W表示二叉树的最大宽度。
所需的空间与节点的最大数量成正比。
在最坏的情况下，deque可能存储了当前层的所有节点，那么空间复杂度就与最宽层的宽度成正比。

示例 3

// Include header file
#include <iostream>
using namespace std;
// C++ program for
// Anticlockwise spiral traversal of a binary tree
// Using recursion

// Binary Tree node
class TreeNode
{
	public: int data;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int data)
	{
		// Set node value
		this->data = data;
		this->left = nullptr;
		this->right = nullptr;
	}
};
// Implement Binary Tree
class BinaryTree
{
	public: TreeNode *root;
	BinaryTree()
	{
		this->root = nullptr;
	}
	// Find height of given binary tree
	int treeHeight(TreeNode *node)
	{
		if (node != nullptr)
		{
			int l = this->treeHeight(node->left) + 1;
			int r = this->treeHeight(node->right) + 1;
			if (l > r)
			{
				return l;
			}
			else
			{
				return r;
			}
		}
		else
		{
			return 0;
		}
	}
	// Display given level from left to right
	void printLeftToRight(TreeNode *node, int level)
	{
		if (node == nullptr)
		{
			return;
		}
		if (level == 1)
		{
			// Print level node
			cout << "  " << node->data;
		}
		else
		{
			// First visit left child
			this->printLeftToRight(node->left, level - 1);
			this->printLeftToRight(node->right, level - 1);
		}
	}
	// Display given level from right to left
	void printRightToLeft(TreeNode *node, int level)
	{
		if (node == nullptr)
		{
			return;
		}
		if (level == 1)
		{
			// Print level node
			cout << "  " << node->data;
		}
		else
		{
			// First visit right child
			this->printRightToLeft(node->right, level - 1);
			this->printRightToLeft(node->left, level - 1);
		}
	}
	// Handles the request of printing
	// anticlockwise spiral of binary tree.
	void antiClockWiseSpiral()
	{
		if (this->root == nullptr)
		{
			cout << "\n Empty Tree " << endl;
		}
		else
		{
			// Start level
			int top = 1;
			// Last level
			int down = this->treeHeight(this->root);
			// This is level indicator (top to down selector)
			bool selection = false;
			// When the top level less than or equal to down level
			while (top <= down)
			{
				if (selection == false)
				{
					// right to left
					this->printRightToLeft(this->root, top);
					// Increase level
					top++;
					// Next is bottom level
					selection = true;
				}
				else
				{
					// left to right
					this->printLeftToRight(this->root, down);
					// Decrease the level
					down--;
					// Next is top level
					selection = false;
				}
			}
		}
	}
};
int main()
{
	BinaryTree *tree = new BinaryTree();
	/*
	         6     
	        / \                        
	       /   \    
	      4     7    
	     / \     \               
	    2   3     12
	       / \    / 
	      10  8  5
	      /    \
	     9     -1
	    -----------------
	    Binary tree   
	*/
	// Add tree node
	tree->root = new TreeNode(6);
	tree->root->left = new TreeNode(4);
	tree->root->left->right = new TreeNode(3);
	tree->root->left->right->left = new TreeNode(10);
	tree->root->left->right->left->left = new TreeNode(9);
	tree->root->left->right->right = new TreeNode(8);
	tree->root->left->right->right->right = new TreeNode(-1);
	tree->root->left->left = new TreeNode(2);
	tree->root->right = new TreeNode(7);
	tree->root->right->right = new TreeNode(12);
	tree->root->right->right->left = new TreeNode(5);
	// Test
	tree->antiClockWiseSpiral();
	return 0;
}

输出

6  7  4  2  3  12  5  8  10  9  -1

说明

1. 二叉树节点定义

在这个例子中，代码定义了TreeNode类，它表示二叉树中的单个节点。
每个节点都分配了一个整数值，并具有指向其左右子节点的指针。

2. 二叉树实现（BinaryTree类）

BinaryTree类用于管理二叉树。
它包含一个根节点，该节点最初设置为nullptr。
该类包含用于确定树的高度以及从左到右或从右到左打印给定层节点的功能。

3. 二叉树的高度

treeHeight函数递归地计算二叉树的高度。此函数返回左子树和右子树之间最大高度加一。

4. 打印层

两个函数printLeftToRight和printRightToLeft用于从左到右和从右到左打印给定层上的节点。

5. 逆时针螺旋遍历

antiClockWiseSpiral函数给出二叉树的逆时针螺旋遍历。
它根据层级使用printLeftToRight和printRightToLeft函数，在它们之间切换。

6. Main函数

main函数创建了一个BinaryTree
使用不同的节点和链接构建了一个示例二叉树。
使用antiClockwiseSpiral函数打印树的逆时针螺旋遍历。

时间和空间复杂度

1. 时间复杂度

时间复杂度为O(N)，其中N是二叉树中的节点数。
在遍历过程中，每个节点只涉及一次。
在最坏的情况下，我们需要遍历所有节点。

2. 空间复杂度

空间复杂度为O(W)，其中W表示二叉树的最大宽度。
所需的空间与节点的最大数量成正比。
在最坏的情况下，deque可能存储了当前层的所有节点，那么空间复杂度就与最宽层的宽度成正比。

结论

如上C++代码所示，逆时针螺旋树遍历算法提供了一种有趣且信息丰富的方式来遍历二叉树的节点。该算法在树的每一层从左到右和从右到左交替进行，形成螺旋图案。我们讨论了该算法的递归和基于类的实现，该算法能够高效地遍历树，同时保持其简单性。

时间复杂度：线性时间复杂度随节点数缩放。

空间复杂度随每层树的最大宽度缩放。

总之，该算法提供了一种有趣且富有创意的二叉树遍历方式。

下一主题Std-filesystem-hard-link-count-in-cpp

C++ 二叉树的逆时针螺旋遍历

引言

历史

方法

C++ 中的实现

示例 1

示例 2

示例 3

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 二叉树的逆时针螺旋遍历

引言

历史

方法

C++ 中的实现

示例 1

示例 2

示例 3

结论

相关帖子

C++ 中的粒子群优化

C++ 中的油漆栅栏算法

C++ 中设计搜索自动完成系统

C++ 中的房屋窃贼

C++ 中的吉斯维特序列

如何在 C++ 中查找两个 multimap 的对称差

C++ STL 中的 match_results length()

C++ 中的 std::execution::read_env

C++ 中的 std::piecewise_construct

C++ 中如何将整个 ASCII 文件读入 std::string？

订阅 Tpoint Tech

联系信息