二叉树-树和二叉树的基本概念_树与二叉树_玉兔阿离的博客-程序员资料

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

1、有一个特殊的结点，称为根结点，根节点没有前驱结点
2、除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。因此，树是递归定义的。

1.2 树的相关概念

1.3 树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

1.4 树在实际中的运用（表示文件系统的目录树结构）

2.二叉树概念及结构

2.1概念

一棵二叉树是结点的一个有限集合，该集合:
1. 或者为空
2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

从上图可以看出：
1. 二叉树不存在度大于2的结点

2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

注意：对于任意的二叉树都是由以下几种情况复合而成的：

2.2现实中的二叉树：

2.3 特殊的二叉树：

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是，则它就是满二叉树。
2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

2.4 二叉树的性质

2.4.1 5道练习加深领悟

二叉树中度为0的节点总比度为2的节点多一个，叶子节点个数 = 199 + 1 = 200

堆是采用数组存放的，队列是链表，栈是顺序表，都是顺序存储结构，非完全二叉树不适合采用数组进行存储，会造成空间浪费

设度为0的节点个数n0，度为1的节点个数n1，度为2的节点个数n2，则n0 + n1 + n2 = 2n，由二叉树性质，n0 = n2 + 1，所以2n2 + n1 + 1 = 2n，又因为n1 = 0 / 1，所以n1 = 1，n2 = n - 1，n0 = n

套出来结果是10

和第3题本质一样，列个方程就出来了，算出来384

2.5 二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

2.5.1 顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

2.5.2 链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，当前学习中一般都是二叉链，后面学到高阶数据结构如红黑树等会用到三叉链。

3. 总结

需要了解树和二叉树的概念以及存储结构，二叉树的一些结论要记住。以及一些简单的计算，如上述的5道计算题，可以更好的了解二叉树的性质。

本文链接：https://blog.csdn.net/C_TQH/article/details/124679967

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

定时器的问题_antd 定时器一次显示一行_lannieZ的博客-程序员资料

在a页面写一个定时，让他每秒钟打印一个1，然后跳转到b页面，此时可以看到，定时器依然在执行。这样是非常消耗性能的！解决方法1：首先在data函数里面进行定义定时器名称：data() { return { timer: null // 定时器名称 } }使用this.timer = (() => { // 某些定时器操作}, 10

android:cacheColorHint=“#00000000”_屌丝男士zkc的博客-程序员资料

istView.setCacheColorHint(0); 或者Android:cacheColorHint="#000000" 去除listview的拖动背景色自定义listview的时候，当你不使用android:cacheColorHint=“#00000000”会出现下面选中一个空间黑色底色的情况，破坏整体美观度：当你不使用android:listSel

frida之HOOK篇（二）手动hook_frida之hook篇(二)手动hook_kfyzjd2008的博客-程序员资料

一、编写测试用APPpackage com.example.helloworld;import androidx.appcompat.app.AppCompatActivity;import android.os.Bundle;import android.view.View;import android.widget.Button;import android.widget.TextView;public class MainActivity extends AppCompatAc

DVD提取字幕的简要流程及涉及的主要工具_雪峰的博客-程序员资料

1、DVD拷盘用 DVD Decrypter，得到VOB文件2、从VOB中提取图形型字幕用 VobSub，得到 idx和sub配对的图形字幕文件3、图形型字幕转换成文本型用 SubOCR，得到 srt 字幕文件4、校对字幕用 Subtitle Workshop，得到翻译精准的 srt 字幕文件5、如果要加上字幕效果把 srt 字幕文件转换成SSA或ASS字幕，还可以用Subtitle Works

学习音视频开发_音视频开发培训哪家强_ChloeDimen的博客-程序员资料

最近公司开发音视频项目，用到了很多关于音视频的开发技术。总之，我都很难下手。上网查了有一篇很好的的音视频开发任务列表。我准备按照任务列表去实践所有的任务。1:：Android 音视频开发(一) : 通过三种方式绘制图片2：Android 音视频开发(二) : 音频采集和播放3：Android音视频开发 (三)：使用 Camera API 进行视频的采集，分别使用 SurfaceVi...

CentOS7搭建NTP服务器及客户端同步时间_freq_mode_hellboy0621的博客-程序员资料

在配置时钟同步服务器时第一次同步时间时，使用ntpdate命令；后续通过ntpd服务与服务器同步时间。一、搭建NTP服务器1、查看服务器、客户端操作系统版本[[email protected] ~]# cat /etc/redhat-releaseCentOS Linux release 7.5.1804 (Core)2、查看服务器是否安装ntp，系统默认安装ntpdate；[[email protected]...

二叉树-树和二叉树的基本概念_树与二叉树_玉兔阿离的博客-程序员资料

前言：

1.树概念及结构

1.1树的概念

1.2 树的相关概念

1.3 树的表示

1.4 树在实际中的运用（表示文件系统的目录树结构）

2.二叉树概念及结构

2.1概念

2.2现实中的二叉树：

2.3 特殊的二叉树：

2.4 二叉树的性质

2.4.1 5道练习加深领悟

2.5 二叉树的存储结构

2.5.1 顺序存储

2.5.2 链式存储

3. 总结

智能推荐

定时器的问题_antd 定时器一次显示一行_lannieZ的博客-程序员资料

android:cacheColorHint=“#00000000”_屌丝男士zkc的博客-程序员资料

frida之HOOK篇（二）手动hook_frida之hook篇(二)手动hook_kfyzjd2008的博客-程序员资料

DVD提取字幕的简要流程及涉及的主要工具_雪峰的博客-程序员资料

学习音视频开发_音视频开发培训哪家强_ChloeDimen的博客-程序员资料

CentOS7搭建NTP服务器及客户端同步时间_freq_mode_hellboy0621的博客-程序员资料

随便推点

常用端口号与对应的服务以及端口关闭_111端口是什么服务_hanghangde的博客-程序员资料

数据结构实验之排序七：选课名单_猿憨憨的博客-程序员资料

Cocos2d-x3.0游戏实例之《别救我》第五篇——使用Cocostudio UI编辑器创建操作界面_linuxheik的博客-程序员资料

好久没学习了。。。_和稀泥的博客-程序员资料

Delphi 2006 高级控件应用_delphi怎么添加rztray控件_voyan的博客-程序员资料

xinetd不太详的详解_changkejia的博客-程序员资料

推荐文章

热门文章

相关标签