数据结构——二叉树

举报
秋名山码民 发表于 2022/08/31 15:40:21 2022/08/31
【摘要】 前言经过前几天的学习,我们对树这个基本数据结构也有了初步的了解,今天让我们一起来看树中比较难的二叉树,有句玩笑话叫”大学有俩棵树,上面挂了好多人,一棵二叉树,一棵高数“,也可以看出二叉树的难度,但是遇难我们更强,开始今天的学习! 二叉树定义特点: - 每个结点'最多'有俩棵子树 - 左右子树都是有顺序的,不能任意颠倒 - 即使只有一棵子树,也要区分它是左子树还是右子树一般情况下,有以...

前言

经过前几天的学习,我们对树这个基本数据结构也有了初步的了解,今天让我们一起来看树中比较难的二叉树,有句玩笑话叫”大学有俩棵树,上面挂了好多人,一棵二叉树,一棵高数“,也可以看出二叉树的难度,但是遇难我们更强,开始今天的学习!

二叉树定义

特点:

  - 每个结点'最多'有俩棵子树
  - 左右子树都是有顺序的,不能任意颠倒
  - 即使只有一棵子树,也要区分它是左子树还是右子树

一般情况下,有以下几种基本形态

  • 空二叉树,没有办法画图了

  • 只有一个根结点
    在这里插入图片描述

  • 根结点只有左子树
    在这里插入图片描述

  • 根结点只有右子树
    在这里插入图片描述

  • 根结点既有左子树又有右子树
    在这里插入图片描述
    再思考一下,如果有三个结点的二叉树,又有几种形态呢?
    5种,怎么来的?先看图
    请添加图片描述

由于他必须是有序的所以要单个计算,左右分开,加起来就是5种
下面来说几个特殊的二叉树:

  • 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是(2^k) -1 ,则它就是满二叉树。

  • 完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树

  • 斜树:有点像线性表,这个斜可以不分左右,所以更像线性表了

如何判断完全二叉树,下面是它的特征:

  • 叶子结点只能出现在最下俩层、
  • 最下层的叶子一定集中在左部的连续位置
  • 倒数俩层,若有叶子结点,一定都在右部连续位置
  • 如果结点度为一,则该结点只有左孩子
  • 同样结点数的二叉树,完全二叉树的深度最小

树的几种遍历方式

  • 前序遍历
  • 中序遍历
  • 后序遍历

数据结构——二叉树先序、中序、后序及层次四种遍历(C语言版)

刷题巩固

二叉树的前序遍历
二叉树的中序遍历
二叉树的后序遍历
二叉树的最大深度

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。