数据结构-二叉树及其遍历
🚀欢迎来到我的【数据结构】专栏🚀
- 🙋我是小蜗，一名在职牛马。
- 🐒我的博客主页 ➡️ ➡️ 小蜗向前冲的主页
- 🙏🙏欢迎大家的关注，你们的关注是我创作的最大动力🙏🙏
🌍前言
本篇文章咱们聊聊数据结构中的树，准确的说因该是只说一说二叉树以及相关的三种递归遍历、三种非递归遍历以及层次遍历。
🌍目录
一、二叉树的定义
二、特殊的二叉树
1、满二叉树
2、完全二叉树
三、二叉树的遍历及代码
示例图：
前置准备：
1、先序遍历
🫧规则
🫧代码
2、中序遍历
🫧规则
🫧代码
3、后序遍历
🫧规则
🫧代码
4、层次遍历
🫧规则
🫧代码
最终结果（总结）
一、二叉树的定义
🍃二叉树 (BinaryTree) 是 n (n>0) 个结点所构成的集合，它或为空树(n-0)或为非空树，对于非空树 T:
(1) 有且仅有一个称之为根的结点:
(2) 除根结点以外的其余结点分为两个互不相交的子集 TI 和 T2，分别称为 T 的左子树和右子树，且 T1 和 T2 本身又都是二叉树。
🍃二叉树与树一样具有递归性质，二叉树与树的区别主要有以下两点:
(1) 二叉树每个结点至多只有两棵子树(即二叉树中不存在度大于 2 的结点) ;
(2) 二叉树的子树有左右之分，其次序不能任意颠倒。
二叉树的递归定义表明二叉树或为空，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。由于这两棵子树也是二叉树，则由二叉树的定义，它们也可以是空树。由此，二叉树可以有 5 种基本形态：
二、特殊的二叉树
1、满二叉树
定义：一棵高度为 h，且含有 个结点的二叉树称为满二叉树。文字不好理解看图！！！
其实就是每一层都含有最多的结点，除叶子结点外每个结点度都为2。
2、完全二叉树
高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1～n的结点一一对应时，称为完全二叉树。
对比
三、二叉树的遍历及代码
示例图：
