个人主页：【😊个人主页】
系列专栏：【❤️数据结构与算法】
学习名言：在寻求真理的长河中，唯有学习，不断地学习，勤奋地学习，有创造性地学习，才能越重山跨峻岭。——华罗庚

系列文章目录

第一章 ❤️ 学前知识
第二章 ❤️ 单向链表
第三章 ❤️ 递归
…

前言

二叉树

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分 。

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。
二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。
二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点 。

相关概念

节点：包含一个数据元素及若干指向子树分支的信息。
节点的度：一个节点拥有子树的数目称为节点的度。
叶子节点：也称为终端节点，没有子树的节点或者度为零的节点。
分支节点：也称为非终端节点，度不为零的节点称为非终端节点。
树的度：树中所有节点的度的最大值。
节点的层次：从根节点开始，假设根节点为第1层，根节点的子节点为第2层，依此类推，如果某一个节点位于第L层，则其子节点位于第L+1层 。
树的深度：也称为树的高度，树中所有节点的层次最大值称为树的深度。
有序树：如果树中各棵子树的次序是有先后次序，则称该树为有序树。
无序树：如果树中各棵子树的次序没有先后次序，则称该树为无序树。
森林：由m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根节点删除，则该树就变成了一片森林，森林中的树
由原来根节点的各棵子树构成。

二叉树的性质

1:二叉树的第i层上至多有2i-1（i≥1）个节点 。
2：深度为h的二叉树中至多含有2h-1个节点 。
3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1。
4：具有n个节点的满二叉树深为log2n+1。
5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点:
当i=1时，该节点为根，它无双亲节点。
当i>1时，该节点的双亲节点的编号为i/2。
若2i≤n，则有编号为2i的左节点，否则没有左节点。
若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点

二叉树的五种基本形态

我们知道二又树是有限元素的集合，该集合或者为空，或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。

空二叉树

当集合为空时，称该二又树为空二又树（顾名思义它什么都没有🤪🤪🤪）

只有一个根节点的二叉树

显然它只有一个根结点

没有任何结点的树才是空二叉树

只有根节点和左子树TL的二叉树

每个有孩子的结点都只有左孩子结点的二叉树

只有根节点和右子树TR的二叉树

每个有孩子的结点都只有右孩子结点的二叉树

完全二叉树

完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。

叶子结点只能出现在最下层和次下层。
最下层的叶子结点集中在树的左部。
倒数第二层若存在叶子结点，一定在右部连续位置。
如果结点度为1，则该结点只有左孩子，即没有右子树。
同样结点数目的二叉树，完全二叉树深度最小。

特殊的二叉树

在二叉树的这个大家族中肯定存在一些特殊的例子，它们有着二叉树的性质，却又与众不同。

满二叉树

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的深度为K，且结点总数是(2^k) -1 ，则它就是满二叉树。(一棵满二叉树的每一个结点要么是叶子结点，要么它有两个子结点，但是反过来不成立，因为完全二叉树也满足这个要求，但不是满二叉树)
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

有意思的是在国外教材中关于满二叉树的定义是这样的：a binary tree T is full if each node is either a leaf or possesses exactly two childnodes.（如果一棵二叉树的结点要么是叶子结点，要么它有两个子结点，这样的树就是满二叉树）

叶子只能出现在最下一层。出现在其它层就不可能达成平衡。
非叶子结点的度一定是2。
在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

斜二叉树

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

度为1；
只有左子节点或右子节点；

小结

好了关于二叉树的基本知识就讲到这了，关于二叉树的更多内容未来我会持续更新，希望这篇文章对你有帮助，下次见

（部分文字与图片来源于网络，侵权请联系删除）