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;
}
}
}
```
