二叉树的顺序存储（Java代码实现）

ゝ一纸荒年。 2023-03-14 08:09 40阅读 0赞

➢**基本说明**  
从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组，

用数组存放树，但是需要保留左右指针。

➢ **顺序存储二叉树的特点:**

1.  顺序二叉树通常只考虑完全二叉树
2.  第n个元素的左子节点为 2\*n+1
3.  第n个元素的右子节点为 2\*n+2
4.  第n个元素的父节点为 (n-1)/2
5.  n:表示二叉树中的第几个元素(按0开始编号）

**示例：一个1234567的二叉树 使用顺序存储**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]  
**代码实现：**  
定义一个ArrBinarytree类，定义一个arr数组，并且添加构造方法，初始化数组。

private int[] arr;
    
    	public ArrBinarytree(int[] arr) { 
    		this.arr = arr;
    	}

定义方法：前序中序后序基本上一样，修改顺序即可。

// 数组的前序遍历 n=>数组下标,根节点
    	public void DLR(int n) { 
    		// 数组为空或者arr.length=0
    		if (arr == null || arr.length == 0) { 
    			System.out.println("数组为空，无法遍历！");
    		}
    		System.out.println(arr[n]);
    		// 向左递归
    		if ((n * 2 + 1) < arr.length) { 
    			DLR(n * 2 + 1);
    		}
    		// 向右递归
    		if ((n * 2 + 2) < arr.length) { 
    			DLR(n * 2 + 2);
    		}
    	}
    	//中序遍历
    	public void LDR(int n) { 
    		// 数组为空或者arr.length=0
    		if (arr == null || arr.length == 0) { 
    			System.out.println("数组为空，无法遍历！");
    		}
    		// 向左递归
    		if ((n * 2 + 1) < arr.length) { 
    			LDR(n * 2 + 1);
    		}
    		System.out.println(arr[n]);
    		// 向右递归
    		if ((n * 2 + 2) < arr.length) { 
    			LDR(n * 2 + 2);
    		}
    	}
    	//后序遍历
    	public void LRD(int n) { 
    		// 数组为空或者arr.length=0
    		if (arr == null || arr.length == 0) { 
    			System.out.println("数组为空，无法遍历！");
    		}
    		// 向左递归
    		if ((n * 2 + 1) < arr.length) { 
    			LRD(n * 2 + 1);
    		}
    		// 向右递归
    		if ((n * 2 + 2) < arr.length) { 
    			LRD(n * 2 + 2);
    		}
    		System.out.println(arr[n]);
    	}

定义测试：进行测试

ArrBinarytree ab = new ArrBinarytree(arr);
    		// ab.DLR(0); // 1 2 4 5 3 6 7
    		// ab.LDR(0); // 4 2 5 1 6 3 7 
    		ab.LRD(0);    // 4 5 2 6 7 3 1

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]: /images/20230312/ead43c754e2c4f5ca237575a69a2cf1c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]: /images/20230312/b75c48d3991d4c1abffefaafc527bf85.png