【数据结构】什么是二叉树?

举报
修修修也 发表于 2024/09/30 16:41:38 2024/09/30
【摘要】 ​ 🦄个人主页:修修修也 🎏所属专栏:数据 结 构 ⚙️操作环境:Visual Studio 2022​编辑目录📌 二叉 树 的定 义 📌 二叉 树 的特点 📌 特殊二叉 树 📌 二叉 树 的性 质 📌 二叉 树 的存 储结 构 📌 二叉 树 的遍 历 前序遍 历 中序遍 历 后序遍 历 层 序遍 历 结语 📌二叉树的定义二叉树(Binary Tree)是n(n≥0)个结点...

 

🦄个人主:修修修也

🎏所属专栏:数据

⚙️操作:Visual Studio 2022

​编辑


📌 二叉 的定

📌 二叉 的特点

📌 特殊二叉

📌 二叉 的性

📌 二叉 的存 储结

📌 二叉 的遍

前序遍

中序遍

后序遍

序遍

结语


📌二叉的定

二叉(Binary Tree)是n(n≥0)点的有限集合,集合或者空集(称空二叉),或者由一个根点和两互不相交的,分点的左子和右子的二叉树组.

 二叉树逻辑结构如下图所示:

​编辑


📌二叉的特点

二叉的特点有:

每个点最多有两棵子,所以二叉存在度大于2的.注意不是只有两,而是最多有.没有子或者有一都是可以的.

左子和右子是有序的,次序不能任意.

即使中某个点只有棵子,也要区分它是左子是右子.下1和2是同一颗树,但它却是不同的二叉:​编辑

二叉树具有五种基本形态:

1. 空二叉.

2. 只有一个根.

3. 点只有左子.

4. 只有右子.

5. 点既有左子有右子.

只有三个点的二叉,有几种形态?

答案是有以下5种形:

​编辑


📌特殊二叉

        所有的点都只有左子的二叉左斜.所有点都是只有右子的二叉叫右斜.两者.上图中的树2就是左斜树,树3就是右斜树.

只有一个,点的个数与二叉的深度相同.

二叉

        在一棵二叉,如果所有分支点都存在左子和右子,并且所有叶子都在同一,这样的二叉为满二叉.

如下图所示,该树就是一颗满二叉树:​编辑

注意,单是每个结点都存在左右子树,不能算是满二叉树,还必须要所有的叶子都在同一层上,这就做到了整棵树的平衡.

因此,二叉的特点有:

1. 叶子只能出在最下一.出在其他就不可能达成平衡.

2. 非叶子点的度一定是2.

3. 在同深度的二叉,二叉点个数最多,叶子数最多.

完全二叉

        具有n点的二叉,如果i(1≤i≤n)的点与同深度的二叉i点在二叉中位置完全相同,则这颗二叉完全二叉,如下图所示:

​编辑

完全二叉的特点有:

1. 叶子点只能出在最下两.

2. 最下的叶子一定集中在左部连续位置.

3. 倒数二,若有叶子,一定都在右部连续位置.

4. 如果点度1,则该结点只有左孩子,即不存在只有右子的情况.

5. 样结点数的二叉,完全二叉的深度最小.


📌二叉的性

性质1:

        在二叉的第i上至多有(i≥1).


推导如下:

​编辑

性质2:

        深度k的二叉至多有(k≥1).


推导如下:

​编辑

性质3:
        任何一二叉T,如果其点数,度2的点数,.


终端结点数其实就是叶子节点数,一颗二叉树,只会存在度为0,度为1,度为2的结点,我们假设度为1的节点数为,则树T结点总数.

性质4:

        具有n点的完全二叉的深度  , (表示不大于x的最大整数).


我们由满二叉树的定义可知,深度为k的满二叉树的结点数n一定是.因为这是最多的结点个数.那么对于倒推可得满二叉树的深度数为.

而对于完全二叉树而言,它的节点数一定少于等于同样深度数的满二叉树的结点数,但一定多于.即满足.易推导得.

性质5:

        如果n点的完全二叉(其深度)的点按(从第1到第,每从左到右),i(1≤i≤n)有:

1. 如果i=1,则结i是二叉的根,无双;如果i>1,其双.

2. 如果2*i>n,则结i无左孩子(i叶子);否左孩子2*i.

3. 如果2*i+1>n,则结i右孩子;否其右孩子是2*i+1.


📌二叉的存储结

序存储结

        二叉序存储结构就是用一二叉中的,并且点的存位置,也就是数的下要能体现结点之逻辑关系.

先来看看完全二叉树的顺序存储,一颗完全二叉树如下图:

​编辑

将这颗二叉树存到数组中,相应的下标对应其同样的位置:

​编辑

但如果遇到树中不存在的结点,我们也可在顺序结构中存入"^"或空,来表示该结点不存在:

​编辑

序存储结适用于完全二叉.因,在最坏的情况下,一个深度k且只有k点的(即存在度2的)却需要的一:

​编辑


二叉

        因二叉每个点最多有两个孩子,所以它的设计一个数据域和两个指,分指向两个孩子,我这样叫做二叉.

如下:

​编辑

二叉链表结构定义代码如下:

typedef struct BiTNode

{

TElemType data; //数据域

struct BiTNode*left; //左孩子指针域

struct BiTNode*right; //右孩子指针域

}BiTNode;


📌二叉的遍

二叉的遍(traversing binary tree)是指从根点出,按照某种次序依次访问二叉中所有,使得每个点被访问一次且只访问一次.

前序遍

        前序遍历的规则是:若二叉树为空,则空操作返回,否则访问,然后前序遍左子,再前序右子.

如下图所示,遍历的顺序为:ABDGHCEIF

​编辑


中序遍

        中序遍历的规则是:若二叉树为空,则空操作返回,否则点开始(注意不是先访问根节点)先中序遍点的左子,然后访问,最后中序遍右子.

如下图所示,遍历的顺序为:GDHBAEICF

​编辑


后序遍

        后序遍历的规则是:若二叉树为空,则空操作返回,否则左到右先叶子后点的方式遍历访问左右子,最后是访问.

如下图所示,遍历的顺序为:GHDBIEFCA

​编辑


序遍

        层序遍历的规则是:若二叉树为空,则空操作返回,否则的第一,也就是根点开始访问,从上而下逐,在同一,按从左到右的对结点逐个访问.

如下图所示,遍历的顺序为:ABCDEFGHI

​编辑


结语

希望二叉的介大家有所帮助,迎大佬留言或私信与我交流.

学海漫浩浩,我亦苦作舟!关注我,大家一起学,一起!

相关文章推荐

【数据 构】什么是 ?

【数据 构】什么是 线 性表 ?

【数据 构】什么是 ?

【数据 构】用 C 实现顺 (附完整运行代 )

【数据 构】深入浅出理解 表中二

【数据 构】 10道 典面 试题 你玩 转链


​编辑

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

评论(0

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

全部回复

上滑加载中

设置昵称

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

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

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