二叉树、完全二叉树、完满二叉树、满二叉树

二叉树、完全二叉树、完满二叉树、满二叉树简单定义 每个节点最多只有 2 个子节点的树叫做二叉树

大家好,欢迎来到IT知识分享网。

目录

一. 前言

二. 二叉树

2.1. 定义

2.2. 特点

2.3. 性质

三. 分类

3.1. 斜树

3.2. 完全二叉树(Complete)

3.3. 完满二叉树(Full)

3.4. 满二叉树(Perfect)

四. 存储类型

五. 遍历种类 


一. 前言

    前一篇我们介绍了树的概念及结点的概念,参见《数据结构-树》,树是数据结构中的重中之重,尤其以各类二叉树为学习的难点。一直以来,对于树的掌握都是模棱两可的状态,现在希望通过写一个关于二叉树的文章,在学习与总结的同时更加深入的了解掌握二叉树。

二. 二叉树

2.1. 定义

    简单定义:每个节点最多只有2个子节点的树叫做二叉树。

    专业定义:二叉树是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。

    下图为一棵普通二叉树

    二叉树、完全二叉树、完满二叉树、满二叉树

2.2. 特点

2.3. 性质

一个编号为 i 的结点有如下特性:

三. 分类

3.1. 斜树

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

左斜树

二叉树、完全二叉树、完满二叉树、满二叉树

右斜树

二叉树、完全二叉树、完满二叉树、满二叉树

3.2. 完全二叉树(Complete)

对一颗具有n个结点的二叉树按层编号,如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树。

 二叉树、完全二叉树、完满二叉树、满二叉树

3.3. 完满二叉树(Full)

除了叶子结点之外的每一个结点都有两个孩子,每一层(当然包含最后一层)都被完全填充。

二叉树、完全二叉树、完满二叉树、满二叉树

3.4. 满二叉树(Perfect)

满二叉树又叫完美二叉树,在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。

二叉树、完全二叉树、完满二叉树、满二叉树

四. 存储类型

顺序存储:二叉树的顺序存储结构就是使用一维数组存储二叉树中的结点,并且结点的存储位置,就是数组的下标索引。

二叉链表:如果顺序存储不能满足二叉树的存储需求,那么考虑采用链式存储。由二叉树定义可知,二叉树的每个结点最多有两个孩子。因此,可以将结点数据结构定义为一个数据和两个指针域。

二叉树、完全二叉树、完满二叉树、满二叉树

五. 遍历种类 

二叉树的遍历是指从二叉树的根结点出发,按照某种次序依次访问二叉树中的所有结点,使得每个结点被访问一次,且仅被访问一次。

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://haidsoft.com/136021.html

(0)
上一篇 2025-06-30 16:33
下一篇 2025-06-30 16:45

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信