二叉树详解

曾经终败给现在 2022-11-14 11:52 55阅读 0赞

#### 一、相关概念 ####

##### 1、定义 #####

二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。

##### 2、度 #####

结点拥有的子树数目称为结点的度。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1MjAxNDY_size_16_color_FFFFFF_t_70]

##### 3、结点层次 #####

从根开始定义起，根为第一层，根的孩子为第二层，以此类推。  
![在这里插入图片描述][20210329101648125.png]

##### 4、树的深度 #####

树中结点的最大层次数称为树的深度或高度。上图中树的深度为3。

#### 二、二叉树特点 ####

*  每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
 *  左子树和右子树是有顺序的，次序不能任意颠倒。
 *  即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

#### 三、二叉树性质 ####

*  在二叉树的第i层上最多有2i-1 个节点 。（i>=1）
 *  二叉树中如果深度为k,那么最多有2k-1个节点。(k>=1）
 *  n0=n2+1 n0表示度数为0的节点数，n2表示度数为2的节点数。
 *  在完全二叉树中，具有n个节点的完全二叉树的深度为\[log2n\]+1，其中\[log2n\]是向下取整。
 *  若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点有如下特性：

(1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 \[i/2\] 的结点为其双亲结点;  
(2) 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；  
(3) 若 2i+1>n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。

#### 四、二叉树遍历 ####

二叉树的遍历主要有三种：  
（1）先(根)序遍历（根左右）  
（2）中(根)序遍历（左根右）  
（3）后(根)序遍历（左右根）

![在这里插入图片描述][2021032910201380.png]  
先(根)序遍历（根左右）：A B D H E I C F J K G  
中(根)序遍历（左根右） : D H B E I A J F K C G  
后(根)序遍历（左右根） : H D I E B J K F G C A

##### 五、关键码序列 #####

若任意节点的左子树不空，则左子树上所有结点的 值均小于它的根结点的值，若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值，任意节点的左、右子树也分别为二叉查找树，没有键值相等的节点。

以小根堆为例，堆的特点是双亲结点的关键字必然小于等于孩子结点的关键字，而两个孩子结点的关键字没有次序规定，而二叉排序数中，每个双亲结点的关键字均大于左子树结点的关键字，均小于右子树j结点的关键字，也就是说，每个双亲结点的左右孩子的关键字有次序关系，这样，当对两种树执行中序遍历后，二叉树会得到一个有序的序列，而堆不一定。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA1MjAxNDY_size_16_color_FFFFFF_t_70]: /images/20221022/9371243ba09145f9b448dd4ab840fe21.png
[20210329101648125.png]: /images/20221022/228be7f977d443b0ab872c2bc251d40d.png
[2021032910201380.png]: /images/20221022/c3ca588a3fb141e98b951885e911c952.png