数据结构与算法:树 顺序存储二叉树(二)

Tips: 采用java语言,关注博主,底部附有完整代码

工具:IDEA

本系列介绍的是数据结构: 树

这是第二篇目前计划一共有12篇:

1. 二叉树入门
2. 顺序二叉树 (本篇)
3. 线索化二叉树
4. 堆排序
5. 赫夫曼树(一)
6. 赫夫曼树(二)
7. 赫夫曼树(三)
8. 二叉排序树
9. 平衡二叉树
10. 2-3树,2-3-4树,B树 B+树 B*树 了解
11. 红黑树(一)
12. 红黑树(二)

敬请期待吧~~

介绍: 顺序存储二叉树,就是将一串数组,以完全二叉树的结构可以前序,中序,后续遍历即可!

小技巧:

• 数组是从上至下,从左至右一层一层排列的!结点全部靠左,所以是一颗完全二叉树!
• 假设当前n的下标是4
  • 左子结点 = 2n + 1
  • 右子结点 = 2n + 2
  • 父结点 = (n - 1 ) / 2

如图所示:

下标n为4的值是45

那么他的左子结点就是 2n + 1, 下标就是9,值是63

那么他的右子结点就是 2n + 2 下标就是10 值是28

那么他的父结点就是 (n - 1 ) / 2 下标就是1 值是23

再来看一张图:

n = 下标

假设当前下标是7

他的左子结点是 2n+1 ,左子结点对应的下标是15 (下标从0开始计算)

现在数组长度是15

所以说没有左子结点

顺序存储二叉树必须是一颗完全二叉树,没有左子结点,他必然没有右子结点,

所以他一定是叶子结点!

现在遍历一颗树的必要条件都满足了:

• 左子结点 : 2n + 1
• 右子结点: 2n + 2
• 父结点: (n-1) / 2
• 左叶子结点: (2n + 1) < ints.length
• 右叶子结点: (2n + 2) < ints.length

那么就直接上代码了!

# 前序遍历:
public static void main(String[] args) {
    int[] ints = {666, 3, 5, 12, 4, 23, 8, 53, 123, 34, 285, 83};

    // n = 4
    // n.left = 2n + 1
    //        = 9

    // n.right = 2n + 2
    //         = 10

    // n.parent = (n - 1) / 2
    //          = 3 / 2 = 1

    // 顺序二叉树只考虑完全二叉树
    // 第n个左子节点为 2n + 1
    // 第n个右子节点为 2n + 2
    // 第n个父节点为 (n - 1) / 2
    // n 表示二叉树的第几个元素
    pre(ints, 0);
}

public static void pre(int[] ints, int index) {
    // 前序
    System.out.println(ints[index]);


    int leftIndex = 2 * index + 1;
    // 判断是否是叶子结点
    if (leftIndex < ints.length) {
       // 向左遍历
        pre(ints, leftIndex);
    }

    int rightIndex = 2 * index + 2;
    // 判断是否是叶子结点
    if (rightIndex < ints.length) {
        // 像右遍历
        pre(ints, rightIndex);
    }
}

本篇比较短小,因为这个是最简单的一个,后面慢慢的就难了,加油!

完整代码

原创不易,您的点赞就是对我最大的支持!

下一篇:线索化二叉树[开发中…]