Tree Boundary Traversal in Java

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

树边界遍历是一种二叉树遍历的专用技术，其中节点以特定顺序访问，以覆盖树的外部边界。在此遍历中，我们的目标是访问位于树外围的节点，包括左边界、所有叶节点和右边界。遍历遵循结构化方法，涵盖

左边界（从上到下，不包括叶节点），
叶节点（跨所有级别的从左到右），
右边界（从下到上，不包括叶节点）。

此遍历对于可视化树的轮廓很有用，并且可以应用于图形表示、分层数据处理和空间结构等应用。

算法

步骤 1： 打印根节点的值（如果它不为 null）。

步骤 2： 沿着左边缘向下遍历，打印非叶节点，直到到达最左边的边界。

步骤 3： 通过遍历左子树和右子树，从左到右打印所有叶节点。

步骤 4： 沿着树的右边缘自下而上遍历，打印非叶节点，直到到达根节点。

步骤 5： 这将显示树的完整边界遍历。

实施

文件名：BinaryTree.java

// Class representing a single node in a binary tree
class TreeNode {
    int value; // Stores the value of the node
    TreeNode leftChild, rightChild; // Pointers to left and right children of the node
    // Constructor to initialize a node with a value
    TreeNode(int value) {
        this.value = value;
        leftChild = rightChild = null; // Initialize children as null
    }
}
// Class representing a binary tree and its boundary traversal methods
class BinaryTree {
    TreeNode root; // Root node of the binary tree
    // Method to print all leaf nodes (nodes with no children)
    void printLeafNodes(TreeNode node) {
        if (node == null) // Base case: if node is null, return
            return;
        printLeafNodes(node.leftChild); // Recursive call to traverse the left subtree
        // If node is a leaf (no children), print its value
        if (node.leftChild == null && node.rightChild == null)
            System.out.print(node.value + " ");
        printLeafNodes(node.rightChild); // Recursive call to traverse the right subtree
    }
    // Method to print the left boundary of the binary tree, excluding leaf nodes
    void printLeftBoundary(TreeNode node) {
        if (node == null) // Base case: if node is null, return
            return;
        // If there is a left child, print the node and proceed to the left
        if (node.leftChild != null) {
            System.out.print(node.value + " ");
            printLeftBoundary(node.leftChild);
        }
        // If no left child, check and move to the right child
        else if (node.rightChild != null) {
            System.out.print(node.value + " ");
            printLeftBoundary(node.rightChild);
        }
    }
    // Method to print the right boundary of the binary tree, excluding leaf nodes
    void printRightBoundary(TreeNode node) {
        if (node == null) // Base case: if node is null, return
            return;
        // If there is a right child, process it first to maintain bottom-up order
        if (node.rightChild != null) {
            printRightBoundary(node.rightChild);
            System.out.print(node.value + " ");
        }
        // If no right child, check and move to the left child
        else if (node.leftChild != null) {
            printRightBoundary(node.leftChild);
            System.out.print(node.value + " ");
        }
    }
    // Method to print the boundary of the binary tree
    void printBoundary(TreeNode node) {
        if (node == null) // If the tree is empty, return
            return;
        System.out.print(node.value + " "); // Print the root node
        printLeftBoundary(node.leftChild); // Print the left boundary in top-down order
        printLeafNodes(node.leftChild); // Print all leaf nodes in the left subtree
        printLeafNodes(node.rightChild); // Print all leaf nodes in the right subtree
        printRightBoundary(node.rightChild); // Print the right boundary in bottom-up order
    }
    // Main method to create and test the boundary traversal
    public static void main(String args[]) {
        BinaryTree tree = new BinaryTree();
        // Construct the binary tree by assigning new values to the nodes
        tree.root = new TreeNode(15);
        tree.root.leftChild = new TreeNode(10); 
        tree.root.leftChild.leftChild = new TreeNode(5); 
        tree.root.leftChild.rightChild = new TreeNode(12); 
        tree.root.leftChild.rightChild.leftChild = new TreeNode(11); 
        tree.root.leftChild.rightChild.rightChild = new TreeNode(13); 
        tree.root.rightChild = new TreeNode(20); 
        tree.root.rightChild.rightChild = new TreeNode(25);
        // Call the printBoundary method to display the boundary traversal
        tree.printBoundary(tree.root);
    }
}   

输出

 
15 10 5 11 13 25 20

时间复杂度： O(N)，其中 N 是树中的节点数。

辅助空间复杂度： O(H)，其中 H 是树的高度。

逆时针边界遍历

逆时针边界遍历是一种以逆时针方向遍历二叉树边界节点的技术。它涉及按顺序收集节点：根、左边界（不包括叶节点）、叶节点（从左到右）和右边界（不包括叶节点，逆序）。

算法

步骤 1： 如果根节点不是叶节点，则将其添加到边界列表中。

步骤 2： 从根节点的左子节点开始，沿着左边缘（不包括叶节点）将每个节点添加到边界列表，如果可能则移动到左子节点，否则移动到右子节点。

步骤 3： 遍历整个树以查找所有叶节点（没有子节点的节点）并将其添加到边界列表中。

步骤 4： 从根节点的右子节点开始，将沿右边缘（不包括叶节点）的每个节点添加到堆栈中，如果可能则移动到右子节点，否则移动到左子节点。

步骤 5： 按相反顺序将堆栈中的节点添加到边界列表中，以完成边界遍历。

实施

文件名：BinaryTree.java

import java.util.ArrayList; // Import ArrayList for storing boundary nodes
import java.util.Stack; // Import Stack for processing right boundary nodes in reverse order
// Class representing the Binary Tree structure
class BinaryTree {
    TreeNode root; // Root node of the binary tree
    // Static nested class representing a tree node
    static class TreeNode {
        int value; // Stores the value of the node
        TreeNode leftChild, rightChild; // References to left and right child nodes
        // Constructor to initialize a node with a given value
        TreeNode(int value) {
            this.value = value;
            leftChild = rightChild = null; // Initialize children as null
        }
    }
    // Method to check if a node is a leaf (no children)
    private boolean isLeaf(TreeNode node) {
        return node.leftChild == null && node.rightChild == null; 
    }
    // Method to add left boundary nodes to the list (excluding leaf nodes)
    private void addLeftBoundary(TreeNode node, ArrayList<Integer> boundaryNodes) {
        node = node.leftChild; // Start from the left child of root
        while (node != null) { // Traverse down the left boundary
            if (!isLeaf(node)) {
                boundaryNodes.add(node.value);
            }
            if (node.leftChild != null) { // Move to the left child if it exists
                node = node.leftChild;
            } else { // If no left child, move to the right child
                node = node.rightChild;
            }
        }
    }
    // Method to add right boundary nodes to the list (excluding leaf nodes)
    private void addRightBoundary(TreeNode node, ArrayList<Integer> boundaryNodes) {
        node = node.rightChild; // Start from the right child of root
        Stack<Integer> stack = new Stack<>(); // Stack to reverse the order of right boundary nodes
        while (node != null) { // Traverse down the right boundary
            if (!isLeaf(node)) {
                stack.push(node.value);
            }
            if (node.rightChild != null) { // Move to the right child if it exists
                node = node.rightChild;
            } else { // If no right child, move to the left child
                node = node.leftChild;
            }
        }
        while (!stack.isEmpty()) { // Pop all elements from the stack to reverse the order
            boundaryNodes.add(stack.pop()); // Add each element to the list in reverse order
        }
    }
    // Method to add all leaf nodes to the list
    private void addLeafNodes(TreeNode node, ArrayList<Integer> boundaryNodes) {
        if (node == null) {
            return;
        }
        if (isLeaf(node)) {
            boundaryNodes.add(node.value); // Add the leaf node value to the list
        } else { // Recursive calls to process left and right children
            addLeafNodes(node.leftChild, boundaryNodes); // Add leaves in the left subtree
            addLeafNodes(node.rightChild, boundaryNodes); // Add leaves in the right subtree
        }
    }
    // Method to get the boundary traversal of the binary tree
    ArrayList<Integer> getBoundary(TreeNode node) {
        ArrayList<Integer> boundaryNodes = new ArrayList<>(); // List to store boundary nodes
        if (node == null) { // If the root is null, return an empty list
            return boundaryNodes;
        }
        if (!isLeaf(node)) { // Check if root is not a leaf
            boundaryNodes.add(node.value); // Add root node to boundary if not a leaf
        }
        addLeftBoundary(node, boundaryNodes); // Add left boundary nodes
        addLeafNodes(node, boundaryNodes); // Add all leaf nodes
        addRightBoundary(node, boundaryNodes); // Add right boundary nodes
        return boundaryNodes; // Return the final boundary traversal list
    }
    // Main method to create a binary tree and display its boundary traversal
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        // Construct the binary tree by assigning values to nodes
        tree.root = new TreeNode(50);
        tree.root.leftChild = new TreeNode(30);
        tree.root.leftChild.leftChild = new TreeNode(10);
        tree.root.leftChild.rightChild = new TreeNode(40);
        tree.root.leftChild.rightChild.leftChild = new TreeNode(35);
        tree.root.leftChild.rightChild.rightChild = new TreeNode(45); 
        tree.root.rightChild = new TreeNode(70);
        tree.root.rightChild.rightChild = new TreeNode(90);
        ArrayList<Integer> boundaryNodes = tree.getBoundary(tree.root); // Get boundary traversal
        // Print the boundary traversal nodes
        for (int value : boundaryNodes) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}   

输出

 
50 30 10 35 45 90 70

时间复杂度： O(N)，其中 N 是节点数。

辅助空间复杂度： O(H)，其中 H 是树的高度。

使用 Morris 遍历方法

Morris 遍历是一种中序遍历方法，它通过在二叉树中创建临时链接（线程）来避免递归或堆栈。它能够以O(1)的辅助空间进行高效遍历，同时在过程结束后保留树的结构。

算法

步骤 1： 从根节点开始。打印其值。

步骤 2： 沿着树的左侧向下移动，打印非叶节点。

步骤 3： 遍历整个树（左子树和右子树），并打印所有叶节点。

步骤 4： 沿着树的右侧向下移动，存储非叶节点。以相反的顺序打印它们。

步骤 5： 将根节点、左边界、叶节点和右边界（逆序）的值组合起来，得到完整的边界遍历。

实施

文件名：BinaryTree.java

import java.util.*; // Import the necessary Java utilities
// Define the TreeNode class representing a node in the binary tree
class TreeNode {
    int value; // Value of the node
    TreeNode leftChild, rightChild; // Pointers to the left and right children
    // Constructor to initialize the node with a specific value
    TreeNode(int value) {
        this.value = value; // Set the value of the node
        this.leftChild = this.rightChild = null; // Initialize children as null
    }
}
// Define the BinaryTree class containing methods for boundary traversal
class BinaryTree {
    // Method to print the left boundary nodes, excluding leaf nodes
    static void printLeftBoundary(TreeNode node) {
        if (node == null) {
            return;
        }
        if (node.leftChild != null || node.rightChild != null) {
            System.out.print(node.value + " ");
        }
        if (node.leftChild != null) { // If left child exists, recurse left
            printLeftBoundary(node.leftChild);
        } else { // If no left child, move to right child
            printLeftBoundary(node.rightChild);
        }
    }
    // Method to print the right boundary nodes, excluding leaf nodes
    static void printRightBoundary(TreeNode node) {
        if (node == null) {
            return;
        }
        if (node.rightChild != null) { // If right child exists, recurse right
            printRightBoundary(node.rightChild);
        } else { // If no right child, move to left child
            printRightBoundary(node.leftChild);
        }
        if (node.leftChild != null || node.rightChild != null) {
            System.out.print(node.value + " ");
        }
    }
    // Method to print all leaf nodes in the binary tree
    static void printLeaves(TreeNode node) {
        if (node == null) {
            return;
        }
        printLeaves(node.leftChild); // Recursively print leaves in left subtree
        if (node.leftChild == null && node.rightChild == null) {
            System.out.print(node.value + " ");
        }
        printLeaves(node.rightChild); // Recursively print leaves in right subtree
    }
    // Method to print the boundary traversal of the binary tree in an anti-clockwise order
    static void printBoundary(TreeNode node) {
        if (node == null) { // Base case: if the tree is empty, return
            return;
        }
        System.out.print(node.value + " "); // Print the root node
        printLeftBoundary(node.leftChild); // Print the left boundary
        printLeaves(node.leftChild); // Print the leaves in the left subtree
        printLeaves(node.rightChild); // Print the leaves in the right subtree
        printRightBoundary(node.rightChild); // Print the right boundary
    }
    // Main method to demonstrate boundary traversal of a binary tree
    public static void main(String[] args) {
        TreeNode root = new TreeNode(50); // Create the root node with value 50
        root.leftChild = new TreeNode(30); // Set left child of root to 30
        root.leftChild.leftChild = new TreeNode(10); // Set left child of 30 to 10
        root.leftChild.rightChild = new TreeNode(40); // Set right child of 30 to 40
        root.leftChild.rightChild.leftChild = new TreeNode(35); // Set left child of 40 to 35
        root.leftChild.rightChild.rightChild = new TreeNode(45); // Set right child of 40 to 45
        root.rightChild = new TreeNode(70); // Set right child of root to 70
        root.rightChild.rightChild = new TreeNode(90); // Set right child of 70 to 90
        printBoundary(root); // Perform and print boundary traversal of the tree
    }
} 

输出

 
50 30 10 35 45 90 70

时间复杂度： O(N)，其中 N 是节点数。

辅助空间： O(H)，其中 H 是树的高度。

下一主题& vs && in Java

Tree Boundary Traversal in Java

算法

实施

逆时针边界遍历

算法

实施

使用 Morris 遍历方法

算法

实施

联系信息

关注我们

教程

面试题

在线编译器

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

Tree Boundary Traversal in Java

算法

实施

逆时针边界遍历

算法

实施

使用 Morris 遍历方法

算法

实施

相关帖子

Java 中的并行流

如何在 Java 中查找整数的长度

Java CloudWatch API

Java 中的 Profile 注解

Java 编程认证

如何在 Java 中将文件转换为十六进制

检查给定字符串是否为偶奇回文（Java）

Java SHA

Java 8 中的 Spliterator

Java 中的 Sylvester 序列

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器