欢迎访问宙启技术站
智能推送

Java函数实现二叉树的深度遍历。

发布时间:2023-06-20 23:20:04

首先,我们需要了解什么是二叉树以及二叉树的遍历方式。

二叉树是由节点组成的树形结构,其中每个节点最多有两个子节点。二叉树可以为空,或者根节点为空,或者一个节点没有子节点。

根据遍历顺序的不同,可以将二叉树的遍历分为三种方式:前序遍历、中序遍历和后序遍历。分别介绍如下:

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函数实现二叉树的深度遍历的详细介绍。