当前位置：极客教程 > C++语言 > C++ 教程 > 螺旋形式的层次顺序遍历

螺旋形式的层次顺序遍历

螺旋形式的层次顺序遍历

什么是二叉树?

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

下面是一个二叉树的简单例子:

    1
   / \
  2   3
 / \ / \
4  5 6  7

该二叉树有7个节点，节点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。

这与普通的层次遍历不同，后者会以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 
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 
#include 
#include 
// 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 SpiralLevelOrderTraversal(TreeNode root)
{
    // Initialize the result list and the queue and stack.
    List result = new List();
    Queue queue = new Queue();
    Stack stack = new Stack();

    // 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属性分别存储该节点的值，并引用该节点的左子节点和右子节点。这个伪代码定义了一个表示二叉树中节点的节点类，具有节点值、左子节点和右子节点的属性。它还定义了一个表示binary are的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来跟踪遍历的方向(从左到右或从右到左)。在每一层的末尾，我们反转方向。如果用二叉树的根节点调用这个函数，它会以螺旋级顺序打印树中所有节点的数据。

如果树如下所示，则输出为

    1
   / \
  2   3
 / \ / \
4  5 6  7

输出:

1
3
2
4
5
6
7

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

解释

螺旋形式的层次顺序遍历是一种以层次顺序遍历树节点的方法，但以螺旋模式而不是线性模式。这意味着每一层上的节点都是以圆形的模式访问的，从左到右，然后再回到右再到左，以此类推。要执行螺旋形式的层次顺序遍历，我们可以使用与普通的层次顺序遍历类似的方法。我们从根节点开始，从左到右访问当前层上的节点。然后，对于当前层的每个节点，我们将其子节点添加到队列或堆栈(在本例中我们将使用堆栈)，以跟踪下一层的节点。

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

Python教程

Python 教程

Python 教程
Tkinter 教程

Tkinter 教程
Pandas 教程

Pandas 教程
NumPy 教程

NumPy 教程
Flask 教程

Flask 教程
Django 教程

Django 教程
PySpark 教程

PySpark 教程
wxPython 教程

wxPython 教程
SymPy 教程

SymPy 教程
Seaborn 教程

Seaborn 教程
SciPy 教程

SciPy 教程
RxPY 教程

RxPY 教程
Pycharm 教程

Pycharm 教程
Pygame 教程

Pygame 教程
PyGTK 教程

PyGTK 教程
PyQt 教程

PyQt 教程
PyQt5 教程

PyQt5 教程
PyTorch 教程

PyTorch 教程
Matplotlib 教程

Matplotlib 教程
Web2py 教程

Web2py 教程
BeautifulSoup 教程

BeautifulSoup 教程

Java教程

Java 教程

Java 教程

Web教程

HTML 教程

HTML 教程
CSS 教程

CSS 教程
CSS3 教程

CSS3 教程
jQuery 教程

jQuery 教程
Ajax 教程

Ajax 教程
AngularJS 教程

AngularJS 教程
TypeScript 教程

TypeScript 教程
WordPress 教程

WordPress 教程
Laravel 教程

Laravel 教程
Next.js 教程

Next.js 教程
PhantomJS 教程

PhantomJS 教程
Three.js 教程

Three.js 教程
Underscore.JS 教程

Underscore.JS 教程
WebGL 教程

WebGL 教程
WebRTC 教程

WebRTC 教程
VueJS 教程

VueJS 教程

数据库教程

SQL 教程

SQL 教程
MySQL 教程

MySQL 教程
MongoDB 教程

MongoDB 教程
PostgreSQL 教程

PostgreSQL 教程
SQLite 教程

SQLite 教程
Redis 教程

Redis 教程
MariaDB 教程

MariaDB 教程

图形图像教程

Vulkan 教程

Vulkan 教程
OpenCV 教程

OpenCV 教程

大数据教程

R语言 教程

R语言 教程

开发工具教程

Git 教程

Git 教程
VSCode 教程

VSCode 教程
Docker 教程

Docker 教程
Gerrit 教程

Gerrit 教程
Excel 教程

Excel 教程

计算机教程

Go语言 教程

Go语言 教程
C++ 教程

C++ 教程

C++ 教程