Java实现二叉树的建立、计算高度与递归输出操作示例

一、建立二叉树

1. 首先定义二叉树节点的数据结构：Node

class Node {
    int value;  // 节点值
    Node left;  // 左子树节点
    Node right; // 右子树节点

    public Node(int value) {
        this.value = value;
        left = null;
        right = null;
    }
}

1. 使用递归的方式来建立二叉树

public Node buildTree(int[] arr, int start, int end) {
    if (start > end) {
        return null;
    }
    int mid = (start + end) / 2;
    Node root = new Node(arr[mid]);
    root.left = buildTree(arr, start, mid - 1);
    root.right = buildTree(arr, mid + 1, end);
    return root;
}

1. 调用方法来生成二叉树并输出它的结构

int[] arr = {1, 2, 3, 4, 5, 6, 7};
Node root = buildTree(arr, 0, arr.length - 1);
System.out.println(root.value);              // 4
System.out.println(root.left.value);         // 2
System.out.println(root.left.left.value);    // 1
System.out.println(root.left.right.value);   // 3
System.out.println(root.right.value);        // 6
System.out.println(root.right.left.value);   // 5
System.out.println(root.right.right.value);  // 7

二、计算二叉树高度

使用递归的思路来计算二叉树的高度，计算方式即为左子树的高度和右子树的高度中较大值加一。

声明代码如下：

public int getHeight(Node root) {
    if (root == null) {
        return 0;
    } else {
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return (leftHeight > rightHeight) ? (leftHeight + 1) : (rightHeight + 1);
    }
}

三、递归输出二叉树

使用递归的方式来进行中序遍历，递归过程中输出节点的值即可。

public void inOrder(Node root) {
    if (root != null) {
        inOrder(root.left);
        System.out.print(root.value + " ");
        inOrder(root.right);
    }
}

示例1：

int[] arr = {1, 2, 3, 4, 5, 6, 7};
Node root = buildTree(arr, 0, arr.length - 1);
inOrder(root);  // 1 2 3 4 5 6 7

示例2：

int[] arr = {10, 20, 30, 40, 50};
Node root = buildTree(arr, 0, arr.length - 1);
inOrder(root);  // 10 20 30 40 50

以上针对Java实现二叉树的建立、计算高度与递归输出操作的完整攻略。