Java 中树的垂直锯齿形遍历

17 Mar 2025 | 4 分钟阅读

目标是给出二叉树的垂直锯齿形遍历顺序中的项目结果。树的垂直锯齿形遍历描述如下

从右到左按正确顺序列出第一层的元素；如果没有剩余部分，则移动到下一层。
如果最后一层没有更多元素，则从左到右打印它们。如果没有，则移动到前一层。
只要还有节点要遍历，就遵循之前的指示。

示例 1

输入

Vertical zig-zag traversal of a tree in Java

输出

遍历后的元素顺序是

21, 27, 23, 28, 22, 24, 26, 25

解释

第一步是打印第一层的元素，将按如下方式打印：1。
目前，剩余的树部分由以下给出
继续到第四层，从最左边的元素开始打印，即：7。
现在树变成了
现在，当我们从第二层移动到更高层时，我们应该从最右边的位置开始，元素是：3。
现在树变成了
再次继续到第四层，从最左边的最后一个元素开始打印，即元素 8。
现在树变成了
现在返回到第二层打印，从最右边的元素开始，即 2。一直这样做，直到所有元素都被遍历。

算法

步骤 1：创建一个向量 tree[]，其中第 i 层的树的所有节点都将存储在 tree[i] 中。

步骤 2：取两个指针 p1 和 p2，分别指向第一层和最后一层。

步骤 3：现在，使用这两个指针开始交替打印节点（p2 从左到右，p1 从右到左）。

步骤 4：如果 p1 指向的层中没有更多节点，则移动到下一层；如果 p2 指向的层中没有更多节点，则返回到前一层。

实施

文件名：VerticalZigZag.java

import java.io.*;
import java.util.*;
@SuppressWarnings("unchecked") 
public class VerticalZigZag
{
    static int size = 100000;
    static int max = 0;
    // Tree representation in the adjacency list
    static ArrayList []ZZTree = new ArrayList[size + 1];
    // A Boolean array that indicates every visited vertex
    static boolean []visted_ver = new boolean[size + 1];
    // An integer array to hold each node's level
    static int []node_level = new int[size + 1];
    // Vector array where each node at level i is stored at index ith
    static ArrayList []nodes = new ArrayList[size + 1];
    // A utility function for generating an edge connecting two vertices
    static void Edge(int a, int b)
    {
    	// Include a in b's list
    	ZZTree[a].add(b);
    	// Include a in b's list
    	ZZTree[b].add(a);
    }
    static class Pair
    {
    	int key, val;
    	Pair(int key, int val)
    	{
    		this.key = key;
    		this.val = val;
    	}
    }
    // Updated Breadth-First Interface
    static void bfs(int node)
    {
    	// Establish a {child, parent} queue.
    	Queue<Pair> ch_parent_queue = new LinkedList<>();
    	// Place the root node at the head of the queue and indicate it as visited.
    	ch_parent_queue.add(new Pair(node, 0));
    	nodes[0].add(node);
    	visted_ver[node] = true;
    	node_level[1] = 0;
    	while (ch_parent_queue.size() != 0)
    	{
    		Pair p = ch_parent_queue.poll();
    		visted_ver[p.key] = true;
    	  // Retrieve each of the dequeued vertex s's neighbouring vertices. Place it in queue if any nearby 
    	// hasn't been visited yet.
    	for(int child : (ArrayList<Integer>)ZZTree[p.key])
    	{
    	     if (!visted_ver[child])
    	     {
    		ch_parent_queue.add(new Pair(child, p.key));
    		node_level[child] = node_level[p.key] + 1;
    		max = Math.max(max, node_level[child]);
    		nodes[node_level[child]].add(child);
    	     }
    	}
       }
    }
    static void display()
    {
    	boolean flag = true;
    	// Indications for both the first and final stages
    	int ptr1 = 0, ptr2 = max;
    	// J points to the first node of the level p2, and I points to the last node of level p1.
    	int i = nodes[ptr1].size() - 1, j = 0;
    	// While as there are still nodes to navigate
    	while (ptr1 <= ptr2)
    	{
    	     // Print the nodes in an alternative manner
    	     if (flag)
    	     {
    		// Output the final unexplored node of level p1.
    		System.out.print((int)nodes[ptr1].get(i) + " ");
    		// Proceed to the node before it.
    		i--;
    		// Proceed to the next level if there are no more nodes.
    		if (i < 0) 
    		{
    		    ptr1++;
    		    i = nodes[ptr1].size() - 1;
    		}
    	      }
    	       else
    	       {
    		// Output the level p2's first unvisited node.
    		System.out.print((nodes[ptr2]).get(j) + " ");
    		// Go on to the following node.
    		j++;
    	           // Proceed to the previous level if there are no more nodes.
    		if (j >= nodes[ptr2].size()) 
    		{
    		     ptr2--;
    		      j = 0;
    		}
    	        }
    	        // Change the flag
    	       flag = !flag;
    	       // If every node has been reached
    	       if (ptr1 >= ptr2 && i < j)
    	       {
    		break;
    	        }
    	}
    }
    public static void main(String[] args) 
    {
    	for(int i = 0; i < size + 1; i++)
    	{
    	     ZZTree[i] = new ArrayList();
    	     nodes[i] = new ArrayList();
    	     visted_ver[i] = false;
    	     node_level[i] = 0;
    	}
    	Edge(21, 22);
    	Edge(21, 23);
    	Edge(22, 24);
    	Edge(23, 25);
        Edge(23, 26);
    	Edge(24, 27);
    	Edge(26, 28);
    	// Invoking the altered BFS function
    	System.out.println("The order after traversing: ");
    	bfs(21);
    	display();
    }
}

输出

The order after traversing: 
21 27 23 28 22 24 26 25

复杂度分析

时间复杂度为 O(n)，空间复杂度为 O(n)。

下一主题使用 Lambda 表达式在 Java 中反转字符串的程序

Java 中树的垂直锯齿形遍历

算法

实施

联系信息

关注我们

教程

面试题

在线编译器

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

Java Conversion

Java Misc

Java 中树的垂直锯齿形遍历

算法

实施

相关帖子

Java 中的 Meta Class vs. Class

Java 中的字典类

Java 中的 Aliquot 序列

Java Program to Find Union and Intersection of Two Unsorted Arrays

Java 中的 import 语句

CollationElementIterator setText(String) method in Java with Example

Java 编程要素

JavaTuples 中的 KeyValue 类

如何在 Java 中创建具有特定文件属性的文件

What is Object-Oriented Programming?

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器