螺旋形式的层序遍历

2024年8月28日 | 阅读 15 分钟

什么是二叉树？

二叉树是一种层次组织节点的**数据结构**。每个节点最多有两个子节点，通常是左子节点和右子节点。根节点是树中的最顶层节点，叶节点是树底部没有子节点的节点。

这是一个简单的二叉树示例

这棵二叉树有七个节点，节点 1 作为根节点，节点 4、5、6 和 7 作为叶节点。

这是一个二叉树的伪代码实现

// Define a Node class representing a binary tree node.
class Node {
  // Define properties for the node value left child and right child.
  public int value;
  public Node left;
  public Node right;

  // Define a constructor that initializes the node value and children.
  public Node(int value, Node left, Node right) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

// Define a BinaryTree class that represents a binary tree.
class BinaryTree {
  // Define a property for the root node of the tree.
  public Node root;

  // Define a constructor that initializes the root node.
  public BinaryTree(Node root) {
    this.root = root;
  }
}

什么是层序遍历？

二叉树的层序遍历涉及按特定顺序访问树中的节点。在正常的层序遍历中，我们从根节点开始，向下移动，按从左到右的顺序访问每个层级的节点。在正常的层序遍历中，我们将按以下顺序访问节点：1、2、3、4、5、6、7。这被称为层序遍历，因为我们在移动到下一层之前就访问了树的每一层的节点。

要执行层序遍历，我们可以使用一个队列来存储每一层的节点。我们首先将根节点压入队列，然后从左到右遍历当前层的节点。在访问完当前层的所有节点后，我们移动到下一层。

螺旋形式的层序遍历是一种树遍历类型，它以螺旋模式访问树中的每个节点。这种类型的遍历对于查找两个节点之间的最短路径很有用，因为它允许算法在不回溯的情况下探索所有可能的路径。遍历的螺旋模式也有助于可视化树的结构，因为它允许用户更清楚地看到节点之间的关系。螺旋形式的层序遍历从根节点开始，然后以螺旋模式访问每个节点。算法首先访问根节点，然后顺时针绕树移动，按顺序访问每个节点。访问每个节点后，算法会移动到树的下一层并重复该过程，直到所有节点都被访问。螺旋形式的层序遍历是一种递归算法，这意味着它会反复调用自身，直到所有节点都被访问。

什么是螺旋形式？

在二叉树中，“螺旋形式”以一种**螺旋模式**遍历树中的节点，即对树的每一层，节点按从左到右，然后从右到左，再从左到右，以此类推的顺序被访问。

螺旋形式的二叉树结构

说明

这棵树的螺旋形式的层序遍历将按以下顺序访问节点：1、2、3、4、5、6、7。

这与常规的层序遍历不同，后者将按 1、2、3、4、5、6、7 的顺序访问节点。

要执行二叉树的螺旋形式层序遍历，您可以使用队列和堆栈。您会将根节点添加到队列中，然后执行以下步骤，直到队列为空

从队列中取出顶层元素并将其添加到结果列表中。

如果节点有左子节点，则将其添加到队列中。

如果节点有右子节点，则将其添加到堆栈中。

如果队列为空但堆栈不为空，则从堆栈中弹出所有元素并将它们添加到队列中。

此算法允许您按上述所述的螺旋模式访问每一层的节点。

伪代码

二叉树的层序遍历涉及按特定顺序访问树的节点。在正常的层序遍历中，我们按从左到右的顺序访问每一层的节点。在螺旋形式的层序遍历中，我们按交替方向（从左到右，然后从右到左，依此类推）访问每一层的节点。

// Initialize the queue with the root node
queue.enqueue(root)
// Initialize the direction of traversal to left-to-right
direction = 1
// Loop until the queue is empty
while (the queue is not empty)
  // Calculate the number of nodes in the current level
  count = queue.size()

  // Traverse all the nodes in the current level
  for (i = 1 to count)
    // Dequeue a node from the queue
    node = queue.dequeue()

    // Print the node data
    print(node.data)

    // Enqueue the left and right children of the node, if they exist
    if (node.left) queue.enqueue(node.left)
    if (node.right) queue.enqueue(node.right)

  // Reverse the direction of traversal
  direction = -direction

C++ 代码

// Here we are writing down the C++ programming language code to demonstrate
// the concept of Level order traversal in spiral form with its relevant 
// code and output supported by syntax 
#include <bits/stdc++.h>
using namespace std;
// defining the structure of the node from the below code
struct node {
	int data;
	// assigning the initial nodes to the left and right
	struct node* left;
           // structure node allocated dynamically to right
	struct node* right;
};
// below, we are writing down the void function to return us the value of the root node, level 
// structurally
void printGivenLevel(struct node* root, int level, int ltr);
// defining the height calling recursively with structure node as the parameter
int height(struct node* node);
// structure node dynamics
struct node* newNode(int data);
void printSpiral(struct node* root)
{
    // defining the height for the structure node
	int h = height(root);
	int i;
	bool ltr = false;
// running the for loop to print the level
	for (i = 1; i <= h; i++) {
		printGivenLevel(root, i, ltr);
		ltr = !ltr;
	}
}
// defining the void function to help us with defining the struct, and level from here
void printGivenLevel(struct node* root, int level, int ltr)
{
// conditional solving edge case if the root is null
	if (root == NULL)
		return;
// conditional solving if the level becomes one
	if (level == 1)
		cout << root->data << " ";
// edge case condition if level comes greater than one
	else if (level > 1) {
		if (ltr) {
			printGivenLevel(root->left, level - 1, ltr);
			printGivenLevel(root->right, level - 1, ltr);
		}
		else {
			printGivenLevel(root->right, level - 1, ltr);
			printGivenLevel(root->left, level - 1, ltr);
		}
	}
}
// defining the height function with a return type integer
int height(struct node* node)
{
	if (node == NULL)
		return 0;
// edge case condition if the level becomes greater than one
	else {
		int lheight = height(node->left);
		int rheight = height(node->right);
		if (lheight > rheight)
			return (lheight + 1);
		else
			return (rheight + 1);
	}
}
struct node* newNode(int data)
{
	node* newnode = new node();
	newnode->data = data;
	newnode->left = NULL;
	newnode->right = NULL;

	return (newnode);
}
// The main driver code functionality starts from here
int main()
{
	struct node* root = newNode(1);
	// defining the allocation of the root nodes
	root->left = newNode(2);
	root->right = newNode(3);
	root->left->left = newNode(7);
	root->left->right = newNode(6);
	root->right->left = newNode(5);
	root->right->right = newNode(4);
	// printing the spiral nodes traversal
	printf("Spiral Order traversal of "
		"binary tree is \n");

	printSpiral(root);

	return 0;
// The main driver code functionality ends from here	
    
}

输出

Spiral Order traversal of binary tree is 
1 2 3 4 5 6 7

C 代码

// Here we are writing down the C programming language code to demonstrate
// the concept of Level order traversal in spiral form with its relevant 
// code and output supported by syntax 
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
// defining the structure of the node from the below code
struct node {
	int data;
	// assigning the initial nodes to the left and right
	struct node* left;
	struct node* right;
};
void printGivenLevel(struct node* root, int level, int ltr);
int height(struct node* node);
// structure node dynamics
struct node* newNode(int data);
void printSpiral(struct node* root)
{
    
    // defining the height for the structure node
	int h = height(root);
	int i;
	bool ltr = false;
	// running the for loop to print the level
	for (i = 1; i <= h; i++) {
		printGivenLevel(root, i, ltr);
		ltr = !ltr;
	}
}
// defining the void function to help us with defining the struct, level
void printGivenLevel(struct node* root, int level, int ltr)
{
	if (root == NULL)
		return;
	if (level == 1)
		printf("%d ", root->data);
		// edge case condition if the level becomes greater than one
	else if (level > 1) {
		if (ltr) {
			printGivenLevel(root->left, level - 1, ltr);
			printGivenLevel(root->right, level - 1, ltr);
		}
		else {
			printGivenLevel(root->right, level - 1, ltr);
			printGivenLevel(root->left, level - 1, ltr);
		}
	}
}
// defining the height function with a return type integer
int height(struct node* node)
{
	if (node == NULL)
		return 0;
		// edge case condition if the level becomes greater than one
	else {
		int lheight = height(node->left);
		int rheight = height(node->right);
		if (lheight > rheight)
			return (lheight + 1);
		else
			return (rheight + 1);
	}
}
struct node* newNode(int data)
{
	struct node* node
		= (struct node*)malloc(sizeof(struct node));
	node->data = data;
	node->left = NULL;
	node->right = NULL;

	return (node);
}
// The main driver code functionality starts from here
int main()
{
	struct node* root = newNode(1);
	// defining the allocation of the root nodes
	root->left = newNode(2);
	root->right = newNode(3);
	root->left->left = newNode(7);
	root->left->right = newNode(6);
	root->right->left = newNode(5);
	root->right->right = newNode(4);
	// printing the spiral nodes traversal
	printf("Spiral Order traversal of binary tree is \n");
	printSpiral(root);

	return 0;
// The main driver code functionality ends from here
}

输出

Spiral Order traversal of binary tree is 
1 2 3 4 5 6 7

该算法从访问根节点开始，然后顺时针绕树移动，按顺序访问每个节点。访问每个节点后，算法会移动到树的下一层并重复该过程，直到所有节点都被访问。螺旋形式的层序遍历是一种**高效算法**，因为它**只访问树中的每个节点一次**。这使其成为树结构大且复杂的应用程序的理想选择，允许算法在不回溯的情况下探索所有可能的路径。

C# 算法

// Perform a level order traversal of the given binary tree in spiral form.
// Return a list containing the traversed nodes.
public List<int> SpiralLevelOrderTraversal(TreeNode root)
{
    // Initialize the result list and the queue and stack.
    List<int> result = new List<int>();
    Queue<TreeNode> queue = new Queue<TreeNode>();
    Stack<TreeNode> stack = new Stack<TreeNode>();

    // Add the root node to the queue.
    queue.Enqueue(root);

    // Perform the spiral traversal.
    while (queue.Count > 0 || stack.Count > 0)
    {
        // Take the top element from the queue and add it to the result list.
        TreeNode current = queue.Dequeue();
        result.Add(current.val);

        // If the node has a left child, add it to the queue.
        if (current.left != null)
        {
            queue.Enqueue(current.left);
        }

        // If the node has a right child, add it to the stack.
        if (current.right != null)
        {
            stack.Push(current.right);
        }

        // If the queue is empty and the stack is not, pop all elements from the stack
        // and add them to the queue.
        if (queue.Count == 0 && stack.Count > 0)
        {
            while (stack.Count > 0)
            {
                queue.Enqueue(stack.Pop());
            }
        }
    }

    // Return the result list.
    return result;
}

C# 中算法的解释

请注意，此实现假定您有一个 TreeNode 类，该类代表二叉树中的一个节点，并具有 val、left 和 right 属性，这些属性分别存储节点的值以及对其左子节点和右子节点的引用。此伪代码定义了一个 Node 类，代表二叉树中的一个节点，具有节点值、左子节点和右子节点属性。它还定义了一个 BinaryTree 类，代表二叉树，具有树的节点属性。

要使用此实现，您可以创建一个 BinaryTree 对象，并将代表根节点的 Node 对象传递给构造函数来创建二叉树。然后，您可以将父节点的 left 和 right 属性设置为引用左子节点和右子节点来向树添加节点。

Java 代码

// Define a node class to represent a node in the tree.
class Node {
	int data;
	Node left, right;

	public Node(int d)
	{
		data = d;
		left = right = null;
	}
}
// Define a class to represent the tree
class BinaryTree {
	Node root;

	// This method performs a level order traversal in spiral form.
    // It starts at the root node and prints the data in each node,
    // in spiral order.
	void printSpiral(Node node)
	{
		int h = height(node);
		int i;

		boolean ltr = false;
		for (i = 1; i <= h; i++) {
			printGivenLevel(node, i, ltr);

		
			ltr = !ltr;
		}
	}
// If the current level stack is empty, it means we have
            //I finished visiting all the nodes on the current level, so
            // we need to switch to the next level.
	
	int height(Node node)
	{
		if (node == null)
			return 0;
		else {

			
			int lheight = height(node.left);
			int rheight = height(node.right);

			
			if (lheight > rheight)
				return (lheight + 1);
			else
				return (rheight + 1);
		}
	}


	void printGivenLevel(Node node, int level, boolean ltr)
	{
	    // We will use two stacks to keep track of the nodes to visit.
        // One stack will hold the nodes on the current level, and the
        // other will hold the nodes on the next level.
		if (node == null)
			return;
		if (level == 1)
			System.out.print(node.data + " ");
		else if (level > 1) {
		     // Add the node's children to the next level stack in the
            // appropriate order depending on whether we are currently
            // traversing the current level from left to right or from
            // right to left.
			if (ltr != false) {
				printGivenLevel(node.left, level - 1, ltr);
				printGivenLevel(node.right, level - 1, ltr);
			}
			else {
				printGivenLevel(node.right, level - 1, ltr);
				printGivenLevel(node.left, level - 1, ltr);
			}
		}
	}
	
	public static void main(String[] args)
	{
		BinaryTree tree = new BinaryTree();
		tree.root = new Node(1);
		tree.root. left = new Node(2);
		tree.root.right = new Node(3);
		tree.root.left.left = new Node(7);
		tree.root.left.right = new Node(6);
		tree.root.right.left = new Node(5);
		tree.root.right.right = new Node(4);
		System.out.println(
			"Spiral order traversal of Binary Tree is ");
		tree.printSpiral(tree.root);
	}
}

输出

The spiral order traversal of Binary Tree is 1 2 3 4 5 6 7

此外，遍历的螺旋模式有助于可视化树的结构，因为它允许用户更清楚地看到节点之间的关系。总而言之，螺旋形式的层序遍历是一种树遍历类型，它以螺旋模式访问树中的每个节点。这种类型的遍历对于查找两个节点之间的最短路径很有用，因为它允许算法在不回溯的情况下探索所有可能的路径。此外，遍历的螺旋模式有助于可视化树的结构，因为它允许用户更清楚地看到节点之间的关系。

JavaScript 代码

function levelOrderSpiral(root) {
  if (!root) return;

  // Create an empty queue for level order traversal
  let queue = [];

  // Push the root node
  queue.push(root);

  // Track the direction of traversal. We start from left to right
  let direction = 1;

  // Run while the queue is not empty
  while (queue.length > 0) {
    // Calculate the number of nodes in current level
    let count = queue.length;

    // Traverse all nodes of current level
    for (let i = 0; i < count; i++) {
      // Dequeue a node from queue
      let node = queue.shift();

      // Print the node data
      console.log(node.data);

      // Enqueue left child
      if (node.left) queue.push(node.left);

      // Enqueue right child
      if (node.right) queue.push(node.right);
    }

    // Reverse the direction
    direction *= -1;
  }
}

说明

在这里，我们使用一个队列来存储每一层的节点，并使用一个变量 direction 来跟踪遍历的方向（从左到右或从右到左）。在每一层的末尾，我们反转方向。如果使用二叉树的根节点调用此函数，它将以螺旋层序打印树中所有节点的数据。

如果树看起来像下面的样子，那么输出是

输出

JavaScript 中的层序遍历

在常规的层序遍历中，我们将按以下顺序访问节点：1、2、3、4、5、6、7。

在螺旋形式的层序遍历中，我们将按以下顺序访问节点：1、3、2、4、5、6、7。

要执行螺旋形式的层序遍历，我们可以使用一个队列来存储每一层的节点。我们首先将根节点压入队列，然后从左到右（或从右到左，取决于遍历方向）遍历当前层的节点。在访问完当前层的所有节点后，我们反转遍历方向并移动到下一层。此算法的时间复杂度为 O(n)，其中 n 是树中的节点数，因为我们**只访问树中的每个节点一次**。它还具有 O(n) 的空间复杂度，因为我们使用队列来存储每一层的节点。

Python 代码

class newNode:
 # Define a Node class to represent a node in the tree.

	def __init__(self, key):
		self.data = key
		self.left = None
		self.right = None


 # This method performs a level order traversal in spiral form.
    # It starts at the root node and prints the data in each node,
    # in spiral order.


def printSpiral(root):
# Define a Tree class to represent the tree.
	h = height(root)


	ltr = False
	for i in range(1, h + 1):

		printGivenLevel(root, i, ltr)

		ltr = not ltr

# We will use two stacks to keep track of the nodes to visit.
        # One stack will hold the nodes on the current level, and the
        # other will hold the nodes on the next level.



def printGivenLevel(root, level, ltr):
    
    # Keep track of whether we are traversing the current level from
        # left to right or from right to left. Initially, we start from
        # left to right.

	if(root == None):
		return
	if(level == 1):
		print(root.data, end=" ")
	elif (level > 1):

		if(ltr):
			printGivenLevel(root.left, level - 1, ltr)
			printGivenLevel(root.right, level - 1, ltr)
# Add the node's children to the next level stack, in the
            # appropriate order depending on whether we are currently
            # traversing the current level from left to right or from
            # right to left.
		else:
			printGivenLevel(root.right, level - 1, ltr)
			printGivenLevel(root.left, level - 1, ltr)


 


def height(node):

	if (node == None):
		return 0
	else:

	
		lheight = height(node.left)
		rheight = height(node.right)

	 # If the current level stack is empty, it means we have
            # finished visiting all the nodes on the current level, so
            # we need to switch to the next level.	
		if (lheight > rheight):
			return(lheight + 1)
		else:
			return(rheight + 1)



if __name__ == '__main__':
	root = newNode(1)
	root.left = newNode(2)
	root.right = newNode(3)
	root.left.left = newNode(7)
	root.left.right = newNode(6)
	root.right.left = newNode(5)
	root.right.right = newNode(4)
	print("Spiral Order traversal of binary tree is")
	printSpiral(root)

输出

Spiral order traversal of Binary Tree is 1 2 3 4 5 6 7

说明

螺旋形式的层序遍历是一种按层序遍历树节点的方式，但采用的是螺旋模式而不是线性模式。这意味着每一层的节点都以循环模式访问，从左到右，然后从右到左，依此类推。要执行螺旋形式的层序遍历，我们可以采用与常规层序遍历类似的方法。我们从根节点开始，按从左到右的顺序访问当前层的节点。然后，对于当前层的每个节点，我们将它的子节点添加到队列或堆栈（在本例中我们将使用堆栈）中，以跟踪下一层的节点。

在访问完当前层的所有节点后，我们切换到下一层，并以相反的方向（从右到左而不是从左到右）访问其节点。然后，对于该层的每个节点，我们将它的子节点以相反的顺序添加到堆栈中（先右子节点，再左子节点）。我们一直这样在层和方向之间交替，直到访问完树中的所有节点。这将导致一种螺旋模式的遍历，其中每一层的节点都以循环方式访问。

下一个主题scanf() 之后有 fgets()/gets()/scanf() 时的 scanf() 问题

← 上一个下一个 →

螺旋形式的层序遍历

什么是二叉树？

联系信息

关注我们

教程

面试题

在线编译器

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++ 全局常量

C++ 最大圆形子数组和

使用 C++ 进行算法交易

C++ 与 Rust 的区别

C++ 中打印向量元素的各种方法

C/C++ iswblank() 函数

C++ 静态变量

C++ 二分法

C++ 对象指针

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器