目录介绍

• 01.二叉树存储方式
• 02.链式存储
• 03.顺序存储

01.二叉树存储方式

• 存储一棵二叉树有两种方法，一种是基于指针或是引用的二叉链式存储法，一种是基于数组的顺序存储法。

02.链式存储

• 从图中可以看到，每个节点有三个字段，一个存储数据，另外两个是指向左右子节点的指针。只要知道了根节点，就可以通过左右子节点的指针把整棵二叉树串起来。这种存储方式比较常用，大部分二叉树代码都是基于这种存储结构实现的。
  • 
    image

03.顺序存储

• 根节点存储在下标为i = 1的位置，那左子节点存储在下标2i = 2 的位置，右子节点存储在下标为2i+1 = 3 的位置。以此类推，B节点的左子节点存储在2i = 22 = 4的位置，右节点存储在2i+1 = 22+1=5的位置。
  • 
    image
• 总结：如果节点x存储在下标为i的位置，那么该节点的左节点存储在下标为2i的位置，右子节点存储在下标为2i+1的位置。反过来，下标i/2的位置，存储的就是该节点的父节点。通过这种方式，只要知道根节点的存储位置。就可以通过下标计算，把整棵树串起来。
• 上面是一棵完全二叉树，仅仅浪费了一个下标为0的存储位置。如果是非完全二叉树，其实会浪费比较多的数组存储空间。例如下面这课非完全二叉树，下标为0，5，7，10，11，12的存储空间，会浪费掉。
  • 
    image
• 所以完全二叉树更适合用数组来存储。

其他内容

01.关于博客汇总链接

• 1.技术博客汇总
• 2.开源项目汇总
• 3.生活博客汇总
• 4.喜马拉雅音频汇总
• 5.其他汇总

02.关于我的博客

• github：https://github.com/yangchong211
• 知乎：https://www.zhihu.com/people/yczbj/activities
• 简书：http://www.jianshu.com/u/b7b2c6ed9284
• csdn：http://my.csdn.net/m0_37700275
• 喜马拉雅听书：http://www.ximalaya.com/zhubo/71989305/
• 开源中国：https://my.oschina.net/zbj1618/blog
• 泡在网上的日子：http://www.jcodecraeer.com/member/content_list.php?channelid=1
• 邮箱：yangchong211@163.com
• 阿里云博客：https://yq.aliyun.com/users/article?spm=5176.100- 239.headeruserinfo.3.dT4bcV
• segmentfault头条：https://segmentfault.com/u/xiangjianyu/articles
• 掘金：https://juejin.im/user/5939433efe88c2006afa0c6e