当前位置：极客笔记 > C++ > C++ 精选教程 > C++ 逆时针螺旋形式的层次遍历

C++ 逆时针螺旋形式的层次遍历

C++ 逆时针螺旋形式的层次遍历

二叉树是什么

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

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

    1
   / \
  2   3
 / \ / \
4  5 6  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属性来存储节点的值，以及对其左右子节点的引用。以下伪代码定义了一个Node类，该类表示二叉树中的一个节点，其中包含节点值、左子节点和右子节点的属性。它还定义了一个BinaryTree类，该类表示二叉树，其中包含树的节点属性。

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

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

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

Java Script 代码

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

解释

螺旋形式的层次遍历是一种以螺旋形式而不是线性形式遍历树节点的方式。这意味着每一层的节点以循环的方式访问，从左侧开始向右侧前进，然后返回到右侧再向左侧前进，依此类推。要以螺旋形式执行层次遍历，可以使用与普通层次遍历相似的方法。我们从根节点开始，从左至右访问当前层的节点。然后，对于当前层的每个节点，我们将其子节点添加到一个队列或栈中（在此示例中我们将使用栈）以跟踪下一层的节点。

在访问完当前层的所有节点后，我们切换到下一层，并以相反的方向（从右至左而不是从左至右）访问其节点。然后，对于此层上的每个节点，我们以相反的顺序将其子节点添加到栈中（先右子节点，然后左子节点）。我们以这种方式在层次和方向之间交替进行，直到遍历完树中的所有节点。这将产生一种层次遍历的螺旋形式，每一层的节点以循环的方式访问。

Camera课程

Camera API2 教程

API2 教程
Camera 性能教程

Perf 教程
Camera Native Framework 教程

Native FW 教程
Camera QCOM ISP 教程

ISP 教程
Camera QCOM Sensor 教程

Sensor 教程

Python教程

Python 教程

Python 教程
NumPy 教程

NumPy 教程
Django 教程

Django 教程

Java教程

Java 教程

Java 教程

Web教程

JavaScript 教程

JavaScript 教程
jQuery 教程

jQuery 教程
CSS 教程

CSS 教程
PHP 教程

PHP 教程
Laravel 教程

Laravel 教程
TypeScript 教程

TypeScript 教程
WordPress 教程

WordPress 教程

数据库教程

SQL 教程

SQL 教程
SQLite 教程

SQLite 教程
MySQL 教程

MySQL 教程
PL/SQL 教程

PL/SQL 教程
MongoDB 教程

MongoDB 教程

图形图像教程

OpenCV 教程

OpenCV 教程

办公软件教程

Excel 教程

Excel 教程

Linux教程

Linux命令全集

Linux命令全集
Linux内核API

Linux内核API
LVGL 教程

LVGL 教程

计算机教程

操作系统 教程

操作系统 教程
计算机网络 教程

计算机网络 教程
C语言 教程

C语言 教程
C++ 教程

C++ 教程
Swift 教程

Swift 教程

大数据教程

Hadoop 教程

Hadoop 教程
Spark 教程

Spark 教程
Scala 教程

Scala 教程

开发工具教程

Git 教程

Git 教程
Jenkins 教程

Jenkins 教程
ChatGPT 教程

ChatGPT 教程
IntelliJ 教程

IntelliJ 教程

C++ 精选教程