二叉树的基本概念(上)

---

你的点赞评论就是对博主最大的鼓励
当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~

---

🍊自我介绍

  Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入式方面的内容。

---

🍊简介

  世界上的树有千万种，我们这里来学习我们数据结构中的树，它是我们现实生活中倒置的树。之前，我们学习的顺序表，链表，栈、和队列。可以说都是我们的线性结构，也就是我们所谓的一对一的结构，可是现实生活中，我们经常碰到是我们一对多的情况。今天，我们就来研究一下这种一对多的数据结构体----“树”。那么，什么叫做树呢?

🍊树的定义

概述
（1）树由结点和边组成
（2）树中除根节点外，每一个结点都有一个父节点，但是可以有多个子节点。
（3）根节点没有父节点

树中的专业术语

节点：父节点，子节点
度：结点拥有子树的个数
叶子节点：没有子节点的节点
边：一个节点到另一个节点的距离
树的深度：节点的层数，根节点默认为第一层。
有序：树的左右位置不能改变。

树的分类

一般树：任意一个结点的子节点的个数不受限制，则称为一般树。（子节点可以有多个），如下图：

二叉树（重点）：任意一个节点的子节点的个数最多有两个，且子节点的个数不能更改。

森林：去掉根节点就称之为森林。

🍊二叉树的特性讲解

如下图是一颗二叉树，它有一些特性：

第一层最多有1个节点
第二层最多有2个节点
第三层最多有4个节点
第四层最多有8个节点
…
第n层最多有$2^{n-1}$个节点

性质1：二叉树的第n层上的结点最多有$2^{n-1}$个节点。

前1层最多一共有1个节点
前2层最多一共有3个节点
前3层最多一共有7个节点
前4层最多一共有15个节点
…
前n层最多一共有$2^n$-1个节点

性质2：深度为n的二叉树最多有$2^n$-1个节点。

性质3：在任意一颗二叉树中，树叶的数目比度数为2的结点的数目多1。
（推导过程）