Java：显示前序和后序遍历

Question

在过去的一段时间里，我一直在处理Binary Trees。我似乎遇到麻烦的一项任务是显示BinaryTree类的preOrderTraversal和postOrderTraversal方法。目前，我只能显示displayInOrder方法。我能做些什么来解决这个错误？

public class BinaryTree { 
BinaryTreeNode root = null; 

public void insertInTree (int newData) { 
    if (root == null) 
     root = new BinaryTreeNode(newData); 
    else root.insert(newData); 
    } 


    public void displayInOrder() { 
     displayInOrder (root); 
    } 

    public void preOrderTraversal() { 
     preOrderTraversal (root); 
    } 

    public void postOrderTraversal() { 
     postOrderTraversal (root); 
    } 

    public void preOrderTraversal (BinaryTreeNode subRoot) { 
     if (subRoot == null) return; 
     preOrderTraversal(subRoot.getLeft()); 
     System.out.println(" " + subRoot.getData() + " "); 
     preOrderTraversal(subRoot.getRight()); 
    } 

    public void postOrderTraversal (BinaryTreeNode subRoot) { 
     if (subRoot == null) return; 
     postOrderTraversal(subRoot.getLeft()); 
     System.out.println(" " + subRoot.getData() + " "); 
     postOrderTraversal(subRoot.getRight()); 
    } 

    public void displayInOrder (BinaryTreeNode subRoot){ 
     if (subRoot == null) return; 
     displayInOrder (subRoot.getLeft()); 
     System.out.print(" " + subRoot.getData() + " "); 
     displayInOrder (subRoot.getRight()); 

    } 


    } 

public class BinaryTreeNode { 
private int data; 
private BinaryTreeNode left; 
private BinaryTreeNode right; 

public BinaryTreeNode() { 
    left = null; right = null; data = 0; 
} 
public BinaryTreeNode(int data) { 
    left = null; right = null; this.data = data; 
} 
public int getData() { 
    return data; 
} 
public BinaryTreeNode getLeft() { 
    return left; 
} 
public BinaryTreeNode getRight() { 
    return right; 
} 
public void insert (int newData) { 
    if (newData < data) { 
     if (left == null) 
      left = new BinaryTreeNode(newData); 
     else left.insert(newData); 
    } else if (newData > data) { 
     if (right == null) 
      right = new BinaryTreeNode(newData); 
     else right.insert(newData); 
    } else 
     System.out.println("Duplicate – not adding……" + newData); 
} 



} 




public class BinaryTreeExample { 

public static void main(String[] args) { 
    BinaryTree tree = new BinaryTree(); 

    tree.insertInTree(6); 
    tree.insertInTree(3); 
    tree.insertInTree(9); 
    tree.insertInTree(1); 
    tree.insertInTree(15); 
    tree.insertInTree(7); 

    tree.displayInOrder(); 

} 

} 

Answer 1

简称遍历定义：

• “以”=左，自我吧
• “预购”=自我，左，右
• “后序”=左，正确，自我

将它应用到您的代码中，您只需要将“自我打印”行移动到：

public void preOrderTraversal (BinaryTreeNode subRoot) { 
    if (subRoot == null) return; 
    System.out.print(" " + subRoot.getData() + " "); 
    preOrderTraversal(subRoot.getLeft()); 
    preOrderTraversal(subRoot.getRight()); 
} 

public void postOrderTraversal (BinaryTreeNode subRoot) { 
    if (subRoot == null) return; 
    postOrderTraversal(subRoot.getLeft()); 
    postOrderTraversal(subRoot.getRight()); 
    System.out.print(" " + subRoot.getData() + " "); 
} 

// already correct 
public void displayInOrder (BinaryTreeNode subRoot){ 
    if (subRoot == null) return; 
    displayInOrder (subRoot.getLeft()); 
    System.out.print(" " + subRoot.getData() + " "); 
    displayInOrder (subRoot.getRight()); 
} 

这些方法只是打印内容。您需要打印最终换行符在包装方法：

public void displayInOrder() { 
    displayInOrder (root); 
    System.out.println(); 
} 

public void preOrderTraversal() { 
    preOrderTraversal (root); 
    System.out.println(); 
} 

public void postOrderTraversal() { 
    postOrderTraversal (root); 
    System.out.println(); 
}