二叉树的概念

待我称王封你为后i 2022-12-09 00:37 289阅读 0赞

## 一 概述 ##

二叉树为多种树形结构中的一种，其特点为每个结点至多只有两棵子树，即二叉树中不存在度大于2的结点，并且二叉树的子树有左右之分，其次序不能任意颠倒。

**二叉树同样是通过递归的形式进行定义。二叉树是n(n>=0)个结点的有限集合：**

1.  当n=0的时候，该树为空二叉树。
2.  当n>0的时候，二叉树由一个根结点和互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别为一棵二叉树。

二叉树是有序树，若将其左，右子树颠倒，则成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。

![20200921094403892.png][]

**二叉树与度为2的有序树的区别：**

1.  度为2的树至少右3个结点，而二叉树可以为空。
2.  度为2的有序树的孩子的左右次序是相对与另一个孩子而言的，若某个结点只有一个孩子，则这个孩子就无须区分其左右次序，而二叉树无论其左右孩子是否同时存在，均需确定其左右次序，即二叉树的结点次序不是相对另一个结点而言，而是确定的。

## 二 几种特殊的二叉树 ##

![20200921095838671.png][]

**满二叉树：**一棵高度为h，且含有2^h - 1个结点的二叉树为满二叉树，即树中的每层都含有最多的结点。而且满二叉树的叶子结点都集中在二叉树的最下一层，并且除叶子结点之外的每个结点度数均为2。

**完全二叉树：**高度为h，有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中的编号1~n的结点一一对应时，称为完全二叉树。完全二叉树的特点如下：

1.  若i<=n/2(取下界)，则结点i为分支结点，否则为叶子节点。
2.  叶子结点只可能在层次最大的两层上出现。对于最大的层次中的叶子结点，都依次排列在该层最左边的位置上。
3.  若有度为1的结点，则只可能有一个，且该结点只有左孩子而无右孩子（重要特征）。
4.  按层序编号后，一旦出现某结点（编号为i）为叶子结点或只有左孩子，则编号大于i的结点均为叶子结点。
5.  若n为奇数，则每个分支结点都有左孩子和右孩子；若n为偶数，则编号最大的分支结点（编号为n/2）只有左孩子，没有右孩子，其余分支结点左，右孩子都存在。

**二叉排序树：**左子树上所有结点的关键字均小于根结点的关键字；右子树上的所有结点关键字均大于根结点的关键字；左子树和右子树各是一棵二叉排序树。

**平衡二叉树：**树上任一结点的左子树和右子树的深度之差不超过1。

[20200921094403892.png]: /images/20221123/7d1afe123c7e4cdc9625a1674dd26f8b.png
[20200921095838671.png]: /images/20221123/850bb8fe3daf4631a3364724ddd3225c.png

发表评论取消回复

表情：

评论列表（有 0 条评论，289人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构】树以及二叉树的概念

> 作者：一个喜欢猫咪的的程序员 > > 专栏：《数据结构》 > > 喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》 > > ![c1dbb8e133d

布满荆棘的人生/ 2024年03月30日 09:29/ 0 赞/ 56 阅读

相关树和二叉树的概念以及结构

目录一、树概念及结构 1.1 树的概念 1.2 树的相关概念 1.3 树的表示 1.4 树在实际中的应用二、二叉树概念及结构 2.1 概念 2.2 特殊的二

不念不忘少年蓝@/ 2023年10月13日 12:53/ 0 赞/ 42 阅读

相关二叉树的概念及特性

目录一、树的引出二、树的特性三、二叉树的概念四、二叉树的性质 -------------------- 一、树的引出树是一种非线性的数据结构，它

╰+哭是因爲堅強的太久メ/ 2023年09月27日 14:04/ 0 赞/ 101 阅读

相关二叉树的概念与性质

`本文主要为观看哔哩哔哩视频网站上的王道考研的数据结构的学习笔记，如有侵权，请联系我删除` 二叉树的定义 ![在这里插入图片描述][watermark_type_ZmF

╰半夏微凉°/ 2023年01月07日 13:28/ 0 赞/ 182 阅读

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

树、二叉树、完全二叉树的区别与基本概念一、树树：不包含回路的连通无向图（树是一种简单的非线性结构）。 ![watermark_type_ZmFuZ3poZW5

我会带着你远行/ 2023年01月02日 12:22/ 0 赞/ 201 阅读

相关二叉树的概念

一概述二叉树为多种树形结构中的一种，其特点为每个结点至多只有两棵子树，即二叉树中不存在度大于2的结点，并且二叉树的子树有左右之分，其次序不能任意颠倒。二叉树同样是

待我称王封你为后i/ 2022年12月09日 00:37/ 0 赞/ 290 阅读

相关二叉树的概念、存储、实现

树是有n个节点的有限集合，并且有且只有一个根节点（其实小编觉得这个和病毒的传播有一定的相似之处，想象一下一种病毒只能传播有限个个体，如下图所示） ![在这里插入图片描

比眉伴天荒/ 2022年12月06日 15:13/ 0 赞/ 133 阅读

相关二叉树的基本概念

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] 二叉树的定义一棵二叉树是结点的一个有限集合，该集合或

本是古典何须时尚/ 2022年10月02日 01:55/ 0 赞/ 209 阅读

相关二叉树、二叉搜索树、平衡二叉树、红黑树、B树、B+树概念的简单区分

文章目录 1、二叉树（Binary Tree） 2、二叉搜索树（Binary Search Tree） 3、平衡二叉树（AVL T

一时失言乱红尘/ 2021年10月19日 09:38/ 0 赞/ 406 阅读

相关树和二叉树的基本概念

一树示意图 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubm

ゝ一纸荒年。/ 2021年07月25日 02:49/ 0 赞/ 440 阅读