数据结构与算法--顺序存储二叉树
2022/8/11 14:24:47
本文主要是介绍数据结构与算法--顺序存储二叉树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
简介
二叉树的存储结构有两种,分别为顺序存储和链式存储
采用顺序存储。指的是使用顺序表(数组)存储二叉树。需要注意的是,顺序存储只适用于完全二叉树
-
顺序存储的完全二叉树的特征(n表示二叉树中第几个元素,按0开始编号)
-
第n个元素的左子节点为2n+1
-
第n个元素的右子节点为2n+2
-
第n个元素的父节点为(n-1)/2
-
-
如果想顺序存储普通二叉树,需要提前将普通二叉树转化为完全二叉树
-
普通二叉树转完全二叉树的方法很简单,只需给二叉树额外添加一些节点,将其"拼凑"成完全二叉树即可
-
顺序存储二叉树基础遍历
前序遍历
import java.util.LinkedList; import java.util.Queue; public class ArrayBinaryTree<K> { /**存储数据结点的数组*/ public K[] array; public ArrayBinaryTree(K[] array) { this.array = array; } /**前序遍历*/ public Queue<K> preErgodic(){ Queue<K> queue = new LinkedList<>(); if (array == null || array.length == 0) { return queue; } preErgodic(0,queue); return queue; } public void preErgodic(int index,Queue<K> queue){ queue.add(array[index]); //向左,递归遍历 if ((2 * index + 1) < array.length) { preErgodic(2 * index + 1,queue); } //向右,递归遍历 if ((2 * index + 2) < array.length) { preErgodic(2 * index + 2,queue); } } }
中序遍历
import java.util.LinkedList; import java.util.Queue; public class ArrayBinaryTree<K> { /**存储数据结点的数组*/ public K[] array; public ArrayBinaryTree(K[] array) { this.array = array; } /**中序遍历*/ public Queue<K> midErgodic(){ Queue<K> queue = new LinkedList<>(); if (array == null || array.length == 0) { return queue; } midErgodic(0,queue); return queue; } public void midErgodic(int index,Queue<K> queue){ //向左,递归遍历 if ((2 * index + 1) < array.length) { midErgodic(2 * index + 1,queue); } queue.add(array[index]); //向右,递归遍历 if ((2 * index + 2) < array.length) { midErgodic(2 * index + 2,queue); } } }
后序遍历
import java.util.LinkedList; import java.util.Queue; public class ArrayBinaryTree<K> { /**存储数据结点的数组*/ public K[] array; public ArrayBinaryTree(K[] array) { this.array = array; } /**后续遍历*/ public Queue<K> afterErgodic(){ Queue<K> queue = new LinkedList<>(); if (array == null || array.length == 0) { return queue; } afterErgodic(0,queue); return queue; } public void afterErgodic(int index,Queue<K> queue) { //向左,递归遍历 if ((2 * index + 1) < array.length) { afterErgodic(2 * index + 1, queue); } //向右,递归遍历 if ((2 * index + 2) < array.length) { afterErgodic(2 * index + 2, queue); } queue.add(array[index]); } }
这篇关于数据结构与算法--顺序存储二叉树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署
- 2024-04-14RAG应用开发实战02-相似性检索的关键 - Embedding