目录
1. 顺序储存二叉树的介绍
- 1. 顺序储存二叉树的介绍
- 2. 顺序储存二叉树的程序实现
从数据储存来看,顺序储存二叉树的底层是用数组来储存数据的,如下图所示:
而遍历顺序储存二叉树,仍然可以以前序遍历、中序遍历、后序遍历的方式进行遍历
顺序存储二叉树的特点:
- 顺序储存二叉树通常只考虑完全二叉树
- 第n个元素的左子节点为 2 ∗ n + 1 2 * n + 1 2∗n+1。其中n为index
- 第n个元素的右子节点为 2 ∗ n + 2 2 * n + 2 2∗n+2
- 第n个元素的父节点为 ( n − 1 ) / 2 (n-1) / 2 (n−1)/2
顺序存储二叉树应用实例: 八大排序算法中的堆排序,就会使用到顺序存储二叉树。堆排序的应用参考地址
2. 顺序储存二叉树的程序实现public class ArrayBinaryTreeDemo { public static void main(String[] args) { int[] array = {1, 2, 3, 4, 5, 6, 7}; // 创建一个ArrayBinaryTree ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(array); arrayBinaryTree.preOrder(); } } // ArrayBinaryTree实现 class ArrayBinaryTree { // 用数据保存ArrayBinaryTree的数据 private int[] array; public ArrayBinaryTree(int[] array) { this.array = array; } // 重载preOrder public void preOrder() { this.preOrder(0); } // 顺序存储二叉树的前序遍历实现。参数为数组的下标 public void preOrder(int index) { // 如果数组为空,或者array.length = 0,则不能遍历 if (array == null || array.length == 0) { System.out.println("数组为空,不能完成顺序储存二叉树的前序遍历"); } // 输出当前元素 System.out.println(array[index]); // 向左递归遍历 if ((index * 2 + 1) < array.length) { preOrder(2 * index + 1); } // 向右递归遍历 if ((index * 2 + 2) < array.length) { preOrder(2 * index + 2); } } }
运行程序,结果如下:
1 2 4 5 3 6 7