【数据结构】树、二叉树总结（一）

ゞ浴缸里的玫瑰 2021-09-21 06:54 399阅读 0赞

## 知识结构 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70_pic_center]

## 树的基本概念和定义 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70_pic_center 1]

## 树的性质（重要） ##

**1. 树中的节点树等于所有节点的度树加1**  
![在这里插入图片描述][20200426171357354.png]

*  总度数等于根节点的所有子节点，当n=3，则度为2
 *  总结点数等于度加1

**2. 度为m的树第i层最多有**  m i − 1 m^\{i-1\} mi−1 **个节点**  
把树每层看做等比数列, 每一层看作一项, 则第1到第i层分别为:  a 1 , a 2 … a i a\_1, a\_2 \\dots a\_i a1,a2…ai ;度即为等比梳理的公比q=m, 首项为 a 1 a\_1 a1=1(一棵树只有一个根节点);

∵ \\because ∵ 等比通项公式:  a n = a 1 ∗ q ( n − 1 ) a\_n = a\_1\*q^\{(n-1)\} an=a1∗q(n−1)

∴ \\therefore ∴ 由上式得  a i = 1 ∗ m ( i − 1 ) ⇒ a i = m ( i − 1 ) a\_i = 1 \* m^\{(i-1)\} \\Rightarrow a\_i=m^\{(i-1)\} ai=1∗m(i−1)⇒ai=m(i−1),

即第i层的节点数等于 m ( i − i ) m^\{(i-i)\} m(i−i)

**3. 高度为h的m叉树, 最多有**  m h − 1 m − 1 \\frac\{m^h-1\}\{m-1\} m−1mh−1 **个节点**  
仍把数的每层看作等比数列, 可得到:  a 1 = 1 , q = m , n = h a\_1 = 1 ,q=m , n=h a1=1,q=m,n=h

∵ S n = a 1 ∗ ( 1 − q n ) ( 1 − q )   ( q ≠ 1 ) \\because S\_n=\\frac\{a\_1\*(1-q^n)\}\{(1-q)\} \\ (q\\neq 1) ∵Sn=(1−q)a1∗(1−qn) (q=1)

∴ S i = 1 ∗ ( 1 − m h ) 1 − m = − ( m h − 1 ) − ( m − 1 ) ⇒ m h − 1 m − 1 \\therefore S\_i =\\frac\{1\*(1-m^h)\}\{1-m\} =\\frac\{-(m^h-1)\}\{-(m-1)\} \\Rightarrow \\frac\{m^h-1\}\{m-1\} ∴Si=1−m1∗(1−mh)=−(m−1)−(mh−1)⇒m−1mh−1

**4. 具有n个节点的m叉树, 最小高度为**  log ⁡ m ( n ( m − 1 ) + 1 ) \\log\_\{m\}(n(m-1)+1) logm(n(m−1)\+1) **向上取整.**

## 二叉树 ##

特点：

*  至多由两个子节点
 *  两个节点有左右之分
 *  节点可以为空  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70_pic_center 2]

### 满二叉树 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70]

*  除叶子节点外每个节点都有两个子节点
 *  只有最后一次有叶子节点，h-1全是父节点
 *  高度为h的满二叉树共有 2 h − 1 2^\{h\}-1 2h−1个节点
 *  第i层共有 2 h − 1 2^\{h-1\} 2h−1个节点
 *  满二叉树的节点为奇数个, 去掉根为偶数个

### 完全二叉树 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70 1]

*  有n(n>2)层的完全二叉树, 叶节点在n和n-1层
 *  按照层序编号, 当 i ≤ ⌊ n 2 ⌋ i\\leq\\lfloor\\frac\{n\}\{2\}\\rfloor i≤⌊2n⌋时, i为双亲(父)节点, 否则为叶子节点
 *  完全二叉树的节点树可能为奇树或偶数, 为奇数时最后一个双亲节点无左孩子; 为偶数时有左孩子.(可看上图加以理解)
 *   i ≤ n − 1 i\\leq n-1 i≤n−1时, 第i层共有 2 h − 1 2^\{h-1\} 2h−1个节点

### 二叉树性质(重要) ###

**1. 非空二叉树的叶子节点数等于度为2的节点数加1, 即**  n 0 = n 2 + 1 n\_0 = n\_2+1 n0=n2\+1  
**2. 非空二叉树第i层最多有** 2 i − 1 2^\{i-1\} 2i−1个节点,  ( i ≥ 1 ) (i\\geq1) (i≥1).  
**3. 高度为h的二叉树最多有** 2 h − 1 2^h-1 2h−1个节点(此时为满二叉树),  h ≥ 1 h\\geq1 h≥1.  
**4. 对二叉树进行层序编号**

*  当i>1, 双亲编号为 ⌊ i 2 ⌋ \\lfloor \\frac\{i\}\{2\} \\rfloor ⌊2i⌋, i为偶数无须向下取整
 *  当 2 i ≤ n 2i\\leq n 2i≤n, 节点左孩子编号为2i, 否则无左孩子.
 *  当 2 i + 1 ≤ n 2i+1\\leq n 2i\+1≤n, 节点右孩子编号为2i+1, 否则无右孩子
 *  节点i所在层次或深度为 ⌊ log ⁡ 2 i ⌋ + 1 \\lfloor \\log\_2i \\rfloor+1 ⌊log2i⌋\+1

**具有n个节点的完全二叉树的高度为** ⌊ log ⁡ 2 n ⌋ + 1 \\lfloor \\log\_2n \\rfloor+1 ⌊log2n⌋\+1 或者 ⌈ log ⁡ 2 ( n + 1 ) ⌉ \\lceil\\log\_2\{(n+1)\}\\rceil ⌈log2(n\+1)⌉

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

> **想了解作者更多，请移步我的个人网站，欢迎交流、留言~**  
> **极客技术空间：[https://elltor.com/][https_elltor.com]**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70_pic_center]: /images/20210920/f1180a71db7e40318a4759ba714800f8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20210920/612e9d887776436c97748067da50f49a.png
[20200426171357354.png]: /images/20210920/ec8d5590473f47c5b356bad1e3fe5a9f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20210920/291431e42c7e4db59df3507d9bad5e25.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70]: /images/20210920/dbe2e7794560492faf11f56e5aae3ed9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70 1]: /images/20210920/e2c29d76244e45cba2f79f5d0d8d83e3.png
[https_elltor.com]: https://elltor.com/