顺序存储二叉树(使用数组存储二叉树,并且前中后遍历)

顺序存储二叉树的特点:

顺序二叉树通常只考虑完全二叉树

第n个元素的左子节点为  2 * n + 1

第n个元素的右子节点为  2 * n + 2

第n个元素的父节点为  (n-1) / 2

n : 表示二叉树中的第几个元素(按0开始编号 与数组下标保持一致)

 

 

package tree; import java.util.Arrays; /** * 预备知识 * (1) * 1) 顺序二叉树通常只考虑完全二叉树 * 2) 第n个元素的左子节点为 2 * n + 1 * 3) 第n个元素的右子节点为 2 * n + 2 * 4) 第n个元素的父节点为 (n-1) / 2 * n : 表示二叉树中的第几个元素(按0开始编号 与数组下标保持一致) * if(index * 2 + 1 < arrayBinaryTree.length){//递归结束条件 * if(index * 2 + 2 < arrayBinaryTree.length ){ * (2)index的引入 * index用于遍历数组中的元素,所以需要借助index * 并且main方法中需要指定从哪个结点开始遍历(一般都是从根节点) * 并且为了不必每次调用遍历方法都得在main方法中填遍历的起点,所以写了重载方法,直接指定了遍历的起点 * * **/ public class ArrBinaryTreeDemo { public static void main(String[] args) { int[] arr = { 1, 2, 3, 4, 5, 6, 7 }; //创建一个 ArrBinaryTree ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr); //arrBinaryTree.preOrder(); // 1,2,4,5,3,6,7 //arrBinaryTree.infixOrder();//4 2 5 1 3 6 7 arrBinaryTree.postOrder();//4 5 2 6 7 3 1 } } //编写一个ArrayBinaryTree, 实现顺序存储二叉树遍历 class ArrBinaryTree{ private int[] arrayBinaryTree; public ArrBinaryTree(int[] arrayBinaryTree) { this.arrayBinaryTree = arrayBinaryTree; } public void preOrder() { this.preOrder(0); } public void preOrder(int index){//index用于遍历数组中的元素,所以需要借助index /* int[] arr = {}; int[] arr = null;*/ if(arrayBinaryTree == null || arrayBinaryTree.length == 0){ System.out.println("数组中无数据不能遍历"); return; } /* for(int i = 0 ; i*2 + 1 <arrayBinaryTree.length;i++){ System.out.println(arrayBinaryTree[i]); }*/ System.out.println(arrayBinaryTree[index]); if(index * 2 + 1 < arrayBinaryTree.length){//递归结束条件 preOrder(index*2 + 1); } if(index * 2 + 2 < arrayBinaryTree.length ){ preOrder(index*2 + 2); } } public void infixOrder(){ this.infixOrder(0); } public void infixOrder(int index){ if(arrayBinaryTree == null || arrayBinaryTree.length == 0){ System.out.println("数组中无数据不能遍历"); return; } if(index * 2 + 1 < arrayBinaryTree.length){ infixOrder(index * 2 + 1); } System.out.println(arrayBinaryTree[index]); if(index * 2 + 2 < arrayBinaryTree.length ){ infixOrder(index * 2 + 2); } } public void postOrder(){ this.postOrder(0); } public void postOrder(int index){ if(arrayBinaryTree == null || arrayBinaryTree.length == 0){ System.out.println("数组中无数据不能遍历"); return; } if(index * 2 + 1 < arrayBinaryTree.length){ postOrder(index * 2 + 1); } if(index * 2 + 2 < arrayBinaryTree.length ){ postOrder(index * 2 + 2); } System.out.println(arrayBinaryTree[index]); } }