05-5.2.1_1 二叉树的定义和基本术语

• 👋 Hi, I’m @Beast Cheng
• 👀 I’m interested in photography, hiking, landscape…
• 🌱 I’m currently learning python, javascript, kotlin…
• 📫 How to reach me --> 458290771@qq.com

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑‍💻
此外，《程序员必备技能》专栏日后会逐步更新，感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏

二叉树的基本概念

二叉树是 $n(n\ge 0)$ 个结点的有限集合：

1. 或者为空二叉树，即 $n=0$
2. 或者由一个根节点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树
   特点：
3. 每个结点至多只有两棵子树
4. 左右子树不能颠倒（二叉树是有序树 ）

几个特殊的二叉树

满二叉树

满二叉树：一棵高度为 h，且含有 $2^h-1$ 个结点的二叉树
特点：

1. 只有最后一层有叶子结点
2. 不存在度为 1 的结点
3. 按层序从 1 开始编号，结点 i 的左孩子为 2i，右孩子为 2i+1，结点 i 的父结点为 i/2（如果有的话）

完全二叉树

完全二叉树：当且仅当其每个结点都与高度为 h 的满二叉树中编号 1~n 的结点一一对应时，称为完全二叉树
特点：

1. 只有最后两层可能有叶子结点
2. 只可能有一个度为 1 的结点
3. 与满二叉树的第三点相同
4. $i\le \frac{n}{2}$ 为分支结点，$i>\frac{n}{2}$ 为叶子结点
   对于完全二叉树来说，如果某结点有一个孩子，那么这个孩子一定是左孩子而不是右孩子

二叉排序树

二叉排序树：一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：

• 左子树 上的所有结点的 关键字 均 小于 根结点的关键字；
• 右子树 上的所有结点的 关键字 均 大于 根结点的关键字；
• 左子树和右子树又各是一棵二叉排序树
  二叉排序树可以用于元素的排序、搜索

平衡二叉树

平衡二叉树：树上任一结点的左子树 和右子树 的深度之差不超过 1
如：左子树深度 = 2，右子树深度 = 3，那么就是平衡二叉树
平衡二叉树能有更高的搜索效率