数据结构_顺序存储二叉树

客官°小女子只卖身不卖艺 2023-07-11 06:17 27阅读 0赞

### 文章目录 ###

*   *  基本说明
     *  特点
     *  代码实现

## 基本说明 ##

从数据存储来看，数组存储方式和树的存储方式可以相互转换。

## 特点 ##

*  只考虑完全二叉树
 *  第n个元素的左子节点为 `2n + 1`
 *  第n个元素的右子节点为 `2n + 2`
 *  第n个元素的父节点为 `(n-1) / 2`
 *  n表示树从顶层向下，从左往右依次编号，对应数组中的索引

## 代码实现 ##

public class ArrayBinaryTree {
        
    	private int[] arr;
    
    	public ArrayBinaryTree(int[] arr) {
        
    		super();
    		this.arr = arr;
    	}
    
    	/**
    	 * 前序遍历数组
    	 * @param index
    	 */
    	public void preOrder(int index) {
        
    		if (arr == null || arr.length == 0) {
        
    			System.out.println("null");
    		}
    		System.out.print(arr[index]);
    		int leftIndex = index * 2 + 1;
    		int rightIndex = index * 2 + 2;
    		if (leftIndex < arr.length) {
        
    			preOrder(leftIndex);
    		}
    		if (rightIndex < arr.length) {
        
    			preOrder(rightIndex);
    		}
    	}
    
    	/**
    	 * 中序遍历
    	 * @param index
    	 */
    	public void infixOrder(int index) {
        
    		if (arr == null || arr.length == 0) {
        
    			System.out.println("null");
    		}
    		int leftIndex = index * 2 + 1;
    		int rightIndex = index * 2 + 2;
    		if (leftIndex < arr.length) {
        
    			infixOrder(leftIndex);
    		}
    		System.out.print(arr[index]);
    		if (rightIndex < arr.length) {
        
    			infixOrder(rightIndex);
    		}
    	}
    
    	/**
    	 * 后序遍历
    	 * @param index
    	 */
    	public void postOrder(int index) {
        
    		if (arr == null || arr.length == 0) {
        
    			System.out.println("null");
    		}
    		int leftIndex = index * 2 + 1;
    		int rightIndex = index * 2 + 2;
    		if (leftIndex < arr.length) {
        
    			postOrder(leftIndex);
    		}
    		if (rightIndex < arr.length) {
        
    			postOrder(rightIndex);
    		}
    		System.out.print(arr[index]);
    	}
    }