java实现简单的二叉树

二叉树是一种常见的数据结构，它以树形结构的形式组织数据，每个节点最多有两个子节点，分别称为左子节点和右子节点。本文将从多个角度来介绍如何使用Java实现简单的二叉树。

1. 定义二叉树节点类

在Java中，可以通过定义一个二叉树节点类来表示每个节点。该类包括节点的值、左子节点和右子节点的引用。以下是节点类的代码示例：

```

public class TreeNode {

int val;

TreeNode left;

TreeNode right;

public TreeNode(int val) {

this.val = val;

this.left = null;

this.right = null;

}

}

```

2. 创建二叉树

创建二叉树的过程是递归的，每个节点可以看作是一个小的二叉树。如果节点为空，则返回null。如果节点不为空，则创建该节点，并递归创建左子节点和右子节点。以下是创建二叉树的代码示例：

```

public class BinaryTree {

public TreeNode createTree(int[] nums, int i) {

if (i >= nums.length || nums[i] == -1) {

return null;

}

TreeNode root = new TreeNode(nums[i]);

root.left = createTree(nums, 2 * i + 1);

root.right = createTree(nums, 2 * i + 2);

return root;

}

}

```

3. 遍历二叉树

遍历二叉树是指按照某种顺序访问二叉树中的每个节点。常见的遍历方式有前序遍历、中序遍历和后序遍历。以下是实现三种遍历方式的代码示例：

```

public class BinaryTree {

//前序遍历

public void preOrder(TreeNode root) {

if (root != null) {

System.out.print(root.val + " ");

preOrder(root.left);

preOrder(root.right);

}

}

//中序遍历

public void inOrder(TreeNode root) {

if (root != null) {

inOrder(root.left);

System.out.print(root.val + " ");

inOrder(root.right);

}

}

//后序遍历

public void postOrder(TreeNode root) {

if (root != null) {

postOrder(root.left);

postOrder(root.right);

System.out.print(root.val + " ");

}

}

}

```

4. 反转二叉树

反转二叉树是指将二叉树的每个节点的左右子节点对调。代码实现比较简单，只需递归处理每个节点的左右子节点即可。

```

public class BinaryTree {

public TreeNode invertTree(TreeNode root) {

if (root == null) {

return null;

}

TreeNode tmp = root.left;

root.left = invertTree(root.right);

root.right = invertTree(tmp);

return root;

}

}

```

5. 求二叉树高度

二叉树的高度是指从根节点到最远叶子节点的路径上的节点数。下面是求二叉树高度的代码实现：

```

public class BinaryTree {

public int getHeight(TreeNode root) {

if (root == null) {

return 0;

} else {

int leftHeight = getHeight(root.left);

int rightHeight = getHeight(root.right);

return Math.max(leftHeight, rightHeight) + 1;

}

}

}

```