Java函数实现二叉树的深度遍历。
首先,我们需要了解什么是二叉树以及二叉树的遍历方式。
二叉树是由节点组成的树形结构,其中每个节点最多有两个子节点。二叉树可以为空,或者根节点为空,或者一个节点没有子节点。
根据遍历顺序的不同,可以将二叉树的遍历分为三种方式:前序遍历、中序遍历和后序遍历。分别介绍如下:
1.前序遍历
前序遍历又叫先序遍历,是指按照根节点、左子树、右子树的顺序遍历二叉树的过程。
2.中序遍历
中序遍历是指按照左子树、根节点、右子树的顺序遍历二叉树的过程。
3.后序遍历
后序遍历是指按照左子树、右子树、根节点的顺序遍历二叉树的过程。
接下来,我们来实现二叉树的深度遍历。
首先,定义一个二叉树节点的类:
class TreeNode {
int value;
TreeNode leftChild;
TreeNode rightChild;
public TreeNode(int value) {
this.value = value;
}
}
为了方便测试,我们可以构造一个二叉树:
TreeNode createTree() {
TreeNode root = new TreeNode(1);
TreeNode node1 = new TreeNode(2);
TreeNode node2 = new TreeNode(3);
TreeNode node3 = new TreeNode(4);
TreeNode node4 = new TreeNode(5);
TreeNode node5 = new TreeNode(6);
TreeNode node6 = new TreeNode(7);
root.leftChild = node1;
root.rightChild = node2;
node1.leftChild = node3;
node1.rightChild = node4;
node2.leftChild = node5;
node2.rightChild = node6;
return root;
}
定义完二叉树,下面我们就可以介绍如何实现二叉树的深度遍历了。
1.前序遍历
前序遍历是按照根节点、左子树、右子树的顺序遍历二叉树的过程。实现代码如下:
void preOrder(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.value + " ");
preOrder(root.leftChild);
preOrder(root.rightChild);
}
2.中序遍历
中序遍历是按照左子树、根节点、右子树的顺序遍历二叉树的过程。实现代码如下:
void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.leftChild);
System.out.print(root.value + " ");
inOrder(root.rightChild);
}
3.后序遍历
后序遍历是按照左子树、右子树、根节点的顺序遍历二叉树的过程。实现代码如下:
void postOrder(TreeNode root) {
if (root == null) {
return;
}
postOrder(root.leftChild);
postOrder(root.rightChild);
System.out.print(root.value + " ");
}
深度遍历其实就是递归遍历,分别从根节点、左子树、右子树开始遍历,所以实现起来比较简单。
以上就是Java函数实现二叉树的深度遍历的详细介绍。
