【数据结构和算法】顺序存储二叉树

顺序存储二叉树的介绍和代码实现

---

1 顺序存储二叉树

1.1 介绍

• 顺序存储二叉树：从数据存储方式来看，数组存储方式和树的存储方式可以相互转换。即顺序存储二叉树本质上是一个数组，但可以将这数组抽象成为二叉树。

1.2 特点

• （1）顺序存储二叉树只会考虑完全二叉树
• （2）第n个元素是左子节点，满足2 * n + 1
• （3）第n个元素是右子节点，满足2 * n + 2
• （4）第n个元素是父节点，满足(n - 1) / 2
• （5）n为二叉树中元素的编号（数组编号）（从0开始编号）

• 可以归纳总结为：上层和下层之间是两倍数的关系

1.3 代码

• 代码只是简单显示了前序遍历，中后序同理，只是打印的位置不一样而已

• （1）代码实现

  public class ArrayBinaryTree {
  
      Object[] arr; //底层存储数组（顺序存储二叉树本质是一个数组）
      int n; //数组长度
  
      public ArrayBinaryTree(Object[] arr) {
          this.arr = arr;
          this.n = arr.length;
      }
  
      /**
       * 前序遍历
       */
      public void prePrint() {
          if (arr == null || n == 0) {
              System.out.println("树为空！");
          }
  
          System.out.println("前序遍历为：");
          //数组下标0为根节点
          prePrintRecursion(0);
      }
  
      /**
       * 前序遍历 --- 递归本体
       * @param index 数组下标
       */
      private void prePrintRecursion(int index) {
          //打印当前index数据（父节点数据）
          System.out.print(arr[index] + " ");
  
          //左子树递归前序遍历
          int temp = index * 2 + 1; //计算左子节点下标
          if (temp < n) {
              //下标不越界就递归
              prePrintRecursion(temp);
          }
  
          //右子树递归前序遍历
          temp = index * 2 + 2; //计算右子节点下标
          if (temp < n) {
              prePrintRecursion(temp);
          }
      }
  }

• （2）测试

  @Test
  public void arrayBinaryTreeTest() {
  	//创建数组
  	Integer[] arr = new Integer[]{1, 2, 3, 4, 5, 6, 7};
  	//通过数组创建顺序存储二叉树
  	ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(arr);
  	//调用前序遍历
  	arrayBinaryTree.prePrint();
  }