专栏首页算法半岛数据结构与算法-二叉树(一)

数据结构与算法-二叉树(一)

二叉树的理解

在理解树的基本概念和结构后接下来我们学习最常用的一种树——二叉树,如下图所示:

从图中可以观察到,每个节点最多有两个分支,也就是两个节点,一般称为左子节点右子节点。注意,是最多有两个节点,而不是必须有两个节点。像上图中的C节点只有一个节点(右子节点)。

完全二叉树和满二叉树

在二叉树中有两种特殊的二叉树,分别是完全二叉树和满二叉树。

完全二叉树

如上图所示,节点F、G、H、I和J是叶子节点,这些叶子节点都在最后的两层,最后一层的叶子节点靠左排列,并且除最后一层外,其他层的节点个数达到最大,这样的二叉树即为完全二叉树

满二叉树

如上图所示,节点D、E、F和G是叶子节点,这些叶子节点都在最后一层,且除了叶子节点外其他的节点都有左右两个子节点,这样的二叉树即为满二叉树

二叉树的存储方式

对于二叉树的存储,可以通过链式存储法顺序存储法分别存储。

链式存储法

观察上图可以知道,对于每个节点有三个字段,其中 data表示存储数据, left表示指向左子节点的指针, right表示指向右子节点的指针。如果我们知道了一颗二叉树的根节点,则我们可以通过左右子节点的指针进行查找。大部分的二叉树的代码都是通过链式存储法来实现的。

顺序存储法

观察上图可以知道,当二叉树中的某一个节点 index为i,则它的左子节点的 index2*i+1,它的右子节点的 index2*i+2,它的父节点的 indexi/2。因此,我们只要知道根节点的 index,则可以通过上述表达式进行查找。对于使用顺序存储法时,需要申请连续的内存空间,因此对于节点个数不多完全二叉树和满二叉树比较合适,但是对于不完全二叉树就会造成大量的空间浪费。

二叉树的前序遍历、中序遍历和后序遍历

在对二叉树遍历时,前序、中序和后序是指当前节点与它的左右子节点的打印现后顺序

  • 前序遍历:先打印当前节点,然后打印左子树,最后打印右子树。当前节点 -> 左子树 -> 右子树;
  • 中序遍历:先打印左子树,然后打印当前节点,最后打印右子树。左子树 -> 当前节点 -> 右子树;
  • 后序遍历:先打印左子树,然后打印右子树,最后打印当前节点。左子树 -> 右子树 -> 当前节点。

对上面二叉树的打印顺序分别为:

  • 前序遍历:A -> B -> D -> E -> C -> F -> G
  • 中序遍历:D -> B -> E -> A -> F -> C -> G
  • 后序遍历:D -> E -> B -> F -> G -> C -> A

本文分享自微信公众号 - 算法半岛(jacob2359),作者:算法半岛

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构与算法-树

    用户3470542
  • 数据结构与算法-二叉树(二)

    二叉查找树是一种特殊的二叉树,它支持动态的数据集合的快速插入、删除和查找操作。二叉查找树的一般结构如下图所示:

    用户3470542
  • 数据结构与算法-跳表

    在学习二分查找时,我们知道二分查找需要依赖数组的随机访问的特性进行查找,而链表不具有随访问的特性,因此不能使用传统上的二分查找方法了。为了使得链表支持类...

    用户3470542
  • 算法与数据结构(三) 二叉树的遍历及其线索化(Swift版)

    前面两篇博客介绍了线性表的顺序存储与链式存储以及对应的操作,并且还聊了栈与队列的相关内容。本篇博客我们就继续聊数据结构的相关东西,并且所涉及的相关Demo依然使...

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

    我是程序员小贱
  • 数据结构二叉树知识点总结

    郭耀华
  • 二叉树遍历的应用:判断二叉树的类别

    昨天的文章讲述了二叉树的先序、中序和后序的遍历方法(递归和非递归),但是这种遍历方法有什么意义么?今天来讲讲这些算法可以用来做什么,只要稍加更改,我们就可以得到...

    算法工程师之路
  • 数据结构二叉树知识点总结

    术语  1. 节点的度:一个节点含有的子树的个数称为该节点的度; 2. 叶节点或终端节点:度为零的节点;  3. 非终端节点或分支节点:度不为零的节点;  4....

    郭耀华
  • [小技巧]巧妙使用flex, letter-spacing实现过渡动画

    本文作者:IMWeb DeepKolos 原文出处:IMWeb社区 未经同意,禁止转载 巧妙利用flex, 实现下面的效果~ 无需js来获取clien...

    IMWeb前端团队
  • [小技巧]巧妙使用flex, letter-spacing实现过渡动画

    有时候会做一些小的宽度变换, 比如居中到居左的变换, 例如上面的搜索的placeholder

    IMWeb前端团队

扫码关注云+社区

领取腾讯云代金券