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   

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。