1 二叉树的存储 1.1 顺序存储
使用数组自上而下，自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在某个数组下标为i-1的分量中，然后通过一些方法确定结点在逻辑上的父子和兄弟关系。
根据二叉树的性质，完全二叉树和满二叉树树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，既能节省存储空间，又能利用数组元素下标值确定结点在二叉树中的位置，以及结点之间的关系。
而对于一般的二叉树也必须按照完全二叉树的形式存储，也就是必须添加一些并不存在的虚拟结点，造成空间的浪费。
图1 二叉树顺序存储
顺序存储的关键是数组下标确定结点的位置，如结点从1开始编号，那么结点i的左孩子为2*i，右孩子为2*i+1。不存在结点用0表示。
先回忆一下二叉树的一些性质：
（1） 非空二叉树第k层最多有2k-1个结点
（2） 高度为h的二叉树至多有2h-1个结点
首先按照树的高度height初始化一颗树，以及一些有用的方法，代码如下：
public class ArrayBiTree<T> { private Object[] data; private int height = 3; // 树的高度 默认为3 private int n; // 结点个数 public ArrayBiTree() { data = new Object[(int) Math.pow(2, height)]; init(); } /** * 指定深度初始化一个树 * @param height 树的深度 */ public ArrayBiTree(int height) { this.height = height; data = new Object[(int) Math.pow(2, height) - 1]; } private void init(){ System.out.println("默认生成一颗完全二叉树，高度为3："); for(int i=0; i<(int) Math.pow(2, height) - 1; i++){ data[i] = i+1; n++; } print(); } /** * 判断结点是否存在 * @param index 根节点从 1 开始 * @return */ public boolean isExist(int index){ if(index > n) return false; return Integer.valueOf(data[index-1].toString()) != 0; } }
1.2 层次遍历/** * 层次遍历，利用队列是实现 */ public void levelOrder(){ RingBuffer<Integer> queue = new RingBuffer<Integer>(n+1); queue.put(1); // 根节点先进队列 while(queue.size()>0){ int tmp = queue.get(); System.out.print(data[tmp-1]+" "); if (isExist(2 * tmp)) { // 如果左子树存在，把左子树编号入栈 queue.put(2 * tmp); } if (isExist(2 * tmp + 1)) { // 如果右子树存在，把右子树编号入栈， queue.put(2 * tmp + 1); } } } 1.3 先序遍历 1.3.1 递归实现
/** * 先序遍历，递归实现Recursion * @param index 根节点从 1 开始 */ public void preOrderRecur(int index){ if(isExist(index)){ //判断结点是否存在 System.out.print(data[index-1]+" "); // 访问根节点 preOrderRecur(2*index); // 递归遍历左子树 preOrderRecur(2*index + 1); // 递归遍历右子树 } }
1.3.2 非递归实现实现方法1：
/** * 先序遍历，非递归实现，借助栈来实现<p> * 根节点先入栈，访问栈顶结点，若栈顶元素的右孩子存在则入栈，若栈顶元素的左孩子存在则入栈，如此循环直到栈空 */ public void preOrder(){ ArrayStack<Integer> stack = new ArrayStack<Integer>(n); stack.push(1); // 根节点入栈 while(!stack.isEmpty()){ int tmp = stack.pop(); // 取根结点，把每个结点都看作根节点 System.out.print(data[tmp-1]+" "); // 访问根结点 if (isExist(2 * tmp + 1)) { // 如果根节点的右子树存在，把右子树编号入栈 stack.push(2 * tmp + 1); } if (isExist(2 * tmp)) { // 如果根节点的左子树存在，把左子树编号入栈 stack.push(2 * tmp); } } }
实现方法2：