顺序存储二叉树
2020-06-14 本文已影响0人
小笨笨的花花
顺序存储二叉树特点
- 只考虑完全二叉树
- 第n个元素的左子节点 下标 2*n+1
- 第n个元素的右子节点 下标 2*n+2
- 第n个元素的父节点为(n-1)/2
- n:表示二叉树的第几个元素(按0开始标号)
应用实例
八大排序算法中的堆排序中,会用到顺序存储二叉树。
//给一个数组,以二叉树前序遍历的方式进行遍历,根 左 右
public void preOrder(int index){
//如果数组为空,或者arr.length=0
if (arr==null|| arr.length==0){
System.out.println("数组为空,不能按照二叉树前序遍历");
}
//输出当前这个元素
System.out.println(arr[index]);
//向左递归遍历
if (index*2+1<arr.length){
preOrder(2*index+1);
}
//向右递归遍历
if (index*2+2<arr.length){
preOrder(2*index+2);
}
}