树的后序遍历

在这种遍历方法中，根节点最后被访问，因此得名。我们首先遍历左子树，然后遍历右子树，最后遍历根节点。

我们从A开始，按照后序遍历，我们首先访问左子树B。B也进行后序遍历。这个过程一直持续到所有节点都被访问。这棵树的后序遍历输出将是：

D → E → B → F → G → C → A

算法

直到所有节点都被遍历：

Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.

示例

class Node{
   int data;
   Node leftNode, rightNode;
   Node() {
      leftNode = null;
      rightNode = null;     
      this.data = data;
   }
   Node(int data) {
      leftNode = null;
      rightNode = null;     
      this.data = data;
   }
   int getData() {
      return this.data;	   
   }
   Node getleftNode() {
      return this.leftNode;      
   }
   Node getRightNode() {
      return this.leftNode;      
   }
   void setData(int data) {
      this.data = data; 
   }
   void setleftNode(Node leftNode) {
      this.leftNode = leftNode;      
   }
   void setRightNode(Node rightNode) {
      this.leftNode = rightNode;         
   }
}
public class PostOrderBinaryTree {
   public static void main(String[] args) {
      Node node = new Node(50);
      node.leftNode = new Node(60);
      node.leftNode.leftNode = new Node(45);
      node.leftNode.rightNode = new Node(64);

      node.rightNode = new Node(60);
      node.rightNode.leftNode = new Node(45);
      node.rightNode.rightNode = new Node(64);
   
      System.out.println("post-order arrangement of given elements: ");
      postOrder(node);
   }   
   public static void postOrder(Node root) {
      if(root !=null) {
         postOrder(root.leftNode);
         postOrder(root.rightNode);    
         System.out.println(root.data);
      }
   }  
}

输出

post-order arrangement of given elements: 
45
64
60
45
64
60
50