二叉树及其三种遍历方式的实现(基于Java)
2022/9/13 1:23:12
本文主要是介绍二叉树及其三种遍历方式的实现(基于Java),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
二叉树概念:
- 二叉树是每个节点的度均不超过2的有序树,因此二叉树中每个节点的孩子只能是0,1或者2个,并且每个孩子都有左右之分。
- 位于左边的孩子称为左孩子,位于右边的孩子成为右孩子;以左孩子为根节点的子树称其为左子树,右孩子为根节点的子树成为右子树。
- 二叉树可以使用顺序表(数组)来存储其节点,并且节点的存储位置即为数组的下标索引。
遍历:将二叉树中的节点信息由非线性排列变为某种意义上的线性排列,即遍历操作是非线性结构线性化。
结构如图所示:
三种遍历方式:
1.前序遍历
基本思想:首先访问根节点,然后前序遍历其左子树,最后前序遍历右子树。注意:遍历左右子树,依旧使用前序遍历
2.中序遍历
基本思想:首先中序遍历根节点的左子树,然后访问根节点,最后中序遍历其右子树。注意:遍历左右子树,依旧使用中序遍历
3.后序遍历
基本思想:首先后续遍历根节点的左子树,然后后序遍历根节点的右子树,最后访问其根节点。注意:遍历左右子树,依旧使用后序遍历
基于Java代码来实现上述三种遍历方式:
import java.util.List; public class ArrayBinaryTree<T> { //一颗二叉树 private T[] arr; //数据不能为空(数据为空,遍历无意义) public ArrayBinaryTree(T[] arr){ if(arr == null || arr.length == 0){ throw new IllegalArgumentException("arr must not null"); } this.arr = arr; } //前序遍历 public void preOrder(int index, List<T> result){ result.add(arr[index]); if(2 * index +1 < arr.length){ preOrder(2 * index +1,result); } if(2 * index + 2 < arr.length){ preOrder(2 * index + 2,result); } } //中序遍历 public void infixOrder(int index,List<T> result){ if(2 * index +1 <arr.length){ infixOrder(2 * index + 1,result); } result.add(arr[index]); if(2 * index + 2 < arr.length){ infixOrder(2 * index + 2,result); } } //后序遍历 public void postOrder(int index,List<T> result){ if(2 * index +1<arr.length){ postOrder(2 * index + 1,result); } if(2 * index + 2 < arr.length){ postOrder(2 * index +2,result); } result.add(arr[index]); } }
单元测试:
import java.util.ArrayList; public class ArrayBinaryTreeTest { public static void main(String[] args){ Integer[] arr = {1,2,4,3,5,6}; ArrayList<Integer> result = new ArrayList<>(arr.length); ArrayBinaryTree<Integer> arrayBinaryTree = new ArrayBinaryTree<>(arr); arrayBinaryTree.preOrder(0,result); System.out.println(result); String[] arr1 = {"A","B","C","D","E","F","G","H","I","J"}; ArrayList<String> result_str = new ArrayList<>(arr1.length); ArrayBinaryTree<String> arrayBinaryTree1 = new ArrayBinaryTree<>(arr1); arrayBinaryTree1.postOrder(0,result_str); System.out.println(result_str); } }
这里测试了前序遍历和后序遍历,中序遍历可自行测试!结果都正确!!!
测试结果:
至此,关于二叉树的前中后三种遍历方法及其代码实现介绍完毕!!!!!!
这篇关于二叉树及其三种遍历方式的实现(基于Java)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行
- 2024-05-08阿里云域名注册流程,分享给第一次购买域名的新手站长!