树、二叉树、完全二叉树的区别与基本概念

我会带着你远行 2023-01-02 12:22 196阅读 0赞

# 树、二叉树、完全二叉树的区别与基本概念 #

# **一、树** #

**树：不包含回路的连通无向图（树是一种简单的非线性结构）。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NzE1MDAw_size_16_color_FFFFFF_t_70][] ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NzE1MDAw_size_16_color_FFFFFF_t_70 1][]

树有着**不包含回路的特点**，所以树就被赋予了很多特性：

1、一棵树中任意两个结点有且仅有唯一的一条路径连通。

2、一棵树如果有n个结点，那它一定恰好有n-1条边。

3、在一棵树中加一条边将会构成一个回路。

4、树中有且仅有一个没有前驱的结点称为**根结点。**

在对树进行讨论的时候将树中的每个点称为结点，

**根结点：**没有父结点的结点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NzE1MDAw_size_16_color_FFFFFF_t_70 2][]

**叶结点：**没有子结点的结点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NzE1MDAw_size_16_color_FFFFFF_t_70 3][]

**内部结点：**一个结点既不是根结点也不是叶结点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NzE1MDAw_size_16_color_FFFFFF_t_70 4][]

每个结点还有深度，比如上图左边的树的4号结点深度是3（深度是指从根结点到这个结点的层数，根结点为第一层）。

# 二、二叉树 #

### 1、基本概念： ###

**二叉树是一种非线性结构，二叉树是递归定义的**，其结点有左右子树之分。

### 2、二叉树的存储结构： ###

**二叉树通常采用链式存储结构，存储结点由数据域和指针域**（指针域：左指针域和右指针域）组成，二叉树的链式存储结构也称为二叉链表，对满二叉树和完全二叉树可按层次进行顺序存储。

特点：

1、每个结点最多有两颗子树。

2、左子树和右子树是有顺序的，次序不能颠倒。

3、即使某结点只有一个子树，也要区分左右子树。

4、二叉树可为空，空的二叉树没有结点，非空二叉树有且仅有一个根节点。

**二叉树中有两种特殊的二叉树：满二叉树、完全二叉树。**

（满二叉树的严格的定义是：一颗深度为h且有2h-1个结点的二叉树）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NzE1MDAw_size_16_color_FFFFFF_t_70 5][]

**完全二叉树：**除最后一层外，每一层上的节点数均达到最大值，在最后一层上只缺少右边的若干结点完全二叉树的形状类似于下图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NzE1MDAw_size_16_color_FFFFFF_t_70 6][]

为了方便理解请看下图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NzE1MDAw_size_16_color_FFFFFF_t_70 7][]

### 二叉树相关词语解释： ###

**结点的度**：结点拥有的子树的数目

**叶子结点：**度为0的结点**（tips：在任意一个二叉树中，度为0的叶子结点总是比度为2的结点多一个）**

**分支结点：**度不为0的结点

**树的度：**树中结点的最大的度

**层次：**根结点的层次为1，其余结点的层次等于该结点的双亲结点的层次加1

**树的高度：**树中结点的最大层次

### 二叉树基本性质： ###

性质1：在二叉树的第k层上至多有2k-1个结点（k>=1）

性质2：在深度为m的二叉树至多有2m-1个结点

性质3：对任意一颗二叉树，度为0的结点（即叶子结点）总是比度为2的结点多一个

性质4：具有n个结点的完全二叉树的深度至少为\[log2n\]+1，其中\[log2n\]表示log2n的整数部分

[参考转载链接][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NzE1MDAw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210105204906247.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NzE1MDAw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NzE1MDAw_size_16_color_FFFFFF_t_70 1]: /images/20221119/f1f3da4d056248ae8fece0f710dc8c96.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NzE1MDAw_size_16_color_FFFFFF_t_70 2]: /images/20221119/38cb10072709490680b608882752742b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NzE1MDAw_size_16_color_FFFFFF_t_70 3]: /images/20221119/db8062290ca04f69b8795e662dd581e5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NzE1MDAw_size_16_color_FFFFFF_t_70 4]: /images/20221119/018c05089bf4433ba40c8ea955514e17.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NzE1MDAw_size_16_color_FFFFFF_t_70 5]: /images/20221119/1469bc8ed16d423cb879d5d556c48bc0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NzE1MDAw_size_16_color_FFFFFF_t_70 6]: /images/20221119/759a0e7ba68b485eb04f00c5f537f79b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NzE1MDAw_size_16_color_FFFFFF_t_70 7]: /images/20221119/6dfecdfa3a964a8aaad52bb771e34427.png
[Link 1]: https://www.cnblogs.com/lanhaicode/p/10358736.html