Java函数：如何实现二叉树的查找与遍历？
发布时间：2023-06-18 10:37:43
一、二叉树简介
从结构上看，二叉树是由结点构成的集合，并且每个结点最多只有两个子结点（左子结点和右子结点）。有左右之分，且左子树和右子树本身又是一棵二叉树。从这个概念上，体现了二叉树的递归性质。
在二叉树的遍历中，主要有前序遍历、中序遍历和后序遍历三种情况。
二、二叉树的存储方式
1.顺序存储方式：将树的每个结点依次存储在一块连续的存储区域中。但是，对于这种存储方式，空间利用率非常低，因为大部分元素都是空结点；另外，我们对树进行操作时，可能需要移动大量元素，增加了复杂度和开销。
2.链式存储方式：通过指针连接每个结点。也就是说，对于每个结点，存储了指向左子结点和右子结点的指针，又称为动态存储方式。
最常见的链式存储方式包括：（1）使用结构体嵌套的方式，统一定义二叉树结构体；（2）使用“指针数组+malloc”的方式，动态生成二叉树结点。
三、Java实现二叉树
1.二叉树结点的定义和二叉树的创建
二叉树结点定义，代码如下：
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
二叉树的创建包括两个操作：初始化空的二叉树和向二叉树中添加结点。
初始化二叉树：
public class BinaryTree {
public TreeNode createBinaryTree(int[] array, int index) {
TreeNode treeNode = null;
if (index < array.length) {
int value = array[index];
treeNode = new TreeNode(value);
treeNode.left = createBinaryTree(array, 2 * index + 1);
treeNode.right = createBinaryTree(array, 2 * index + 2);
}
return treeNode;
}
}
向二叉树中添加结点：
public TreeNode addTreeNode(TreeNode root, int value) {
if (root == null) {
root = new TreeNode(value);
return root;
}
if (value < root.val) {
root.left = addTreeNode(root.left, value);
} else {
root.right = addTreeNode(root.right, value);
}
return root;
}
2.二叉树的遍历
前序遍历（根->左->右）：
public void preOrderTraversal(TreeNode node) {
if (node != null) {
System.out.print(node.val + " ");
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
}
中序遍历（左->根->右）：
public void inOrderTraversal(TreeNode node) {
if (node != null) {
inOrderTraversal(node.left);
System.out.print(node.val + " ");
inOrderTraversal(node.right);
}
}
后序遍历（左->右->根）：
public void postOrderTraversal(TreeNode node) {
if (node != null) {
postOrderTraversal(node.left);
postOrderTraversal(node.right);
System.out.print(node.val + " ");
}
}
3.二叉树的查找
在二叉树中查找一个给定的结点：
public TreeNode search(TreeNode root, int value) {
if (root == null || root.val == value) {
return root;
}
if (value < root.val) {
return search(root.left, value);
} else {
return search(root.right, value);
}
}
查找二叉树中的最小值：
public TreeNode findMin(TreeNode root) {
while (root.left != null) {
root = root.left;
}
return root;
}
查找二叉树中的最大值：
public TreeNode findMax(TreeNode root) {
while (root.right != null) {
root = root.right;
}
return root;
}
四、使用案例
1.创建二叉树并添加结点
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
int[] array = new int[]{12, 23, 45, 43, 5, 7, 87, 34, 8, 90};
TreeNode root = binaryTree.createBinaryTree(array, 0);
binaryTree.addTreeNode(root, 15);
}
2.遍历二叉树
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
int[] array = new int[]{12, 23, 45, 43, 5, 7, 87, 34, 8, 90};
TreeNode root = binaryTree.createBinaryTree(array, 0);
System.out.println("前序遍历：");
binaryTree.preOrderTraversal(root);
System.out.println();
System.out.println("中序遍历：");
binaryTree.inOrderTraversal(root);
System.out.println();
System.out.println("后序遍历：");
binaryTree.postOrderTraversal(root);
}
3.查找二叉树中的结点
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
int[] array = new int[]{12, 23, 45, 43, 5, 7, 87, 34, 8, 90};
TreeNode root = binaryTree.createBinaryTree(array, 0);
System.out.println("树中是否存在节点 34 ：" + binaryTree.search(root, 34));
System.out.println("树中最小值：" + binaryTree.findMin(root).val);
System.out.println("树中最大值：" + binaryTree.findMax(root).val);
}
五、总结
本文主要介绍了二叉树的基本概念和实现方式，同时给出了二叉树的创建和遍历、查找等操作的Java实现。对于需要用到二叉树的情况，读者可以根据自己的实际需要，选择最合适的实现方式。当然，本文介绍的只是二叉树的基本操作，对于复杂的算法和应用场景，读者可以进一步深入研究。