大家好,欢迎来到IT知识分享网。
目录
一. 前言
前一篇我们介绍了树的概念及结点的概念,参见《数据结构-树》,树是数据结构中的重中之重,尤其以各类二叉树为学习的难点。一直以来,对于树的掌握都是模棱两可的状态,现在希望通过写一个关于二叉树的文章,在学习与总结的同时更加深入的了解掌握二叉树。
二. 二叉树
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