（数据结构）树和二叉树相关知识点

偏执的太偏执、 2023-02-18 01:43 8阅读 0赞

**1.树的概念及结构**  
**1.1 树的概念**  
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70]  
树的相关定义：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 1]  
如上图所示  
**节点的度：** 一个节点含有的子树的个数称为该节点的度； 如上图：A的为6  
**叶节点或终端节点：** 度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点  
**非终端节点或分支节点：** 度不为0的节点； 如上图：D、E、F、G…等节点为分支节点  
**双亲节点或父节点：** 若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点  
**孩子节点或子节点：** 一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点  
**兄弟节点：** 具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点  
**树的度：** 一棵树中，最大的节点的度称为树的度； 如上图：树的度为6  
**节点的层次：** 从根开始定义起，根为第1层，根的子节点为第2层，以此类推  
**树的高度或深度：** 树中节点的最大层次； 如上图：树的高度为4  
**堂兄弟节点：** 双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点  
**节点的祖先：** 从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先  
**子孙：** 以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙  
**森林：** 由m（m>0）棵互不相交的树的集合称为森林

**1.2 树的表示**  
实际中树有很多种表示方式，如：双亲表示法，孩子表示法、孩子兄弟表示法等等。最常用的是孩子兄弟表示法。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 2]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 3]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 4]  
孩子兄弟表示法：

typedef int DataType; 
    struct Node 
    {
           
        struct Node* _firstChild1;    // 第一个孩子结点    
        struct Node* _pNextBrother;   // 指向其下一个兄弟结点
        DataType _data;               // 结点中的数据域
     };

**1.3 树在实际中的应用（表示文件系统的目录树结构）**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 5]

**2 二叉树概念及结构**  
**2.1 概念**  
一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树 的二叉树组成。  
**2.2 特点**

1.  每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
2.  二叉树的子树有左右之分，其子树的次序不能颠倒。  
    **2.3 数据结构中的二叉树**  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 6]  
    **2.4 特殊的二叉树**  
    1.满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。  
    2 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 7]

**2.5 二叉树的性质**  
1 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点。  
2 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1.  
3 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0＝n2＋1  
4 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=Log2(n+1). (ps：Log2(n+1)是log以2为底，n+1为对数，h若为小数，向上取整)  
5 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：  
若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点 ；  
若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子 ；  
若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子。  
**2.6 二叉树的存储结构**  
二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。  
**2.6.1 顺序存储**  
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用只有堆才会使用数组来存储（堆在下一篇文章中讲到）。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 8]

**2.6.2 链式存储**  
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。  
![在这里插入图片描述][20200615093528228.png]

// 二叉链 
    struct BinaryTreeNode 
    {
            
        struct BinTreeNode* _pLeft;   // 指向当前节点左孩子    
        struct BinTreeNode* _pRight; // 指向当前节点右孩子    
        BTDataType _data; // 当前节点值域 
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200615084458611.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200615084654702.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200615085759924.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200615085828338.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200615085856987.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200615090333511.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200615091050612.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200615091330919.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200615093243468.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp,size_16,color_FFFFFF,t_70
[20200615093528228.png]: https://img-blog.csdnimg.cn/20200615093528228.png