二叉树的基本概念

本是古典何须时尚 2022-10-02 01:55 207阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

**二叉树的定义**

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。

**二叉树的5种基本形态，任意一棵二叉树都由这5种形态组合而成**

空二叉树，单节点二叉树，右子树为空的二叉树，左子树为空的二叉树，左右子树都有的二叉树

**性质1**

非空二叉树的第i层，最多有（2的（i-1）次方）个节点

**性质2**

高度为h的二叉树，最多有（2的h次方-1）个节点

**性质3**

对于任意一棵二叉树，如果它的叶子节点数为N0，度为2的节点数为N2，那么N0=N2+1

**性质4**

具有n个结点的完全二叉树的高度为log2(n+1)或log2(n)+1。

**性质5**

如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给节点编号为1,2,3,···,n，然后按此结点编号将树中各结点顺序地存放于一个一位数组中，并简称编号为i的结点为结点i(1≤i≤n)。则有以下关系：

若i≤n/2，即2i≤n，则编号为i的结点为分支结点，否则为叶子结点。

若n为奇数，则每个分支结点都既有左孩子结点，也有右孩子结点；若n为偶数，则编号最大的分支结点（编号为n/2）只有左孩子节点，没有右孩子结点，其余分支结点都有左右孩子结点

若编号为i的结点有左孩子结点，则左孩子结点的编号为2i，若编号为i的结点有右孩子结点，则右孩子结点的编号为(2i+1)。

除根结点外，若一个结点的编号为i，则它的双亲结点的编号为⌊i/2⌋，也就是说，当i为偶数时，其双亲结点的编号为i/2，它是双亲结点的左孩子结点，当i为奇数时，其双亲结点的编号为(i-1)/2，它是双亲结点的右孩子结点。

**满二叉树**

结合性质2，高度为h的二叉树，如果它的节点个数达到最大，即为满二叉树

**完全二叉树**

如果一棵具有n个结点的高度为k的二叉树，它的每一个结点都与高度为k的满二叉树中编号为1~n的结点一一对应，则称这棵树为完全二叉树。

换一种说法

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

理解一下完全二叉树的概念，下图是一个满二叉树

![114339_Mr9N_2836128.jpg][]

然后是一个完全二叉树

![114439_AdzT_2836128.jpg][]

转载于:https://my.oschina.net/dongtianxi/blog/796035

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220113/9f6069d8362444fa89c78d3573e79d4e.png
[114339_Mr9N_2836128.jpg]: https://static.oschina.net/uploads/space/2016/1129/114339_Mr9N_2836128.jpg
[114439_AdzT_2836128.jpg]: https://static.oschina.net/uploads/space/2016/1129/114439_AdzT_2836128.jpg

发表评论取消回复

表情：

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

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

相关阅读

相关【数据结构】二叉树的基本概念

![在这里插入图片描述][f601c179eaf04219afa7d83b5cd94a0b.png] 文章目录一、树 1、什么是树 2

╰半夏微凉°/ 2024年03月04日 02:50/ 0 赞/ 109 阅读

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

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

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

相关二叉树的概念

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

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

相关 Data Structure--树基本概念引入(二叉树)

树的表示基本概念关键字二叉树二叉树存储 1.顺序存储 2.链式存储基本概念

向右看齐/ 2022年10月31日 01:57/ 0 赞/ 220 阅读

相关二叉树的基本概念

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

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

相关关于二叉树二叉堆的一些基本概念

文章转载自：[http://blog.csdn.net/include\_u/article/details/48092129][http_blog.csdn.net_incl

古城微笑少年丶/ 2022年06月07日 09:25/ 0 赞/ 435 阅读

相关二叉树、平衡二叉树、B- tree、B+ tree 基本概念

1 二叉树二叉树binary tree是指每个节点最多含有两个子树的树结构。特点： 1.所有节点最多拥有两个子节点，即度不大于2

雨点打透心脏的1/2处/ 2022年05月20日 06:59/ 0 赞/ 277 阅读

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

首先，什么是二叉树？二叉树（Binary Tree）是n （n>=0）个节点的有限集合，该集合可以为空集（称为空二叉树），或者由一个根节点和两个互不相交的，分别称为根节点

太过爱你忘了你带给我的痛/ 2022年01月31日 22:43/ 0 赞/ 512 阅读

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

二叉树简单说就是有两个子树的树 1.种类及概念: 　　二叉树是每个结点最多有两个子树的树结构。　　完全二叉树：除最后一层外，若其余层都是满的，并且最后一层或者是满的，或

悠悠/ 2021年12月01日 22:46/ 0 赞/ 425 阅读

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

一树示意图 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubm

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