C树和森林的研究学习随记【一】

喜欢ヅ旅行 2024-03-31 10:39 43阅读 0赞

#### 文章目录 ####

*  树与森林
 *  树结构初识
 *   *  树基本的相关概念
     *  森林
     *  二叉树(Binary Tree)
     *   *  满二叉树【饱满】
         *  完全二叉树【少了叶子的满二叉树】
         *  总结
         *  树和森林的转换
         *  快速转换技巧
         *  森林转化为二叉树
         *  分辨
         *  二叉树的五大性质

## 树与森林 ##

*  树是一种的数据结构。顾名思义，类似于我们生活中的树一样。【具体一点就是一对多的数据结构】

## 树结构初识 ##

![在这里插入图片描述][6da2116597394ec08d5e226fc4ba6ccd.png]

*  从最上面的根节点的节点开始像下面进行延申，更多的节点，这种结构就称为***树（Tree）***。
 *  ***注意分支只能向后单向延申，不能与其他分支上的结点相交。***

### 树基本的相关概念 ###

<table> 
 <thead> 
  <tr> 
   <th>术语</th> 
   <th>解释</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>根节点</td> 
   <td>位于最上面的结点。</td> 
  </tr> 
  <tr> 
   <td>度</td> 
   <td>每个节点连接的子节点数目（分支的数目）。</td> 
  </tr> 
  <tr> 
   <td>树的度</td> 
   <td>一棵树中各个结点度的最大值。</td> 
  </tr> 
  <tr> 
   <td>子树</td> 
   <td>每个节点延伸下去的下一个节点都可以称为一棵子树。</td> 
  </tr> 
  <tr> 
   <td>结点的层次(Level)</td> 
   <td>按照从上往下的顺序，树的根节点的层次为1，每向下一层+1</td> 
  </tr> 
  <tr> 
   <td>树的层次(Depth)</td> 
   <td>整棵树中所有结点的最大层次。</td> 
  </tr> 
  <tr> 
   <td>子节点(Child)</td> 
   <td>与当前结点直接向下相连的结点</td> 
  </tr> 
  <tr> 
   <td>父节点(Parent)</td> 
   <td>与当前结点直接向上连接的结点</td> 
  </tr> 
  <tr> 
   <td>兄弟结点(Sibling)</td> 
   <td>两个结点的父节点相同</td> 
  </tr> 
  <tr> 
   <td>祖宗结点(Ancestor)</td> 
   <td>从根节点开始一直到某个结点的整条路径的所有结点，都是当前结点的祖宗节点</td> 
  </tr> 
  <tr> 
   <td>叶子结点</td> 
   <td>度为0的结点【一般位于分支的最末端】</td> 
  </tr> 
  <tr> 
   <td>分支结点</td> 
   <td>度为1或2的非根节点</td> 
  </tr> 
 </tbody> 
</table>

### 森林 ###

*  一片森林是由很多课树构成。  
    ![在这里插入图片描述][218d104f69b74991a5d884fa4f2ec8e2.png]
 *  各个树之间互不连接。

### 二叉树(Binary Tree) ###

*  二叉树是一种特殊的树，它的度最大只能为2。  
    ![在这里插入图片描述][336cf4cda539484b90e1fb8429b14ca5.png]
 *  \*\*\*二叉树的结点的子树是有左右之分的，不能颠倒顺序。\*\*\****A左边的子树为左子树，A右边的树为右子树。***
 *  二叉树的五种基本形态  
    ![在这里插入图片描述][a475cf444926444da6d7949ce5db3002.png]

#### 满二叉树【饱满】 ####

*  满二叉树：***所有的分支结点都存在左子树和右子树，且叶子结点都在同一层。***
 *  整棵树都是很饱满的，没有度为1的结点。  
    ![在这里插入图片描述][d72fda05b28a4e729b8323d3ac5ac3bc.png]

#### 完全二叉树【少了叶子的满二叉树】 ####

*  只有最后一层有空缺，并且所有的叶子节点是按照从左到右的顺序排列的。  
    ![在这里插入图片描述][db895367dace4366a3e405103b817059.png]

#### 总结 ####

*  ***一颗满二叉树一定是一个课完全二叉树。完全二叉树一定不是满二叉树***【但完全二叉树是一颗少了叶子的满二叉树】。

#### 树和森林的转换 ####

*  普通树转换为二叉树的转换规则
    
     *  孩子结点->左子树结点(左孩子)
     *  兄弟节点->右子树结点(右兄弟)
 *  规律：***一颗普通树转化为二叉树后2，跟结点一定没有左子树。***
 *  普通树  
    ![在这里插入图片描述][d88513e58071470ba4a922ec894cdf64.png]
 *  转换后的二叉树  
    ![在这里插入图片描述][cae4d892b5fd4ce28ef56c9b16272c15.png]

#### 快速转换技巧 ####

*  第一步：直接将从最左端开始将所有的兄弟节点连接起来。  
    ![在这里插入图片描述][e8604d67f73446e3a6d72023f1b32e35.png]
 *  第二步：然后擦除所有结点除了最左边结点以外的连线。  
    ![在这里插入图片描述][68c702b64f594862bfb3ca39e7cd1bb4.png]
 *  第三步：所有的黑色连线偏向左，橙色连线偏向右  
    ![在这里插入图片描述][48b4f97f2b384714b566b8f02b728ec5.png]

#### 森林转化为二叉树 ####

*  第一步：先将森林中的所有普通树转化为二叉树。
 *  第二步：然后依次相连【右兄弟】
 *  森林  
    ![在这里插入图片描述][72c6377b741d4741b7155b4bb7f1787d.png]
 *  转化后的二叉树  
    ![在这里插入图片描述][76c633cdbc8a4b93bda3017b68b17753.png]
 *  连接每棵树时，都是从根节点的右边开始，不断向右连接。

#### 分辨 ####

*  如果二叉树的根节点有右兄弟结点，则它是由森林转换而来。否则，它是由一棵树转换而来。

#### 二叉树的五大性质 ####

*  性质一：对于一颗二叉树，第i层的最大结点数量为  
     2 i − 1 2^\{i-1\} 2i−1
 *  性质二：对于一颗深度为k的二叉树，可以具有的最大结点数量为:  
     n = 2 0 + 2 1 + 2 2 + . . . + 2 k − 1 n=2^0+2^1+2^2+...+2^\{k-1\} n=20\+21\+22\+...\+2k−1  
    简化计算  
     S n = a 1 × ( 1 − q n ) 1 − q = 1 × ( 1 − 2 k ) 1 − 2 = − ( 1 − 2 k ) = 2 k − 1 S\_n=\\frac\{a\_1\\times(1-q^n)\}\{1-q\}=\\frac\{1\\times(1-2^k)\}\{1-2\}=-(1-2^k)=2^k-1 Sn=1−qa1×(1−qn)=1−21×(1−2k)=−(1−2k)=2k−1
    
     *  结论：
        
         *  一颗深度为k的二叉树最大结点数量为 2 k − 1 2^k-1 2k−1,结点的边数为 E = n − 1 E=n-1 E=n−1
 *  性质三：【记忆】  
     n 0 = n 2 + 1 n\_0=n\_2+1 n0=n2\+1
    
     *  假设一颗二叉树中度为0、1、2的结点数量为 n 0 、 n 1 、 n 2 n\_0、n\_1、n\_2 n0、n1、n2，由于一棵树二叉树中只有这三种类型的结点，可得结点总数：  
         n = n 0 + n 1 + n 2 n=n\_0+n\_1+n\_2 n=n0\+n1\+n2
     *  从二叉树的边数考虑，因为每个结点有且仪有一条边与具交结点相连，那么边数之和就可以表示为  
         E = n 1 + 2 n 2 E=n\_1+2n\_2 E=n1\+2n2
     *  度为1的结点有一条边，度为2的结点有两条边，度为0的结点没有，加在一起就是整棵二叉树的边数之和,可得  
         E = n − 1 = n 1 + 2 n 2 n = n 1 + 2 n 2 + 1 E=n-1=n\_1+2n\_2 n=n\_1+2n\_2+1 E=n−1=n1\+2n2n=n1\+2n2\+1
     *  再结合第一个公式  
         n 0 = n 2 + 1 n\_0=n\_2+1 n0=n2\+1
 *  性质四：【记忆】
    
     *  完全二叉树除了最后一层有空缺外，其他层数都是饱满的，假设这模二叉树为满二叉树，那么根据我们前面得到的性质，假设层数为 k k k，那么结点数量为： n = 2 k − 1 n=2^k-1 n=2k−1，根据完全二叉树的性质，最后一层可以满可以不满，那么一棵完全二叉树结点数 n n n满足：  
         2 k − 1 − 1 < n < = 2 k − 1 2^\{k-1\}-1<n<=2^k-1 2k−1−1<n<=2k−1
     *  因为n肯定是一个整数，那么可以写为  
         2 k − 1 < = n < = 2 k − 1 2^\{k-1\}<=n<=2^k-1 2k−1<=n<=2k−1
     *  现在我们只看左边的不等式，我们对不等式两边同时取对数，得到  
         k − 1 < = l o g 2 n k-1<=log\_2n k−1<=log2n
     *  综上所述，***一棵具有n个结点的完全二叉树深度为***  
         k = ⌊ l o g 2 n ⌋ + 1 k=\\lfloor log\_2n \\rfloor+1 k=⌊log2n⌋\+1
 *  性质五：
    
     *  一颗有n个结点的完全二叉树，由性质四得到深度为k=log2+1现在对于任意一个结点i，结点的顺序为从上往  
        下，从左往右：
     *  对于一个拥有左右孩子的结点来说，其左孩子为 2 i 2i 2i，右孩子为 2 i + 1 2i+1 2i\+1。
     *  如果 i = 1 i=1 i=1，那么此节点为二叉树的根节点，如果 i > 1 i>1 i>1，那么其父节点为 ⌊ i / 2 ⌋ \\lfloor i/2 \\rfloor ⌊i/2⌋
     *  如果 2 i > n 2i>n 2i>n，则结点 i i i没有左孩子
     *  如果 2 i + 1 > n 2i+1>n 2i\+1>n，则结点i没有右孩子

[6da2116597394ec08d5e226fc4ba6ccd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/ba452d3239754a8a9707119397f26dc6.png
[218d104f69b74991a5d884fa4f2ec8e2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/4549004fb91442e3a51b90381ea44078.png
[336cf4cda539484b90e1fb8429b14ca5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/aae75474d471488cb5dcf0ee9832990e.png
[a475cf444926444da6d7949ce5db3002.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/5bf183d5c2b846dd993bdaf5082bc3ac.png
[d72fda05b28a4e729b8323d3ac5ac3bc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/a154bdfb0cac46e9a9c94de968521c1d.png
[db895367dace4366a3e405103b817059.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/471d0bea0072474ea9fe59972a10fd47.png
[d88513e58071470ba4a922ec894cdf64.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/25ad3189540f4617a93feb20618ca1ae.png
[cae4d892b5fd4ce28ef56c9b16272c15.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/c8f675bd4d0b4b97b36db8e0cc56b42c.png
[e8604d67f73446e3a6d72023f1b32e35.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/26c508828de14b528868909e7fb80100.png
[68c702b64f594862bfb3ca39e7cd1bb4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/ed60f6c8a581456c8313520fe5b99706.png
[48b4f97f2b384714b566b8f02b728ec5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/aa17552ba7824a259da554a4c82e1c4b.png
[72c6377b741d4741b7155b4bb7f1787d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/c290c4abfb7142d283e5437f6e287012.png
[76c633cdbc8a4b93bda3017b68b17753.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/c05a9f6ec0264851be42226c9dbbfc5c.png