devbox
Monodyee
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C语言数据结构之树（保姆级讲解）_c语言的图与树

作者：Monodyee | 2024-05-07 21:14:57

赞

踩

c语言的图与树

前言

         树是“一对多”的非线性存储结构，较链表、队列那些，树的概念会多点，涵盖的范围也较广。

C语言数据结构之单链表

C语言数据结构之双向链表

c语言数据结构之栈

c语言数据结构之队列

1 树概念

1.1  树基本术语

图1

 

 双亲节点：以A、B、C、D为例，A是BCD的双亲节点；

孩子节点：以A、B、C、D为例，BCD是A的子节点；

兄弟节点：BCD有共同的父节点A，所以BCD之间又互为兄弟节点；

叶子节点：没有孩子节点的节点，例如K、L、M节点；

根节点：没有双亲结点的节点；

子树：A是整棵树的树根节点，单看BEFKL节点，也可以看成单独的树，B节点为该树的树根，                 所以BEFKL节点称为子树；

树：由根节点和若干子树构成；单个节点也可以看成树，只有一个树根节点；

节点的度：该节点拥有孩子节点的个数，A节点的度为3；

树的度：比较树中各节点的度，最大节点的度为该树的度，以上的树的度为3；

树的深度（高度）：根节点为第一层，然后依此类推，KLM在第四层，所以，以上树深度为4；

有序树：树中各节点位置不能互换的叫有序树；无序树，节点位置则可以互换；

空树：没有任何节点；

森林：由 n （n>=0）个互不相交的树组成的叫森林；以上去除 A 节点，分别以 B、C、D 为根节点的三棵子树就可以称为森林。

1.2  二叉树

二叉树：顾名思义，就是子节点的个数不能超过2个的有序树，只能0、1和2；二叉树又可以细分为满二叉树和完全二叉树；

满二叉树：二叉树中除了叶子结点，每个结点的度都为 2，则称为满二叉树；

完全二叉树：一个深度为k，有n个节点的二叉树中，节点按从上至下、从左到右的顺序进行编号，编号为 i (1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同则为完全二叉树。

 2 二叉树节点的遍历

图二
图2

 

2.1 前序遍历

公式：先“根”节点，再左子树，后右子树。

此处说的“根”节点并不是特指树的根节点，如图2，由树的根节点A开始遍历，然后遍历左节点B，然后以B节点作为“根”节点，继续套用公式，再左后右，所以下一个遍历D节点，直到叶子节点处不再有子节点，就往回找右节点，以此类推......

图2的前序遍历最终顺序为：A->B->D->H->E->C->F->I->G。

2.2 中序遍历

公式：先左子树，再“根”节点，后右子树。

如图2，把该树看成由根节点A和左、右子树组成的一棵树；先看左子树：套公式，先左，从H节点开始，再“根”遍历D，该“根”没有右节点，则继续往上找（在D、H组成的子树中，D为根，H为左；而在B、D、E组成的子树中，B为根，D为左，E为右节点），接下来遍历“根”节点B，后遍历右节点E，以此类推......

图2的中序遍历最终顺序为：H->D->B->E->A->I->F->C->G。

2.3 后序遍历

 公式：先左子树，再右子树，后根节点。

后序遍历就不多解释了，跟前两个差不多逻辑，

图2的后序遍历最终顺序为：H->D->E->B->I->F->G->C->A。

3 树实例编写

3.1  实现逻辑概要

接下来我们要实现的树形结构并非二叉树，双亲节点下可以有多个孩子节点；

功能：

        ①可以在树形结构中，指定的节点下添加孩子节点；

        ②遍历树中节点，找出指定节点的双亲节点和孩子节点，并打印在终端；

        ③退出程序并释放节点内存空间。

3.2  程序分析

3.2.1  定义相关结构体

节点数据最大不能超过32个字节；

struct _bro结构体，用来链接双亲节点下的各兄弟节点；

struct _node结构体中，data指向节点具体数据，parent指向该节点的双亲节点，head_child指向首个孩子节点，child_count表示该节点下的孩子节点个数，cur_high表示该节点所在树结构中的层数；

struct _tree结构体，包含一个节点变量和树的深度（tree_high）。

  1. typedef char Data_type;  //数据类型
  2. #define DATA_LEN_MAX  32
  3.  
  4. typedef struct _bro {    //亲兄弟
  5.     struct _bro *next;
  6. }Bro_t;
  7.  
  8. typedef struct _node {
  9.     Data_type *data;            //节点数据
  10.     struct _node *parent;       //双亲节点
  11.     struct _node *head_child;   //孩子节点
  12.     int child_count;            //孩子个数
  13.     Bro_t bro_list;             //亲兄弟节点链表
  14.     int cur_high;               //当前节点层次，根节点为1
  15. }Node_t;
  16.  
  17. typedef struct _tree {
  18.     Node_t *node;           //树的节点
  19.     int tree_high;          //树的高度
  20. }Tree_t;

3.2.2 节点位置遍历函数

传入参数：树和双亲结点数据；

通过比较节点数据找到双亲节点，并将该节点地址值返回；

查找的方法就是二叉树的先序遍历方法，先根节点，再左子树，后右子树，直到找到为止，在这里兄弟节点的链表就发挥了很大作用。

  1. /*****************************************
  2.  * Fuction :查找双亲节点（类似前序遍历）
  3.  * root    ：传递树根
  4.  * Pdata   ：传递查找的父节点数据
  5.  * ***************************************/
  6. Node_t *find_parent_node(Tree_t *root,Data_type *Pdata)
  7. {
  8.     Node_t *p = root->node;
  9.  
  10.     while(1) {
  11.         if(strcmp(p->data,Pdata) == 0){            //找到节点 退出
  12.             //printf("find parent node succeed .\n");
  13.             return p;
  14.         }
  15.         else{
  16.             if(p->head_child != NULL) {     //判断该节点是否有子节点
  17.                 p = p->head_child;
  18.             }
  19.             else {
  20.                 if(p->bro_list.next != NULL) {      //没有子节点，则判断是否有兄弟节点
  21.                     p = (Node_t *)p->bro_list.next;
  22.                 }
  23.                 else {
  24.                     while(1) {
  25.                         p = p->parent;
  26.                         if(p->parent == NULL) {          //往树根节点方向查找还未遍历的节点，直到树根处退出遍历
  27.                             printf("find parent node fail !\n");
  28.                             return NULL;
  29.                         }                           
  30.                         if(p->bro_list.next != NULL) {
  31.                             p = (Node_t *)p->bro_list.next;
  32.                             break;
  33.                         }
  34.                     }
  35.                 }
  36.             }
  37.         }
  38.     }
  39. }

3.2.3 兄弟链表函数

参数：传递新添加的节点；

双亲节点的head_child作为兄弟链表表头，表尾node->bro_list.next指向NULL表示结束。

  1. /********************************
  2.  * Fuction :链接亲兄弟节点
  3.  * node    :添加的节点
  4.  * ******************************/
  5. void bro_node_list(Node_t *node)
  6. {
  7.     Node_t *p = node->parent;
  8.     Node_t *q = p->head_child;
  9.  
  10.     if(p->child_count == 0) {
  11.         p->head_child = node;
  12.         node->bro_list.next = NULL;
  13.         p->child_count += 1;
  14.     }
  15.     else {
  16.         while(q->bro_list.next != NULL){
  17.             q = (Node_t *)q->bro_list.next;
  18.         }
  19.         q->bro_list.next = (Bro_t *)node;
  20.         node->bro_list.next = NULL;
  21.     }
  22. }

3.2.4  添加节点函数

这里需要传递三个参数：树，父节点数据，新节点数据；

首先，需要为所创建的节点申请结构体变量内存空间和节点数据存放空间，内存申请失败则直接退出创建；如果创建新节点之前为空树，则新创建的节点作为树根节点，否则就通过函数find_parent_node查找父节点的位置，查找失败退出，成功就添加新节点，并将新节点添加到兄弟链表中。

该函数主要做的就是填充结构体变量，使各节点联系起来。

  1. /*************************************************
  2.  * Fuciton :在树中创建一个新节点，新节点挂在双亲节点下
  3.  * root    :传递树根节点
  4.  * Pdata   :双亲节点的数据
  5.  * Data    :新节点的数据
  6.  * ***********************************************/
  7. void create_tree_node(Tree_t *root, Data_type *Pdata, Data_type *Data)
  8. {
  9.     Node_t *node = (Node_t *)malloc(sizeof(Node_t));
  10.     Node_t *p = NULL;
  11.     Data_type *data_buf = (Data_type *)malloc(strlen(Data)+ 1);
  12.     
  13.     if((node == NULL) || (data_buf == NULL)) {
  14.         printf("malloc failed !\n");
  15.         return ;
  16.     }
  17.  
  18.     strcpy(data_buf,Data);
  19.  
  20.     if(root->node == NULL) {        //树根
  21.         root->node = node;      
  22.         root->tree_high = 1;    
  23.         node->data = data_buf;
  24.         node->parent = NULL;
  25.         node->head_child = NULL;
  26.         node->child_count = 0;
  27.         node->bro_list.next = NULL;
  28.         node->cur_high = 1;
  29.     }
  30.     else {
  31.         p = find_parent_node(root,Pdata);
  32.         if(p != NULL) {             //找到双亲节点
  33.             node->data = data_buf;
  34.             node->parent = p;
  35.             node->head_child = NULL;
  36.             node->child_count = 0;
  37.             node->cur_high = p->cur_high + 1;
  38.             if(node->cur_high > root->tree_high) {
  39.                 root->tree_high = node->cur_high;
  40.             }     
  41.             bro_node_list(node);
  42.         }
  43.         else {
  44.             free(node);
  45.             free(data_buf);
  46.         }
  47.     }
  48. }

3.2.5 节点内存释放函数

参数：传递树；

节点的内存释放只能从叶子节点开始，不然各节点的联系就会被破坏，从而无法找到其它节点，这里利用后序遍历法进行查找，先左子树，再右子树，后根节点；

通过for(p; p->head_child != NULL; p = p->head_child)查找树的最终左子树，然后判断该节点在兄弟链表中是否有其它的节点，如果有，则去查找该子树的叶子节点，从叶子节点开始释放，没有的话就释放掉，回到双亲节点继续查找。

  1. /**********************************
  2.  * Fuction :释放掉节点申请的内存(后序遍历方法)
  3.  * root    :传递树根节点
  4.  * *******************************/
  5. void free_tree_nodes(Tree_t *root)
  6. {
  7.     Node_t *p = root->node;
  8.     Node_t *temp = NULL;
  9.     int free_count = 0;
  10.  
  11.     if(p == NULL) {
  12.         printf("empty tree! \n");
  13.         return;
  14.     }        
  15.     for(p; p->head_child != NULL; p = p->head_child);       //查找左子树的叶子节点
  16.  
  17.     do {
  18.         if(p->bro_list.next != NULL) {          //判断该节点是否有兄弟节点
  19.             temp = p;
  20.             printf(" free data is %s\n",temp->data);
  21.             p = (Node_t *)p->bro_list.next;
  22.             free(temp);
  23.             for(p; p->head_child != NULL; p = p->head_child);          
  24.         }
  25.         else {
  26.             temp = p;
  27.             printf(" free data is %s\n",temp->data);
  28.             p = p->parent; 
  29.             free(temp);
  30.         }
  31.         ++free_count;
  32.     }while(p != NULL);
  33.     printf("%d-Node memory free OK.\n",free_count);
  34. }

3.3 程序汇总

  1. /****************************************
  2. Fuction:C语言实现树
  3. Time:11/21/2022
  4. Author:Qurry
  5. ****************************************/
  6.  
  7. #include <stdio.h>
  8. #include <stdlib.h>
  9. #include <string.h>
  10.  
  11. typedef char Data_type;  //数据类型
  12. #define DATA_LEN_MAX  32
  13.  
  14. typedef struct _bro {    //亲兄弟
  15.     struct _bro *next;
  16. }Bro_t;
  17.  
  18. typedef struct _node {
  19.     Data_type *data;            //节点数据
  20.     struct _node *parent;       //双亲节点
  21.     struct _node *head_child;   //孩子节点
  22.     int child_count;            //孩子个数
  23.     Bro_t bro_list;             //亲兄弟节点链表
  24.     int cur_high;               //当前节点层次，根节点为1
  25. }Node_t;
  26.  
  27. typedef struct _tree {
  28.     Node_t *node;           //树的节点
  29.     int tree_high;          //树的高度
  30. }Tree_t;
  31.  
  32. /*****************************************
  33.  * Fuction :查找双亲节点（类似前序遍历）
  34.  * root    ：传递树根
  35.  * Pdata   ：传递查找的父节点数据
  36.  * ***************************************/
  37. Node_t *find_parent_node(Tree_t *root,Data_type *Pdata)
  38. {
  39.     Node_t *p = root->node;
  40.  
  41.     while(1) {
  42.         if(strcmp(p->data,Pdata) == 0){            //找到节点 退出
  43.             //printf("find parent node succeed .\n");
  44.             return p;
  45.         }
  46.         else{
  47.             if(p->head_child != NULL) {     //判断该节点是否有子节点
  48.                 p = p->head_child;
  49.             }
  50.             else {
  51.                 if(p->bro_list.next != NULL) {      //没有子节点，则判断是否有兄弟节点
  52.                     p = (Node_t *)p->bro_list.next;
  53.                 }
  54.                 else {
  55.                     while(1) {
  56.                         p = p->parent;
  57.                         if(p->parent == NULL) {          //往树根节点方向查找还未遍历的节点，直到树根处退出遍历
  58.                             printf("find parent node fail !\n");
  59.                             return NULL;
  60.                         }                           
  61.                         if(p->bro_list.next != NULL) {
  62.                             p = (Node_t *)p->bro_list.next;
  63.                             break;
  64.                         }
  65.                     }
  66.                 }
  67.             }
  68.         }
  69.     }
  70. }
  71.  
  72. /********************************
  73.  * Fuction :链接亲兄弟节点
  74.  * node    :添加的节点
  75.  * ******************************/
  76. void bro_node_list(Node_t *node)
  77. {
  78.     Node_t *p = node->parent;
  79.     Node_t *q = p->head_child;
  80.  
  81.     if(p->child_count == 0) {
  82.         p->head_child = node;
  83.         node->bro_list.next = NULL;
  84.         p->child_count += 1;
  85.     }
  86.     else {
  87.         while(q->bro_list.next != NULL){
  88.             q = (Node_t *)q->bro_list.next;
  89.         }
  90.         q->bro_list.next = (Bro_t *)node;
  91.         node->bro_list.next = NULL;
  92.     }
  93. }
  94.  
  95. /*************************************************
  96.  * Fuciton :在树中创建一个新节点，新节点挂在双亲节点下
  97.  * root    :传递树根节点
  98.  * Pdata   :双亲节点的数据
  99.  * Data    :新节点的数据
  100.  * ***********************************************/
  101. void create_tree_node(Tree_t *root, Data_type *Pdata, Data_type *Data)
  102. {
  103.     Node_t *node = (Node_t *)malloc(sizeof(Node_t));
  104.     Node_t *p = NULL;
  105.     Data_type *data_buf = (Data_type *)malloc(strlen(Data)+ 1);
  106.     
  107.     if((node == NULL) || (data_buf == NULL)) {
  108.         printf("malloc failed !\n");
  109.         return ;
  110.     }
  111.  
  112.     strcpy(data_buf,Data);
  113.  
  114.     if(root->node == NULL) {        //树根
  115.         root->node = node;      
  116.         root->tree_high = 1;    
  117.         node->data = data_buf;
  118.         node->parent = NULL;
  119.         node->head_child = NULL;
  120.         node->child_count = 0;
  121.         node->bro_list.next = NULL;
  122.         node->cur_high = 1;
  123.     }
  124.     else {
  125.         p = find_parent_node(root,Pdata);
  126.         if(p != NULL) {             //找到双亲节点
  127.             node->data = data_buf;
  128.             node->parent = p;
  129.             node->head_child = NULL;
  130.             node->child_count = 0;
  131.             node->cur_high = p->cur_high + 1;
  132.             if(node->cur_high > root->tree_high) {
  133.                 root->tree_high = node->cur_high;
  134.             }     
  135.             bro_node_list(node);
  136.         }
  137.         else {
  138.             free(node);
  139.             free(data_buf);
  140.         }
  141.     }
  142. }
  143.  
  144. /**********************************
  145.  * Fuction :添加多个子树节点
  146.  * root    :传递树根节点
  147.  * *******************************/
  148. void add_tree_nodes(Tree_t *root)
  149. {
  150.     Data_type pdata_buf[DATA_LEN_MAX],data_buf[DATA_LEN_MAX];
  151.     memset(pdata_buf,0,DATA_LEN_MAX);
  152.     memset(data_buf,0,DATA_LEN_MAX);
  153.     printf("window下输入ctrl+z完成创建;linux下输入ctrl+d完成创建\n");
  154.     if(root->node == NULL){
  155.         printf("please input tree root data : \n");
  156.         scanf("%s",data_buf);
  157.         create_tree_node(root, NULL, data_buf);
  158.     }
  159.     printf("please input Pdata & data :\n");
  160.     while(scanf("%s %s",pdata_buf,data_buf) != EOF) {
  161.         printf("pdata_buf:%s,data_buf:%s \n",pdata_buf,data_buf);
  162.         create_tree_node(root, pdata_buf, data_buf);
  163.     }
  164.     printf("tree high is %d\n",root->tree_high);
  165. }
  166.  
  167. /**********************************
  168.  * Fuction :遍历打印树形结构
  169.  * root    :传递树根节点
  170.  * *******************************/
  171. void print_tree_node(Tree_t *root)
  172. {
  173.     Data_type temp[DATA_LEN_MAX];
  174.     Node_t *p = NULL;
  175.     int i = 0;
  176.     printf("please input node data :");
  177.     scanf("%s",temp);
  178.     p = find_parent_node(root,temp);
  179.     if(p == NULL) {
  180.         printf("node data error! \n");
  181.     }
  182.     else {
  183.         if(p->parent != NULL)
  184.             printf("Node parent data :%s\n",p->parent->data);
  185.         if(p->head_child != NULL) {
  186.             p = p->head_child;
  187.             while(1) {
  188.                 printf("Node child-%d:%s\n",i++,p->data);
  189.                 if(p->bro_list.next == NULL)
  190.                     break;
  191.                 p = (Node_t *)p->bro_list.next;
  192.             }
  193.         }
  194.     }
  195. }
  196.  
  197. /**********************************
  198.  * Fuction :释放掉节点申请的内存(后序遍历方法)
  199.  * root    :传递树根节点
  200.  * *******************************/
  201. void free_tree_nodes(Tree_t *root)
  202. {
  203.     Node_t *p = root->node;
  204.     Node_t *temp = NULL;
  205.     int free_count = 0;
  206.  
  207.     if(p == NULL) {
  208.         printf("empty tree! \n");
  209.         return;
  210.     }        
  211.     for(p; p->head_child != NULL; p = p->head_child);       //查找左子树的叶子节点
  212.  
  213.     do {
  214.         if(p->bro_list.next != NULL) {          //判断该节点是否有兄弟节点
  215.             temp = p;
  216.             printf(" free data is %s\n",temp->data);
  217.             p = (Node_t *)p->bro_list.next;
  218.             free(temp);
  219.             for(p; p->head_child != NULL; p = p->head_child);          
  220.         }
  221.         else {
  222.             temp = p;
  223.             printf(" free data is %s\n",temp->data);
  224.             p = p->parent; 
  225.             free(temp);
  226.         }
  227.         ++free_count;
  228.     }while(p != NULL);
  229.     printf("%d-Node memory free OK.\n",free_count);
  230. }
  231.  
  232. /*****************************
  233.  * Fuction : 模式菜单
  234.  * **************************/
  235. int menu_select()
  236. {
  237.     char mode[10];
  238.     printf("1:添加    2:打印    0:退出\n");
  239.     printf("Please input mode num: ");
  240.     scanf("%s",&mode);
  241.     if(mode[0] == '1')
  242.         return 1;
  243.     else if(mode[0] == '2')
  244.         return 2;
  245.     else if(mode[0] == '0')
  246.         return 0;
  247.     else
  248.         return -1;
  249. }
  250.  
  251. void main()
  252. {
  253.     int mode = -1;
  254.     Tree_t tree_root = {
  255.         .node = NULL,
  256.         .tree_high = 0,
  257.     };
  258.     Tree_t *tree_p = &tree_root;
  259.  
  260.     while(1) {
  261.         mode = menu_select();
  262.         switch(mode) 
  263.         {
  264.             case 0:
  265.                 free_tree_nodes(tree_p);
  266.                 return ;
  267.  
  268.             case 1:
  269.                 add_tree_nodes(tree_p);
  270.                 break;
  271.  
  272.             case 2:
  273.                 print_tree_node(tree_p);
  274.                 break;
  275.  
  276.             default :
  277.                 printf("mode input error !\n");
  278.                 break;
  279.         }
  280.     }
  281. }

4 测试结果

按照上图 图1 的树形结构进行测试，结果如下：

 

 

 

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号