算法：什么是树以及树相关概念

蔚落 2022-12-16 15:23 149阅读 0赞

# 树的定义 #

*  树是用来处理一对多的数据结构
 *  树是n(n>=0)个节点的有限集
    
     *  n = 0， 叫做空树
     *  n > 0：
        
         *  根节点是唯一的
         *  子树的个数没有限制，但是一定是不相交的  
            ![在这里插入图片描述][2020102021453424.png_pic_center]

## 树的度 ##

*  节点拥有的子树数量称为节点的度 。 根据各个节点的度的不同，节点可以分为：
    
     *  叶子节点(Leaf) \[也叫做终端节点\]： 度为0的节点
     *  分支节点\[也叫做非终端节点\]： 度不为0
        
         *  内部节点： 除了根节点之外，分支节点也叫做内部节点
 *  树的度是树内各节点的度的最大值  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]

## 节点间关系 ##

*  当前节点的**子树的根**称为该节点的孩子（子节点）
 *  当前节点称为其子节点的双亲 【因为当前节点只有一个，所以叫做双亲节点，而不是父/母节点】
 *  同一个双亲的孩子之间互称为兄弟
 *  节点的祖先是从根节点到当前节点所经分支上的所有节点。 比如下图， 相对于H节点，D，B，A都是它的祖先
 *  以某节点为根的子树中任一节点都称为该节点的子孙。比如B的子孙有D，G，H，I  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 1]

## 树的层 ##

*  节点的层(level)： 从根节点开始，**根节点为第一层，跟的孩子为第二层。。。** 若某节点为第i层，则其子树的跟就在第i+1层
 *  **其双亲在同一层的节点互为堂兄弟**。 比如下图中的，D，E，F是堂兄弟，G，H，I，J是堂兄弟
 *  树中节点的最大层次称为树的深度。比如下图中树的深度为4  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 2]

## 树的有序性 ##

如果树中结点的各子树从左向右是有序的，子树间不能互换位置，则称该树为有序树，否则为无序树。

## 树的表示方法 ##

### 双亲表示法 ###

> 取一块连续的内存空间，在层次每个节点的同时，各自都附加一个记录其父节点位置的变量
> 
>  *  在树结构中，除了树根外，每个结点都只有一个父结点（又叫“双亲结点”）。

#define tree_size 100//宏定义树中结点的最大数量
    #define TElemType int//宏定义树结构中数据类型
    typedef struct PTNode{
         //节点结构
        TElemType data;//节点数据
        int parent;//双亲位置下标
    }PTNode;
    typedef struct {
          // 树结构
        PTNode nodes[tree_size];//节点数组
        int r,n;//根的位置下标和结点数
    }PTree;

例如，使用双亲表示法存储图 1（A）中的树结构时，数组存储结果为（B）：

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

当算法中需要在树结构中频繁地查找某结点的父结点时，使用双亲表示法最合适。当频繁地访问结点的孩子结点时，双亲表示法就很麻烦，采用孩子表示法就很简单

## 孩子表示法 ##

> 孩子表示法： 把每个节点的孩子节点排列起来，以单链表作存储结构，则n个节点有n个孩子链表，如果是叶子节点则单链表为空。然后n个头指针有组成一个线性表，采用顺序存储结构，存放进一个一维数组中

#define TElemType int
    #define Tree_Size 100
    //孩子表示法
    typedef struct CTNode{
        
        int child;//链表中每个结点存储的不是数据本身，而是数据在数组中存储的位置下标
        struct CTNode * next;
    }*ChildPtr;
    typedef struct {
        
        TElemType data;//结点的数据类型
        ChildPtr firstchild;//孩子链表的头指针
    }CTBox;
    typedef struct{
        
        CTBox nodes[Tree_Size];//存储结点的数组
        int n,r;//结点数量和树根的位置
    }CTree;

使用孩子表示法存储的树结构，正好和双亲表示法相反，适用于查找某结点的孩子结点，不适用于查找其父结点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 4]

## 双亲孩子表示法 ##

将双亲表示法和孩子表示法结合起来  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 5]

## 孩子兄弟表示法 ##

使用链式存储结构存储普通树。链表中每个结点由 3 部分组成：  
![在这里插入图片描述][20201020222724448.png_pic_center]  
其中孩子指针域，表示指向当前结点的第一个孩子结点，兄弟结点表示指向当前结点的下一个兄弟结点。

#define ElemType int
    typedef struct CSNode{
        
        ElemType data;
        struct CSNode * firstchild,*nextsibling;
    }CSNode,*CSTree;

通过孩子兄弟表示法，普通树转化为了二叉树，所以孩子兄弟表示法又被称为“二叉树表示法”或者“二叉链表表示法”。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 6]

[树的双亲表示法、孩子表示法和孩子兄弟表示法][Link 1]

# 比较 #

## 树与线性表 ##

![在这里插入图片描述][20201020220953100.png_pic_center]

## 树与森林 ##

一棵树为树，两棵树及以上则称为森林  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 7]

[2020102021453424.png_pic_center]: /images/20221123/3d708944130c4899b2f5cfe59cf5a254.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/8df3c0451010465ab05972d241c1c5b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/5738fb555a5541b8ac2cafc0d0c1e7b7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/500e3f261d2a41518a04f51d3f7eb8e6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/f659074e582c4a7aaf6b48e64e7c2eb3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/004be00b3bd64238a953a47283d7f43f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/0a68fdc9658948e08727a02e0bec6b68.png
[20201020222724448.png_pic_center]: /images/20221123/a473772b18aa44d08a1d85aa38e24562.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/3eafd217b73046228682fc9a359ebc40.png
[Link 1]: http://data.biancheng.net/view/30.html
[20201020220953100.png_pic_center]: /images/20221123/048a4c5480794783a471550d7fc62fa8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/216c50828497498f985f29a7714c1b54.png