Java 实现二叉树的后序遍历

悠悠 2024-03-17 09:28 20阅读 0赞

#### 1、定义节点类 ####

class Node {
        
        int val;
        Node left;
        Node right;
        Node(int val) {
        
            this.val = val;
        }
    }
    
    public class BinaryTree {
        
        /**
         * 后序遍历
         * @param root 节点
         */
        public void postorderTraversal(Node root) {
        
            if (root != null) {
        
                postorderTraversal(root.left);
                postorderTraversal(root.right);
                System.out.print(root.val + " ");
            }
        }
    }

##### 1）解析 #####

首先，定义了一个 Node 类表示二叉树的节点。节点包含了一个整型的 val 值，以及左右两个子节点的引用。  
然后，定义了 BinaryTree 类，该类包含了一个方法 postorderTraversal，用于实现后序遍历。  
后序遍历的顺序是：先遍历左子树，然后遍历右子树，最后遍历根节点。  
如果二叉树为空，则直接返回。否则，先输出左子树的值，然后递归遍历右子树和根节点。

##### 2）使用方法 #####

首先创建二叉树的节点，然后构建二叉树，最后调用 BinaryTree 类的 postorderTraversal 方法进行后序遍历。

#### 2、测试代码 ####

public class TestTree {
        
        public static void main(String[] args) {
        
            // 构建二叉树
            Node root = new Node(1);
            root.left = new Node(2);
            root.right = new Node(3);
            root.left.left = new Node(4);
            root.left.right = new Node(5);
    
            // 后序遍历
            BinaryTree bt = new BinaryTree();
            System.out.print("Postorder Traversal: ");
            bt.postorderTraversal(root); // 4 5 2 3 1
        }
    }

#### PS ####

Java 实现 二叉树的 前序遍历：[https://www.cnblogs.com/miracle-luna/p/17368605.html][https_www.cnblogs.com_miracle-luna_p_17368605.html]  
Java 实现 二叉树的 中序遍历：[https://www.cnblogs.com/miracle-luna/p/17368610.html][https_www.cnblogs.com_miracle-luna_p_17368610.html]  
Java 实现 二叉树的 后序遍历：[https://www.cnblogs.com/miracle-luna/p/17368606.html][https_www.cnblogs.com_miracle-luna_p_17368606.html]

[https_www.cnblogs.com_miracle-luna_p_17368605.html]: https://www.cnblogs.com/miracle-luna/p/17368605.html
[https_www.cnblogs.com_miracle-luna_p_17368610.html]: https://www.cnblogs.com/miracle-luna/p/17368610.html
[https_www.cnblogs.com_miracle-luna_p_17368606.html]: https://www.cnblogs.com/miracle-luna/p/17368606.html