Java实现二叉树创建与八种遍历方法详解

73 浏览量更新于2024-09-01 1 收藏 51KB PDF 举报

本文主要介绍了如何使用Java实现二叉树的创建及五种遍历方法，包括递归和非递归的方式，涵盖了先序、中序、后序三种经典遍历，以及广度优先和深度优先遍历。在Java中，二叉树是一种常用的数据结构，用于组织和操作数据。它由节点组成，每个节点包含一个值和两个指向子节点的引用（左孩子和右孩子）。二叉树的创建通常通过数组或链表来实现。本示例中，使用了一个整数数组`int[] datas`来初始化二叉树，并通过`List<Node> nodelist`存储每个节点。首先，`creatBinaryTree`方法用于根据数组创建二叉树。这个方法会递归地将数组元素分配给二叉树的节点，通常从数组的第一个元素开始作为根节点，然后依次处理其余元素。具体实现细节可能包括判断当前元素是否有左孩子和右孩子，以及如何将它们连接起来。接下来，文章讨论了五种遍历方法： 1. 递归先序遍历（Root-Left-Right）：首先访问根节点，然后递归遍历左子树，最后遍历右子树。在`preOrderTraversal`方法中，会使用递归调用来实现这一过程。 2. 非递归先序遍历：使用栈来模拟递归过程。从根节点开始，将其压入栈中，然后不断出栈并访问节点，直到栈为空。如果当前节点有左孩子，先将其左孩子压入栈，再访问右孩子，以此类推。`preOrderTraversalbyLoop`方法实现了这一过程。 3. 递归中序遍历（Left-Root-Right）：首先遍历左子树，然后访问根节点，最后遍历右子树。`inOrderTraversal`方法使用递归实现。 4. 非递归中序遍历：使用栈来实现。不同于先序遍历，这里需要在访问根节点之前，先将左子树的所有节点压入栈。当遇到一个没有左孩子的节点时，开始访问节点，然后转向其右子树。`inOrderTraversalbyLoop`方法展示了这种方法。 5. 递归后序遍历（Left-Right-Root）：先遍历左子树，然后遍历右子树，最后访问根节点。`postOrderTraversal`方法使用递归实现。此外，文中可能还提到了广度优先遍历（BFS）和深度优先遍历（DFS），这两种遍历策略通常使用队列（BFS）和栈（DFS）来实现，遍历顺序有所不同。广度优先遍历按照层次顺序访问节点，而深度优先遍历则尽可能深地探索树的分支。在Java中，二叉树遍历的应用广泛，例如在搜索、排序、表达式求解等场景中都有所体现。理解并熟练掌握这些遍历方法对于理解和优化算法至关重要。

java实现二叉树的创建及实现二叉树的创建及5种遍历方法种遍历方法(总结总结)

下面小编就为大家带来一篇java实现二叉树的创建及5种遍历方法(总结)。小编觉得挺不错的，现在就分享给大

家，也给大家做个参考。一起跟随小编过来看看吧

用java实现的数组创建二叉树以及递归先序遍历，递归中序遍历，递归后序遍历，非递归前序遍历，非递归中序遍历，非递归

后序遍历，深度优先遍历，广度优先遍历8种遍历方式：

package myTest;

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.List;

import java.util.Stack;

public class myClass {

public static void main(String[] args) {

// TODO Auto-generated method stub

myClass tree = new myClass();

int[] datas = new int[]{1,2,3,4,5,6,7,8,9};

List<Node> nodelist = new LinkedList<>();

tree.creatBinaryTree(datas, nodelist);

Node root = nodelist.get(0);

System.out.println("递归先序遍历：");

tree.preOrderTraversal(root);

System.out.println();

System.out.println("非递归先序遍历：");

tree.preOrderTraversalbyLoop(root);

System.out.println();

System.out.println("递归中序遍历：");

tree.inOrderTraversal(root);

System.out.println();

System.out.println("非递归中序遍历：");

tree.inOrderTraversalbyLoop(root);

System.out.println();

System.out.println("递归后序遍历：");

tree.postOrderTraversal(root);

System.out.println();

System.out.println("非递归后序遍历：");

tree.postOrderTraversalbyLoop(root);

System.out.println();

System.out.println("广度优先遍历：");

tree.bfs(root);

System.out.println();

System.out.println("深度优先遍历：");

List<List<Integer>> rst = new ArrayList<>();

List<Integer> list = new ArrayList<>();

tree.dfs(root,rst,list);

System.out.println(rst);

}

/**

* @param datas 实现二叉树各节点值的数组

* @param nodelist 二叉树list

private void creatBinaryTree(int[] datas,List<Node> nodelist){

//将数组变成node节点

for(int nodeindex=0;nodeindex<datas.length;nodeindex++){

Node node = new Node(datas[nodeindex]);

nodelist.add(node);

}

//给所有父节点设定子节点

for(int index=0;index<nodelist.size()/2-1;index++){

//编号为n的节点他的左子节点编号为2*n 右子节点编号为2*n+1 但是因为list从0开始编号，所以还要+1

//这里父节点有1（2,3）,2（4,5）,3（6,7）,4（8,9）但是最后一个父节点有可能没有右子节点需要单独处理

nodelist.get(index).setLeft(nodelist.get(index*2+1));

nodelist.get(index).setRight(nodelist.get(index*2+2));

}

//单独处理最后一个父节点因为它有可能没有右子节点

int index = nodelist.size()/2-1;

nodelist.get(index).setLeft(nodelist.get(index*2+1)); //先设置左子节点

if(nodelist.size() % 2 == 1){ //如果有奇数个节点，最后一个父节点才有右子节点

nodelist.get(index).setRight(nodelist.get(index*2+2));

}

/**

* 遍历当前节点的值

下载后可阅读完整内容，剩余3页未读，立即下载

weixin_38617451

粉丝: 4
资源: 903

Java实现二叉树创建与八种遍历方法详解

java实现 二叉树的创建，排序，遍历

Java创建二叉树java

Java实现二叉树的遍历

java创建二叉树_java实现二叉树的创建及5种遍历方法(总结)

用Java实现二叉树输入先序遍历和中序遍历然后输出后序遍历

java实现二叉树层次遍历

Java实现二叉树前序遍历，要求包含输入输出

java实现二叉树层序遍历

Java二叉树非递归遍历

用java实现二叉树的层序遍历

最新资源

java实现二叉树的创建，排序，遍历