【数据结构】顺序查找树节点计算思路与遍历详解

前言

觉得文章有帮助的话，麻烦随手留下点赞收藏吧，关注小冷看更多干货学习文章

★ 这里是小冷的博客 ✓ 优质技术好文见专栏个人公众号，分享一些技术上的文章，以及遇到的坑当前系列：数据结构系列源代码 git 仓库数据结构代码地址代码Git 仓库地址

顺序存储二叉树

顺序存储二叉树的概念

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

上图的二叉树的结点，要求以数组的方式来存放 arr : [1, 2, 3, 4, 5, 6, 6] 2) 要求在遍历数组 arr 时，仍然可以以前序遍历，中序遍历和后序遍历的方式完成结点的遍历

顺序存储二叉树的特点:

顺序二叉树通常只考虑完全二叉树
第 n 个元素的左子节点为 2 * n + 1（计算公式）
第 n 个元素的右子节点为 2 * n + 2 （计算公式）
第 n 个元素的父节点为 (n-1) / 2
n : 表示二叉树中的第几个元素

顺序存储二叉树遍历

需求

给你一个数组 {1,2,3,4,5,6,7}，要求以二叉树前序遍历的方式进行遍历。

前序遍历的结果应当为 1,2,4,5,3,6,7

编码思路

这里判断的思路首先是有一个数组转变成树看待的思想，

数组： 1,2,3,4,5,6,7

树（如下图）

第 n 个元素的左子节点为 2 * n + 1（计算公式）
第 n 个元素的右子节点为 2 * n + 2 （计算公式）

我们可以用这个公式来证明一下，数组转树的正确性

比如我们要计算二的位置，2是1的左子节点，1是下标为0的元素 2*0+1 套用公式 = 1，之后的节点同理

代码实现

代码语言：javascript

复制

package com.hyc.DataStructure.tree;
/**

@projectName: DataStructure
@package: com.hyc.DataStructure.tree
@className: ArrayTreeDemo
@author: 冷环渊 doomwatcher
@description: TODO
@date: 2022/2/4 19:07
@version: 1.0

*/

public class ArrayTreeDemo {

public static void main(String[] args) {

int[] arr = {1, 2, 3, 4, 5, 6, 7};

ArrayTree arrayTree = new ArrayTree(arr);

//452 6731

arrayTree.postOrder(0);

}

}

class ArrayTree {

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

//    顺序存储树的前序遍历
// 遍历公式 找到n的第n个左结点 n*2+1 找到n的第n个右节点 n*2+2
// 输入参数 int index 为开始遍历到根节点 即为 数组下标0
public void preOrder(int index) {
    //非空判断 避免空指针
    if (arr == null || arr.length == 0) {
        System.out.println(&#34;该树 为空 不能遍历&#34;);
    }
    //    前序遍历先输出自己
    System.out.println(arr[index]);
    //    之后递归遍历左结点
    //判断index 是否越界
    if ((2 * index + 1) &lt; arr.length) {
        preOrder(index * 2 + 1);
    }
    //    之后递归遍历右边结点
    //判断index 是否越界
    if ((2 * index + 2) &lt; arr.length) {
        preOrder(index * 2 + 2);
    }
}

public void infixOrder(int index) {
    //非空判断 避免空指针
    if (arr == null || arr.length == 0) {
        System.out.println(&#34;该树 为空 不能遍历&#34;);
    }
    //    递归遍历左结点
    //判断index 是否越界
    if ((2 * index + 1) &lt; arr.length) {
        infixOrder(index * 2 + 1);
    }
    //    中序遍历输出自己
    System.out.println(arr[index]);
    //    递归遍历右边结点
    //判断index 是否越界
    if ((2 * index + 2) &lt; arr.length) {
        infixOrder(index * 2 + 2);
    }
}

public void postOrder(int index) {
    //非空判断 避免空指针
    if (arr == null || arr.length == 0) {
        System.out.println(&#34;该树 为空 不能遍历&#34;);
    }
    //    递归遍历左结点
    //判断index 是否越界
    if ((2 * index + 1) &lt; arr.length) {
        postOrder(index * 2 + 1);
    }
    //    递归遍历右边结点
    //判断index 是否越界
    if ((2 * index + 2) &lt; arr.length) {
        postOrder(index * 2 + 2);
    }
    //    后序遍历输出自己
    System.out.println(arr[index]);
}

}

这里我们先了解顺序存储二叉树，并且掌握他的节点计算思路和遍历思路，小冷之后的文章堆排序的时候会进行知识点的使用，提前预热