二叉树利用数组存储
二叉树利用数组存储
如果利用数组存储一个二叉树的用空节点填补为完全二叉树的形式（无值节点用空填补），从左到右存储，那么我们可以利用以下的访问规则：
- 一个i节点的父节点为i/2向下取整
- 一个i节点的左孩子位2i(2i<= n, 否则没有左孩子)，
- 右孩子为2i+1(2i+1 <= n，否则没有右孩子)
- 这种树求高度，利用二叉树的最大节点数s = (2^n) - 1 来进行计算，n就是树的高度。
举一个栗子吧O(∩_∩)O~~～！
我们首先有一棵这样的树：
image.png
在我们利用数组存储它的时候，需要把它补充完一棵 完全二叉树 其中节点从1开始进行标记，从上到下，从左到右，看下面：
image.png
我们就简单点，把树的节点简单的封装为一个字符包装类存储字母：
public class BinaryTreeDemo {
static int TREESIZE = 14;
int getHeight(int size){
return (int)Math.floor(Math.log10((double)size+1)/Math.log10(2.0));
}
// 1. 求左孩子
int getLeftChild(Character[] arr, int index) {
if (2 * index > TREESIZE) {
return -1;
}
return 2 * index;
}
// 2. 求右孩子
int getRightChile(Character[] arr, int index) {
if (2 * index + 1 > TREESIZE) {
return -1;
}
return 2 * index + 1;
}
// 3. 求父节点
int getParent(Character[] arr, int index) {
if (index < 2 || index > TREESIZE) {
return -1;
}
return (int) Math.floor(index / 2);
}
// 先序遍历
void perOrder(Character[] arr, int index) {
System.out.println(arr[index]);
if (getLeftChild(arr, index) != -1 && arr[getLeftChild(arr, index)] != null) {
perOrder(arr, getLeftChild(arr, index));
}
if (getRightChile(arr, index) != -1 && arr[getRightChile(arr, index)] != null) {
perOrder(arr, getRightChile(arr, index));
}
}
// 中序遍历
void midOrder(Character[] arr, int index) {
if (getLeftChild(arr, index) != -1 && arr[getLeftChild(arr, index)] != null) {
midOrder(arr, getLeftChild(arr, index));
}
System.out.println(arr[index]);
if (getRightChile(arr, index) != -1 && arr[getRightChile(arr, index)] != null) {
midOrder(arr, getRightChile(arr, index));
}
}
// 后续遍历
void lastOrder(Character[] arr, int index) {
if (getLeftChild(arr, index) != -1 && arr[getLeftChild(arr, index)] != null) {
lastOrder(arr, getLeftChild(arr, index));
}
if (getRightChile(arr, index) != -1 && arr[getRightChile(arr, index)] != null) {
lastOrder(arr, getRightChile(arr, index));
}
System.out.println(arr[index]);
}
public static void main(String[] args) {
// 我们构建的一棵测试二叉树,下标从1开始
Character[] binaryTree = {null, 'A', 'B', 'C', null, null,
'D', 'E', null, null, null, null, null, null, 'F'};
BinaryTreeDemo btd = new BinaryTreeDemo();
System.out.println("先序～！");
btd.perOrder(binaryTree, 1);
System.out.println("中序～！");
btd.midOrder(binaryTree, 1);
System.out.println("后序～！");
btd.lastOrder(binaryTree, 1);
System.out.println("树的高度～！");
System.out.println(btd.getHeight(TREESIZE));
}
}
利用数组进行二叉树的非递归操作我们目前不讨论，我们会针对树的链式存储进行递归和非递归的～！撒花～！
