顺序存储二叉树前序、中序、后序

布满荆棘的人生 2021-08-11 14:08 334阅读 0赞

【一】顺序存储二叉树

> **数组存储方式和树的存储方式可以相互转换。**
> 
> 要求：  
> 1）二叉树的节点，要求以数组的方式来存放  
> 2）要求在遍历数组时，仍然可以以前序遍历、中序遍历和后序遍历的方式来完成节点的遍历。
> 
> 特点：
> 
> 1.  顺序二叉树通常只考虑完全二叉树
> 2.  第n个元素的左子树的下标为2\*n+1;
> 3.  第n个元素的右子树的下标为2\*n+2;
> 4.  第n个元素的父节点为(n-1)/2
> 
>  n:表示二叉树中的第几个元素（从0开始编号）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RoZV9CZXN0X0hhY2tlcg_size_16_color_FFFFFF_t_70][]

【二】代码实现顺序存储二叉树的前序、中序、后序

/*
     * 特点：
     * 1>顺序二叉树通常只考虑完全二叉树
     * 2>第n个元素的左子树的下标为2*n+1;
     * 3>第n个元素的右子树的下标为2*n+2;
     * 4>第n个元素的父节点为(n-1)/2
     * 
     * n:表示二叉树中的第几个元素（从0开始编号）
     * */
    public class TreeTest2 {
    	public static void main(String[] args) {
    		int[] arr= {1,2,3,4,5,6,7};
    		System.out.println("------前序遍历");
    		ArrayBinaryTree abt=new ArrayBinaryTree(arr);
    		abt.preOrder(0);
    		
    		System.out.println("------中序遍历");
    		abt.infixOrder(0);
    		
    		System.out.println("------后序遍历");
    		abt.pastOrder(0);
    	}
    }
    
    class ArrayBinaryTree{
    	private int[] arr;
    	public ArrayBinaryTree(int[] arr) {
    		//super();
    		this.arr = arr;
    	}
    	
    	/*public void preOrder() {
    		preOrder(0);
    	}*/
    	//顺序存储二叉树的先序遍历
    	public void preOrder(int index) {
    		//如果数组为空
    		if(arr==null||arr.length==0) {
    			System.out.println("数组为空，不能按照二叉树的先序遍历");
    		}
    		System.out.println(arr[index]);
    		if((index*2+1)<arr.length) {
    			preOrder(index*2+1);
    		}
    		if((index*2+2)<arr.length) {
    			preOrder(index*2+2);
    		}
    	}
    	
    	//顺序存储二叉树的中序遍历
    	public void infixOrder(int index) {
    		//如果数组为空
    		if(arr==null||arr.length==0) {
    			System.out.println("数组为空，不能按照二叉树的先序遍历");
    		}
    		if((index*2+1)<arr.length) {
    			preOrder(index*2+1);
    		}
    		System.out.println(arr[index]);
    		if((index*2+2)<arr.length) {
    			preOrder(index*2+2);
    		}
    	}
    	
    	//顺序存储二叉树的后序遍历
    	public void pastOrder(int index) {
    		//如果数组为空
    		if(arr==null||arr.length==0) {
    			System.out.println("数组为空，不能按照二叉树的先序遍历");
    		}
    		if((index*2+1)<arr.length) {
    			preOrder(index*2+1);
    		}
    		if((index*2+2)<arr.length) {
    			preOrder(index*2+2);
    		}
    		System.out.println(arr[index]);
    	}
    }

【三】输出截图

先序：

![20190915232410697.png][]

中序：

![20190915232436312.png][]

后序：

![20190915232502681.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RoZV9CZXN0X0hhY2tlcg_size_16_color_FFFFFF_t_70]: /images/20210811/196fcc5dd1894d65be26392ab6152213.png
[20190915232410697.png]: /images/20210811/6eee4570e0f5446c84a1db3bfa3c34b3.png
[20190915232436312.png]: /images/20210811/7e26e02b8c9b4108b7eb062574840749.png
[20190915232502681.png]: /images/20210811/98e021607e3443858d25ad7859961965.png