Vertical Tree Traversal in Java

2025 年 5 月 9 日 | 阅读 9 分钟

Java 垂直树遍历涉及根据二叉树节点与根的水平距离，逐列地组织和打印节点。通过使用 TreeMap 和层序遍历，节点被分组并按垂直顺序显示，确保树的结构化视图。

输入

具有以下结构的二叉树

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

输出

 
[4]  
[2]  
[1, 5, 6]  
[3]  
[7]

解释

节点按其水平距离 (HD) 分组

HD = -2: [4]
HD = -1: [2]
HD = 0: [1, 5, 6]
HD = 1: [3]
HD = 2: [7]

暴力破解法

该方法按水平距离对节点进行分组，并逐层处理它们，以确保二叉树的结构化垂直顺序遍历。

算法

步骤 1: 创建一个 TreeMap 来存储每个水平距离 (HD) 的节点。

步骤 2: 从根开始，将其添加到队列中，HD = 0。

步骤 3: 处理每个节点

将节点的 H D 添加到 TreeMap 中。
将左子节点添加到队列中，HD 减 1；将右子节点添加到队列中，HD 加 1。

步骤 4: 重复此过程，直到所有节点都被处理（队列为空）。

步骤 5: 通过按 HD 顺序从 TreeMap 中读取值来打印结果。

实施

import java.util.*;
// Class representing a Node in the binary tree
class Node {
    int data;        // Value of the node
    Node left, right; // Pointers to the left and right child nodes
    // Constructor to initialize the node with data
    public Node(int data) {
        this.data = data;    // Set the node value
        left = right = null; // Initialize children as null
    }
}
public class VerticalTreeTraversal {
    // Function to perform vertical order traversal of the binary tree
    static void verticalOrder(Node root) {
        // Check if the tree is empty
        if (root == null)
            return; // Exit if there are no nodes to process
        // TreeMap to store nodes based on their horizontal distance (HD)
        TreeMap<Integer, ArrayList<Integer>> map = new TreeMap<>();
        // Queue to perform level-order traversal; stores Pair (Node, HD)
        Queue<Pair> queue = new LinkedList<>();
        // Add the root node to the queue with horizontal distance = 0
        queue.add(new Pair(root, 0)); 
        // Traverse the tree level by level
        while (!queue.isEmpty()) {
            // Remove the front node from the queue
            Pair temp = queue.poll();
            Node currentNode = temp.node; // Extract the current node
            int hd = temp.hd;             // Extract the horizontal distance
            // Add the current node's value to the TreeMap at the corresponding HD
            if (!map.containsKey(hd))      // Check if HD is not already in the map
                map.put(hd, new ArrayList<>()); // Add a new list for this HD
            map.get(hd).add(currentNode.data);  // Append the current node's value
            // Add the left child to the queue with updated HD = current HD - 1
            if (currentNode.left != null)
                queue.add(new Pair(currentNode.left, hd - 1));
            // Add the right child to the queue with updated HD = current HD + 1
            if (currentNode.right != null)
                queue.add(new Pair(currentNode.right, hd + 1));
        }
        // Print the nodes in vertical order by traversing the TreeMap
        for (Map.Entry<Integer, ArrayList<Integer>> entry : map.entrySet()) {
            System.out.println(entry.getValue()); // Print nodes for each HD
        }
    }
    // Pair class to store a Node along with its horizontal distance (HD)
    static class Pair {
        Node node; // The tree node
        int hd;    // The horizontal distance of the node
        // Constructor to initialize the Pair with a node and its HD
        public Pair(Node node, int hd) {
            this.node = node; // Set the node
            this.hd = hd;     // Set the horizontal distance
        }
    }
    // Main method to test the verticalOrder function
    public static void main(String[] args) {
        // Create the binary tree
        Node root = new Node(1);          // Root node with value 1
        root.left = new Node(2);          // Left child of root with value 2
        root.right = new Node(3);         // Right child of root with value 3
        root.left.left = new Node(4);     // Left child of node 2 with value 4
        root.left.right = new Node(5);    // Right child of node 2 with value 5
        root.right.left = new Node(6);    // Left child of node 3 with value 6
        root.right.right = new Node(7);   // Right child of node 3 with value 7
        // Perform vertical order traversal and print the result
        System.out.println("Vertical Order Traversal of Binary Tree:");
        verticalOrder(root);
    }
}   

输出

 
[4]
[2]
[1, 5, 6]
[3]
[7]

时间复杂度: O(N log N)，其中 N 是节点数（由于 TreeMap 插入）。

空间复杂度: O(N)，用于 TreeMap 和队列。

使用二叉树方法

该方法使用层序遍历和队列，根据节点与根的水平距离 (HD) 来分组节点。TreeMap 以排序方式存储每个 HD 的节点，确保了垂直对齐。

算法

步骤 1: 初始化一个 TreeMap 用于按水平距离 (HD) 存储节点，并初始化一个队列用于层序遍历。添加根节点，HD = 0。

步骤 2: 从队列中处理每个节点，将其值添加到其 HD 下方的 TreeMap 中。

步骤 3: 如果存在，将左子节点添加到队列中，HD 减 1；将右子节点添加到队列中，HD 加 1。

步骤 4: 重复此过程，直到队列为空。

步骤 5: 从 TreeMap 中打印按 HD 分组的节点。

实施

import java.util.*; 
// Class representing a tree node
class Node {
    int data; // Data stored in the node
    Node left, right; // Pointers to the left and right child nodes
    // Constructor to initialize a node with data and null children
    public Node(int data) {
        this.data = data; // Assign the data to the node
        left = right = null; // Initialize left and right pointers as null
    }
}
public class VerticalTraversal {
    // Method to perform vertical traversal of a binary tree
    static void verticalTraversal(Node root) {
        if (root == null) return; // If the tree is empty, do nothing and return
        // TreeMap to store nodes grouped by horizontal distance (HD)
        TreeMap<Integer, List<Integer>> map = new TreeMap<>();
        // Queue to support level-order traversal; stores Pair of node and its HD
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(root, 0)); // Start with the root node at HD = 0
        // Loop to perform level-order traversal
        while (!queue.isEmpty()) {
            Pair current = queue.poll(); // Retrieve and remove the front of the queue
            Node node = current.node; // Current node being processed
            int hd = current.hd; // Horizontal distance of the current node
            // Add the node's data to the TreeMap at its horizontal distance
            map.putIfAbsent(hd, new ArrayList<>()); // Create a new list if no list exists for this HD
            map.get(hd).add(node.data); // Add the current node's data to the list
            // If the left child exists, add it to the queue with HD decremented by 1
            if (node.left != null) queue.add(new Pair(node.left, hd - 1));
            // If the right child exists, add it to the queue with HD incremented by 1
            if (node.right != null) queue.add(new Pair(node.right, hd + 1));
        }
        // Loop through the TreeMap to print nodes grouped by horizontal distance
        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
            System.out.println(entry.getValue()); // Print the list of nodes for each HD
        }
    }
    // Pair class to store a node and its horizontal distance (HD)
    static class Pair {
        Node node; // The tree node
        int hd; // Horizontal distance of the node
        // Constructor to initialize the Pair with a node and its HD
        Pair(Node node, int hd) {
            this.node = node; // Assign the node
            this.hd = hd; // Assign the horizontal distance
        }
    }
    // Main method to test the vertical traversal method
    public static void main(String[] args) {
        // Construct the binary tree
        Node root = new Node(1); // Create the root node
        root.left = new Node(2); // Left child of root
        root.right = new Node(3); // Right child of root
        root.left.left = new Node(4); // Left child of node 2
        root.left.right = new Node(5); // Right child of node 2
        root.right.left = new Node(6); // Left child of node 3
        root.right.right = new Node(7); // Right child of node 3
        // Print the vertical traversal of the binary tree
        System.out.println("Vertical Traversal of the Binary Tree:");
        verticalTraversal(root); // Call the vertical traversal method
    }
}   

输出

 
Vertical Traversal of the Binary Tree:
[4]
[2]
[1, 5, 6]
[3]
[7]

时间复杂度: O(N log N)

空间复杂度: O(N)

使用 HashMap 方法

该代码使用 HashMap 来根据节点与根的水平距离 (HD) 对节点进行分组。层序遍历可确保系统地访问节点，并且键 (HD) 被排序以实现有序垂直遍历。

算法

步骤 1: 如果根节点为空，则从函数返回。

步骤 2: 创建一个 HashMap 来存储按水平距离 (HD) 分组的节点。

步骤 3: 使用队列处理节点，并添加其左子节点和右子节点，并更新 HD 值。

步骤 4: 从 HashMap 中提取键 (HD)，并按升序对其进行排序。

步骤 5: 对于每个排序后的 HD，打印存储在 HashMap 中的节点。

实施

import java.util.*; 
// Class representing a node in the binary tree
class Node {
    int data; // Data value of the node
    Node left, right; // References to the left and right child nodes
    // Constructor to initialize the node with a value and null children
    public Node(int data) {
        this.data = data; // Assign the data value
        this.left = this.right = null; // Initialize left and right children as null
    }
}
public class VerticalTraversalUsingHashMap {
    // Function to perform vertical traversal of a binary tree
    static void verticalTraversal(Node root) {
        if (root == null) return; // If the tree is empty, exit the function
        // HashMap to store nodes grouped by their horizontal distance (HD)
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        // Queue for level-order traversal, storing pairs of Node and their HD
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(root, 0)); // Add the root node with horizontal distance 0 to the queue
        // Perform level-order traversal
        while (!queue.isEmpty()) {
            Pair current = queue.poll(); // Dequeue the front element
            Node node = current.node; // Get the current node
            int hd = current.hd; // Get the horizontal distance of the current node
            // Add the current node's data to the list in the map for its horizontal distance
            map.putIfAbsent(hd, new ArrayList<>()); // Create a new list if it doesn't exist
            map.get(hd).add(node.data); // Add the node's data to the list at HD
            // If the left child exists, enqueue it with HD decreased by 1
            if (node.left != null) queue.add(new Pair(node.left, hd - 1));
            // If the right child exists, enqueue it with HD increased by 1
            if (node.right != null) queue.add(new Pair(node.right, hd + 1));
        }
        // Get all the keys (HDs) from the map and sort them
        List<Integer> sortedKeys = new ArrayList<>(map.keySet()); // Extract all HDs into a list
        Collections.sort(sortedKeys); // Sort the HDs in ascending order
        // Print nodes grouped by their horizontal distances
        for (int key : sortedKeys) {
            System.out.println(map.get(key)); // Print the list of nodes at each HD
        }
    }
    // Helper class to store a node and its horizontal distance (HD) as a pair
    static class Pair {
        Node node; // The tree node
        int hd; // Horizontal distance of the node
        // Constructor to initialize a Pair with a node and its HD
        Pair(Node node, int hd) {
            this.node = node; // Assign the node
            this.hd = hd; // Assign the horizontal distance
        }
    }
    // Main method to test the vertical traversal functionality
    public static void main(String[] args) {
        // Create the binary tree
        Node root = new Node(1); // Root node with value 1
        root.left = new Node(2); // Left child of root
        root.right = new Node(3); // Right child of root
        root.left.left = new Node(4); // Left child of node 2
        root.left.right = new Node(5); // Right child of node 2
        root.right.left = new Node(6); // Left child of node 3
        root.right.right = new Node(7); // Right child of node 3
        // Print the vertical traversal of the binary tree
        System.out.println("Vertical Traversal of the Binary Tree:");
        verticalTraversal(root); // Call the function to perform vertical traversal
    }
}   

输出

 
Vertical Traversal of the Binary Tree:
[4]
[2]
[1, 5, 6]
[3]
[7]

下一个话题Java 中的 SexagesimalFormatter

← 上一个下一个 →

Vertical Tree Traversal in Java

暴力破解法

算法

实施

使用二叉树方法

算法

实施

使用 HashMap 方法

算法

实施

联系信息

关注我们

教程

面试题

在线编译器

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

Vertical Tree Traversal in Java

暴力破解法

算法

实施

使用二叉树方法

算法

实施

使用 HashMap 方法

算法

实施

相关帖子

Java 中的 DAO 类

How to Calculate Date Difference in Java

Java 中的 Callable 和 Future

How to Split a String in Java with Delimiter

CharBuffer hasArray() method in Java

Java 中一次性密码生成器代码

Java 泛型的优点

Java Program to Illustrate Use of Binary Literals

Executor Framework Java

Java 中拆分两个字符串以构成回文

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器