今天给二叉树加个BGM,二叉树唱歌了!

2020/11/01 10:44
阅读数 6

前面咱们学习了数组,链表,栈,队列,现在我们开始学习一种非线性结构,它叫做树。那么既然是新东西,我们就需要知道为什么出现树这种数据结构,树这种数据结构解决什么问题,它的应用场景在哪里?

39147659933268e64d49142d4d5ac81d.jpeg

1 树 简介

  • 树为一种非线性结构,所以其各个数据元素不再保持在一个线性序列中,每个数据元素可能与零个或者多个其他数据元素发生联系。

  • 树中每个元素称为结点,为了体现结点之间的关系,分为父节点,子节点,兄弟节点,叶节点,为了更直观的了解这几个基本概念,我们看下图。3f1793e9fd1b28e3e402edda5a7494e2.png

  • 一棵树,有高度,有深度,有层数,基本概念是什么,又是怎么计算的呢?

概念 解析
节点的深度 根节点到此节点所经历边的个数
节点的层数 节点的深度+1
树的高度 根节点的高度
节点的高度 节点到叶子节点的最长路径

为了加深对概念的理解,画个图理解更佳。ef07a2eab5bb8ad2efa35b9962608d0f.jpeg

2 二叉树 简介

二叉树,在树的基础上加了属性词"二叉",两个分支,其实上面咱们所画的树就是二叉树。那么特殊的二叉树值得注意的是完全二叉树满二叉树,如下图所示。

4e5f824475d62571129c61dca60b445c.png

3 二叉树存储方式

3.1 链表存储方式

我们了解了二叉树的一点基本概念后,为了表示节点之间的关系,引入链表结构,用左右两个指针分别指向左节点和右节点,这样就可以串联整个二叉树,如下图所示。

5c3baeab0722cc58de7733fc1e9b5542.png

3.2 数组存储方式

我们知道数组最大的一个特点就是内存连续,方便随机访问,下标通常从0开始。好了,知道这些我们就先看看用数组如何存储一棵二叉树。

a2de6b55f132b06644f5ecb917b71eb8.png

上图我们假设A元素下标为1(机智的小伙伴看到下标是不是就想到了数组下标),那么它左节点B=2*1=2,右节点c=2*1+1=3,依次推理,假设元素p的下标为i,那么元素p的左节点为2i,右节点为2i+1.那么对应于数组是怎样的呢,如下图所示。

3ff3685e580afc462bc62785eafc9ce1.png

3.2 二叉树存储方式小结

上面使用了数组和链表两种方式对二叉树进行存储。如果为完全二叉树,链表存储每个节点需要多两个左右指针,而对数组而言简直是“天籁之音”,它只需要浪费一个如上图下标为0的存储位置。

4 二叉树的遍历

了解了二叉树基本概念,用什么存储后,现在我们看看如何得到我们需要的节点元素,也就是所谓的遍历

4.1 前序遍历

套路:先访问根节点,再访问左子树,最后访问右子树

2570d1daf42a88d36ab2f33629ce6b97.png

4.2 中序遍历

套路:先访问左子树,再访问根节点,最后访问右子树

3d4ad2117633420b1f50ef852c00f99f.png

4.3 后序遍历

套路: 先访问左子树,再访问右子树,最后访问根节点

302ca902bdcde5288e8f31f7288b7802.png

4.4 层次遍历

套路:逐层遍历

74b470b93c994bd8d3078a300634a6c5.png

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部