Java数据结构——认识二叉树

柔情只为你懂 2023-10-10 15:06 5阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：敲代码の流川枫
> 
> 博客主页：[流川枫的博客][Link 1]
> 
> 专栏：[和我一起学java][java]
> 
> 语录：Stay hungry stay foolish
> 
> 工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
> 
> [点击注册和我一起刷题][Link 2]

**文章目录**

树的概念

树型结构

二叉树

二叉树的性质

满二叉树

完全二叉树

性质4公式推导

经典题目

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ） A 不存在这样的二叉树 B 200 C 198 D 199

2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ） A n B n+1 C n-1 D n/2

3.一个具有767个节点的完全二叉树，其叶子节点个数为（） A 383 B 384 C 385 D 386

4.一棵完全二叉树的节点数为531个，那么这棵树的高度为（ ） A 11 B 10 C 8 D 12 答案： 1.B 2.A 3.B 4.B

--------------------

## 树的概念 ##

![82331f1682814ad78bfa45b7d898795b.png][]

### 树型结构 ###

树是一种重要的**非线性数据结构**，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，像自然界中的树那样。**树是递归定义的**

树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一

一切具有层次关系的问题都可用树来描述。满二叉树，完全二叉树，排序二叉树

为了便于理解，树还有以下重要的概念或表示方法：

> **节点的度**：一个**节点**所含有的子树的个数就是这个节点的度
> 
> **树的度**：一棵树中所有**节点**的度的最大值称为该树的度
> 
> **叶子节点**：度为0的结点称为叶子节点
> 
> **父节点**：一个**节点**含有子节点，那么这个节点就是子节点的父节点
> 
> **根节点**：没有双亲的节点称为根节点
> 
> **节点的层次**：根节点为第一层，根节点的子节点为第二层，以此类推
> 
> **树的深度**：树中节点的最大层次

### 二叉树 ###

![95c8e70db6aa46acb810939e3d8f67bc.png][]

在计算机科学中，**二叉树是每个结点最多有两个子树的有序树**。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。

> 注意：
> 
> **二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)**
> 
> **二叉树的子树有左右之分，次序不能颠倒**

二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：

![4d0c1beda7cc4ee68daa2b0e74ebd413.png][]

## 二叉树的性质 ##

二叉树有许多重要的性质，理解并记忆有助于我们做题

> 性质1：根节点的层数为1，二叉树第i层上的节点数目最多为2^（i-1）(i>=0)
> 
> 性质2：根节点的二叉树的深度为1，深度为k的二叉树至多有（2^k）-1个节点（k>=0）
> 
> 性质3：包含n个节点的二叉树的高度至少为(log2n)+1
> 
> 性质4：在任意一棵二叉树中，若叶子节点的个数为n0，度为2的结点数为n2，则n0=n2+1
> 
> 性质5：一棵树有N个节点，则有N-1条边

###  **满二叉树** ###

高度为h，并且由（2^h）-1个节点组成的二叉树，称为满二叉树

![136c04fc44bf46939ac026373d78c926.png][]

### **完全二叉树** ###

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n 个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完 全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

![673fff63b3f5446e81bb689b61e88fa5.png][]

**特点**：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。

### 性质4公式推导 ###

> 假设任意一颗二叉树中有N个节点：
> 
> 记度为0的节点为n0，度为1的节点为n1，度为2的节点为n2
> 
> 则有：**N = n0+n1+n2**

> 由上图的二叉树我们可以看出，一个度为1 的节点能向下产生一条边，一个度为2的节点向下产生两条边，一个度为0的节点向下产生0条边，**一棵树有N个节点，则有N-1条边**
> 
> 那么度为1 的节点能产生n1条边，度为2的节点能产生2\*n2条边，度为0的节点产生0条边
> 
> 则有：**N-1 = n1+2\*n2**

> 另两式相等则有：
> 
> **n0+n1+n2 = n1+2\*n2+1**
> 
> 推出：**n0=n2+1**

## 经典题目 ##

> ### 1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ） A 不存在这样的二叉树 B 200 C 198 D 199 ###

> 由性质4得出，n0=n2+1，二叉树度为2的节点有199个，叶子节点个数为200个，选B

> ### 2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ） A n B n+1 C n-1 D n/2 ###

![dd545b572d2d4d30be0f1929d39d4630.png][]

> **性质4：在任意一棵二叉树中，若叶子节点的个数为n0，度为2的结点数为n2，则n0=n2+1**
> 
> 本题节点个数为2n，是偶数情况
> 
> 那么**2n = n0 + 1 + n2**
> 
> **又因为n0 = n2 +1**
> 
> **则有：2n - 1 = 2n0 - 1**
> 
> **n0 = n**
> 
> **选A**

> ### 3.一个具有767个节点的完全二叉树，其叶子节点个数为（） A 383 B 384 C 385 D 386 ###

> **性质4：在任意一棵二叉树中，若叶子节点的个数为n0，度为2的结点数为n2，则n0=n2+1**
> 
> 767节点总数为奇数，则n1为0
> 
> 则有：767 = n0 + n2
> 
> 由 **n0 = n2 + 1**
> 
> n0 = 768/2 = 384
> 
> 选B

> ### 4.一棵完全二叉树的节点数为531个，那么这棵树的高度为（ ） A 11 B 10 C 8 D 12 答案： 1.B 2.A 3.B 4.B ###

> **性质3：包含n个节点的二叉树的高度至少为(log2n)+1**
> 
> 2^9 = 512 < 53B
> 
> 节点数为531，要向上取整
> 
> **2^10 = 1024**
> 
> 选B

> “ 本期的分享就到这里了， 记得给博主一个三连哈，你的支持是我创作的最大动力！

![ced485cbb11e458d81a746890b32cf3f.gif][]

[ced485cbb11e458d81a746890b32cf3f.gif]: https://img-blog.csdnimg.cn/ced485cbb11e458d81a746890b32cf3f.gif
[Link 1]: https://blog.csdn.net/chenchenchencl?spm=1011.2421.3001.5343
[java]: https://blog.csdn.net/chenchenchencl/category_11932758.html
[Link 2]: https://www.nowcoder.com/link/pc_csdncpt_qdmdlcf_c
[82331f1682814ad78bfa45b7d898795b.png]: https://img-blog.csdnimg.cn/82331f1682814ad78bfa45b7d898795b.png
[95c8e70db6aa46acb810939e3d8f67bc.png]: https://img-blog.csdnimg.cn/95c8e70db6aa46acb810939e3d8f67bc.png
[4d0c1beda7cc4ee68daa2b0e74ebd413.png]: https://img-blog.csdnimg.cn/4d0c1beda7cc4ee68daa2b0e74ebd413.png
[136c04fc44bf46939ac026373d78c926.png]: https://img-blog.csdnimg.cn/136c04fc44bf46939ac026373d78c926.png
[673fff63b3f5446e81bb689b61e88fa5.png]: https://img-blog.csdnimg.cn/673fff63b3f5446e81bb689b61e88fa5.png
[dd545b572d2d4d30be0f1929d39d4630.png]: https://img-blog.csdnimg.cn/dd545b572d2d4d30be0f1929d39d4630.png