Java通过递归进行二叉树遍历详解编程语言

// 测试二叉树遍历,递归算法 
public class TestBinaryTree { 
    public static void main(String[] args) { 
        Node<String> g = new Node<String>("G", null, null); 
        Node<String> e = new Node<String>("E", null, null); 
        Node<String> f = new Node<String>("F", null, null); 
        Node<String> d = new Node<String>("D", null, g); 
        Node<String> b = new Node<String>("B", d, e); 
        Node<String> c = new Node<String>("C", null, f); 
        Node<String> a = new Node<String>("A", b, c); 
  
        System.out.println("生成的二叉树:"); 
        System.out.println("            A"); 
        System.out.println("            |     "); 
        System.out.println("       |---------|"); 
        System.out.println("       B         C"); 
        System.out.println("       |         |"); 
        System.out.println("  |---------|     -----|"); 
        System.out.println("  D         E          F"); 
        System.out.println("  |"); 
        System.out.println("   ----|"); 
        System.out.println("       G"); 
  
        System.out.println("二叉树深度：" + BinaryTree.getDepth(a)); 
  
        System.out.print("前序遍历："); 
        BinaryTree.priorderTraversal(a); 
        System.out.println(); 
  
        System.out.print("中序遍历："); 
        BinaryTree.inorderTraversal(a); 
        System.out.println(); 
  
        System.out.print("后序遍历："); 
        BinaryTree.postorderTraversal(a); 
        System.out.println(); 
    } 
} 
  
// 二叉树 
class BinaryTree { 
    // 前序遍历 
    static <T> void priorderTraversal(Node<T> node) { 
        if (node != null) { 
            visitNode(node); 
            priorderTraversal(node.getLeftChild()); 
            priorderTraversal(node.getRightChild()); 
        } 
    } 
  
    // 中序遍历 
    static <T> void inorderTraversal(Node<T> node) { 
        if (node != null) { 
            inorderTraversal(node.getLeftChild()); 
            visitNode(node); 
            inorderTraversal(node.getRightChild()); 
        } 
    } 
  
    // 后序遍历 
    static <T> void postorderTraversal(Node<T> node) { 
        if (node != null) { 
            postorderTraversal(node.getLeftChild()); 
            postorderTraversal(node.getRightChild()); 
            visitNode(node); 
        } 
    } 
  
    // 二叉树深度 
    static <T> int getDepth(Node<T> node) { 
        if (node == null) { 
            return 0; 
        } 
        int leftDepth = 0; 
        int rightDepth = 0; 
        leftDepth = getDepth(node.getLeftChild()); 
        rightDepth = getDepth(node.getRightChild()); 
        return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1; 
    } 
  
    // 访问节点 
    static <T> void visitNode(Node<T> node) { 
        System.out.print(node.getKey() + " "); 
    } 
} 
  
// 节点 
class Node<T> { 
    private T key; 
    private Node<T> leftChild; 
    private Node<T> rightChild; 
  
    public Node() { 
  
    } 
  
    public Node(T key, Node<T> leftChild, Node<T> rightChild) { 
        super(); 
        this.key = key; 
        this.leftChild = leftChild; 
        this.rightChild = rightChild; 
    } 
  
    public T getKey() { 
        return key; 
    } 
  
    public void setKey(T key) { 
        this.key = key; 
    } 
  
    public Node<T> getLeftChild() { 
        return leftChild; 
    } 
  
    public void setLeftChild(Node<T> leftChild) { 
        this.leftChild = leftChild; 
    } 
  
    public Node<T> getRightChild() { 
        return rightChild; 
    } 
  
    public void setRightChild(Node<T> rightChild) { 
        this.rightChild = rightChild; 
    } 
  
}

输出结果：

生成的二叉树:  
            A  
            |       
       |---------|  
       B         C  
       |         |  
  |---------|     -----|  
  D         E          F  
  |  
   ----|  
       G  
二叉树深度：4  
前序遍历：A B D G E C F   
中序遍历：D G B E A C F   
后序遍历：G D E B F C A