数据结构-二叉树及其遍历

 🚀欢迎来到我的【数据结构】专栏🚀

• 🙋我是小蜗，一名在职牛马。
• 🐒我的博客主页​​​​​​ ➡️ ➡️ 小蜗向前冲的主页
• 🙏🙏欢迎大家的关注，你们的关注是我创作的最大动力🙏🙏

🌍前言

本篇文章咱们聊聊数据结构中的树，准确的说因该是只说一说二叉树以及相关的三种递归遍历、三种非递归遍历以及层次遍历。

🌍目录

一、二叉树的定义

二、特殊的二叉树

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的结点一一对应时，称为完全二叉树。

对比

三、二叉树的遍历及代码

示例图：