您的位置: 首页  >  文章  >  数据结构通用树

数据结构通用树

分类: 文章 • 2025-05-10 10:04:10

   今天来看大家介绍树，树是一种非线性的数据结构，树是由n个结点组成的有限集合，如果n=0,称为空树；如果n>0，则：有一个特定的称之为根的结点，它只有直接后继，但没有直接前驱；除根以外的其他结点划分为m个互不相交的有限集合，每个集合又是一棵树，并且称之为根的子树。

      如图

              数据结构通用树

      树的一些基本概念

l 树的结点包含一个数据以及若干指向子树的分支

l 结点拥有的子树数称为结点的度

u 度为0的结点称为叶结点

u 度不为0的结点称为分支结点

l 树的度定义为所有结点中的度的最大值

l 结点的直接后继称为该结点的孩子

u 相应的，该结点称为孩子的双亲

l 结点的孩子的孩子的.....称为该结点的子孙

u 相应的，该结点称为子孙的祖先

l 同一个双亲的孩子之间互称兄弟

l 树中结点的最大层次称为树的深度或高度

l 森林是由n（n>=0）棵互不相交的树组成的集合

在这里，我们用通用树结构来给大家介绍树的一些基本操作和操作实现。通用树的存储结构为：

   数据结构通用树

这里介绍通用树的常用操作：

l 创建树

l 销毁树

l 清空树

l 插入结点到树中

l 删除结点

l 获取某个结点

l 获取根结点

l 获取树的高度

l 获取总结点数

l 获取树的度

l 输出树

代码总分为三个文件：

GTree.h ： 放置功能函数的声明，以及树的声明，以及数据的声明 

GTree.c ： 放置功能函数的定义，以及树结点和组织链表结点的定义

Main.c   ： 主函数，使用功能函数完成各种需求，一般用作测试

整体结构图为：

 数据结构通用树

这里详细说下插入结点操作，删除结点操作：

 

插入结点操作：

数据结构通用树

如图：

 

  数据结构通用树

删除结点操作：

数据结构通用树

如图：

 

数据结构通用树

OK! 上代码：

GTree.h ： 

[cpp] view plain copy
  1. #ifndef _GTREE_H_  
  2. #define _GTREE_H_  
  3.   
  4. typedef void GTree;  
  5. typedef void GTreeData;  
  6. typedef void (GTree_Printf)(GTreeData*);  
  7.   
  8. GTree* GTree_Create();  
  9.   
  10. void GTree_Destroy(GTree* tree);  
  11.   
  12. void GTree_Clear(GTree* tree);  
  13.   
  14. int GTree_Insert(GTree* tree, GTreeData* data, int pPos);  
  15.   
  16. GTreeData* GTree_Delete(GTree* tree, int pos);  
  17.   
  18. GTreeData* GTree_Get(GTree* tree, int pos);  
  19.   
  20. GTreeData* GTree_Root(GTree* tree);  
  21.   
  22. int GTree_Height(GTree* tree);  
  23.   
  24. int GTree_Count(GTree* tree);  
  25.   
  26. int GTree_Degree(GTree* tree);  
  27.   
  28. void GTree_Display(GTree* tree, GTree_Printf* pFunc, int gap, char div);  
  29.   
  30. #endif  


 

GTree.c ： 

[cpp] view plain copy
  1. #include <stdio.h>  
  2. #include <malloc.h>  
  3. #include "GTree.h"  
  4. #include "LinkList.h"  
  5.   
  6. typedef struct _tag_GTreeNode GTreeNode;  
  7. struct _tag_GTreeNode  
  8. {  
  9.     GTreeData* data;  
  10.     GTreeNode* parent;  
  11.     LinkList* child;  
  12. };  
  13.   
  14. typedef struct _tag_TLNode TLNode;  
  15. struct _tag_TLNode  
  16. {  
  17.     LinkListNode header;  
  18.     GTreeNode* node;  
  19. };  
  20.   
  21. GTree* GTree_Create()  
  22. {  
  23.     return LinkList_Create();  
  24. }  
  25.   
  26. void GTree_Destroy(GTree* tree)  
  27. {  
  28.     GTree_Clear(tree);  
  29.       
  30.     LinkList_Destroy(tree);  
  31. }  
  32.   
  33. void GTree_Clear(GTree* tree)  
  34. {  
  35.     GTree_Delete(tree, 0);  
  36. }  
  37.   
  38. int GTree_Insert(GTree* tree, GTreeData* data, int pPos)  
  39. {  
  40.     LinkList* list = (LinkList*)tree;  
  41.       
  42.     int ret = (NULL!=list) && (NULL!=data) && (pPos<LinkList_Length(list));  
  43.       
  44.     if(ret)  
  45.     {  
  46.         TLNode* trNode = (TLNode*)malloc(sizeof(TLNode));  
  47.         TLNode* cldNode = (TLNode*)malloc(sizeof(TLNode));  
  48.         TLNode* pNode = (TLNode*)LinkList_Get(list, pPos);  
  49.           
  50.         GTreeNode* cNode = (GTreeNode*)malloc(sizeof(GTreeNode));  
  51.           
  52.         ret = (NULL!=trNode) && (NULL!=cldNode) && (NULL!=cNode);  
  53.           
  54.         if(ret)  
  55.         {  
  56.             cNode->data = data;  
  57.             cNode->parent = NULL;  
  58.             cNode->child = LinkList_Create();  
  59.               
  60.             trNode->node = cNode;  
  61.             cldNode->node = cNode;  
  62.               
  63.             LinkList_Insert(list, (LinkListNode*)trNode, LinkList_Length(list));  
  64.           
  65.             if(NULL != pNode)  
  66.             {  
  67.                 cNode->parent = pNode->node;  
  68.                   
  69.                 LinkList_Insert(pNode->node->child, (LinkListNode*)cldNode, LinkList_Length(pNode->node->child));  
  70.             }  
  71.             else  
  72.             {  
  73.                 free(cldNode);  
  74.             }  
  75.         }  
  76.         else  
  77.         {  
  78.             free(trNode);  
  79.             free(cldNode);  
  80.             free(cNode);  
  81.         }  
  82.     }  
  83.       
  84.     return ret;  
  85. }  
  86.   
  87. static int recursive_height(GTreeNode* node)  
  88. {  
  89.     int ret = 0;  
  90.       
  91.     if(NULL != node)  
  92.     {  
  93.         int subHeight = 0;  
  94.         int i = 0;  
  95.           
  96.         for(i=0; i<LinkList_Length(node->child); i++)  
  97.         {  
  98.             TLNode* trNode = (TLNode*)LinkList_Get(node->child, i);  
  99.               
  100.             subHeight = recursive_height(trNode->node);  
  101.               
  102.             if(ret < subHeight)  
  103.             {  
  104.                 ret = subHeight;  
  105.             }  
  106.         }  
  107.           
  108.         ret = ret+1;  
  109.     }  
  110.       
  111.     return ret;  
  112. }  
  113.   
  114.   
  115. int GTree_Height(GTree* tree)  
  116. {  
  117.     TLNode* trNode = (TLNode*)LinkList_Get(tree, 0);  
  118.       
  119.     int ret = 0;  
  120.       
  121.     if(NULL != trNode)  
  122.     {  
  123.         ret = recursive_height(trNode->node);  
  124.     }  
  125.       
  126.     return ret;  
  127. }  
  128.   
  129. static void recursive_delete(LinkList* list, GTreeNode* node)  
  130. {  
  131.     if((NULL != list) && (NULL != node))  
  132.     {  
  133.         GTreeNode* parent = node->parent;  
  134.           
  135.         int index = -1;  
  136.         int i = 0;  
  137.           
  138.         for(i=0; i<LinkList_Length(list); i++)  
  139.         {  
  140.             TLNode* trNode = (TLNode*)LinkList_Get(list, i);  
  141.               
  142.             if(node == trNode->node)  
  143.             {  
  144.                 LinkList_Delete(list, i);  
  145.                 free(trNode);  
  146.                 index = i;  
  147.                   
  148.                 break;  
  149.             }  
  150.         }  
  151.           
  152.         if(0 <= index)  
  153.         {  
  154.             if(NULL != parent)  
  155.             {  
  156.                 for(i=0; i<LinkList_Length(parent->child); i++)  
  157.                 {  
  158.                     TLNode* trNode = (TLNode*)LinkList_Get(parent->child, i);  
  159.                       
  160.                     if(node == trNode->node)  
  161.                     {  
  162.                         LinkList_Delete(parent->child, i);  
  163.                         free(trNode);  
  164.                           
  165.                         break;    
  166.                     }  
  167.                 }  
  168.             }  
  169.               
  170.             while(0 < LinkList_Length(node->child))  
  171.             {  
  172.                 TLNode* trNode = (TLNode*)LinkList_Get(node->child, 0);  
  173.                   
  174.                 recursive_delete(list, trNode->node);  
  175.             }  
  176.               
  177.             LinkList_Destroy(node->child);  
  178.             free(node);  
  179.         }  
  180.     }  
  181. }  
  182.   
  183. GTreeData* GTree_Delete(GTree* tree, int pos)  
  184. {  
  185.     TLNode* trNode = (TLNode*)LinkList_Get(tree, pos);  
  186.       
  187.     GTreeData* ret = NULL;  
  188.       
  189.     if(NULL != trNode)  
  190.     {  
  191.         ret = trNode->node->data;  
  192.           
  193.         recursive_delete(tree, trNode->node);  
  194.     }  
  195.       
  196.     return ret;  
  197. }  
  198.   
  199. GTreeData* GTree_Get(GTree* tree, int pos)  
  200. {  
  201.     TLNode* trNode = (TLNode*)LinkList_Get(tree, pos);  
  202.       
  203.     GTreeData* ret = NULL;  
  204.       
  205.     if(NULL != trNode)  
  206.     {  
  207.         ret = trNode->node->data;  
  208.     }  
  209.       
  210.     return ret;  
  211. }  
  212.   
  213. GTreeData* GTree_Root(GTree* tree)  
  214. {  
  215.     return GTree_Delete(tree, 0);  
  216. }  
  217.   
  218. int GTree_Count(GTree* tree)  
  219. {  
  220.     return LinkList_Length(tree);  
  221. }  
  222.   
  223. static int recursive_degree(GTreeNode* node)  
  224. {  
  225.     int ret = -1;  
  226.       
  227.     if(NULL != node)  
  228.     {  
  229.         int subDegree = 0;  
  230.         int i = 0;  
  231.           
  232.         ret = LinkList_Length(node->child);  
  233.           
  234.         for(i=0; i<LinkList_Length(node->child); i++)  
  235.         {  
  236.             TLNode* trNode = (TLNode*)LinkList_Get(node->child, i);  
  237.               
  238.             subDegree = recursive_degree(trNode->node);  
  239.               
  240.             if(ret < subDegree)  
  241.             {  
  242.                 ret = subDegree;  
  243.             }  
  244.         }  
  245.     }  
  246.       
  247.     return ret;  
  248. }  
  249.   
  250. int GTree_Degree(GTree* tree)  
  251. {  
  252.     TLNode* trNode = (TLNode*)LinkList_Get(tree, 0);  
  253.       
  254.     int ret = -1;  
  255.       
  256.     if(NULL != trNode)  
  257.     {  
  258.         ret = recursive_degree(trNode->node);  
  259.     }  
  260.       
  261.     return ret;  
  262. }  
  263.   
  264. static void recursive_display(GTreeNode* node, GTree_Printf* pFunc, int format, int gap, char div)  
  265. {  
  266.     int i = 0;  
  267.       
  268.     if((NULL != node) && (NULL != pFunc))  
  269.     {  
  270.         for(i=0; i<format; i++)  
  271.         {  
  272.             printf("%c", div);  
  273.         }  
  274.           
  275.         pFunc(node->data);  
  276.         printf("\n");  
  277.           
  278.         for(i=0; i<LinkList_Length(node->child); i++)  
  279.         {  
  280.             TLNode* trNode = (TLNode*)LinkList_Get(node->child, i);  
  281.               
  282.             recursive_display(trNode->node, pFunc, format+gap, gap, div);  
  283.         }  
  284.     }  
  285. }  
  286.   
  287. void GTree_Display(GTree* tree, GTree_Printf* pFunc, int gap, char div)  
  288. {  
  289.     TLNode* trNode = (TLNode*)LinkList_Get(tree, 0);  
  290.       
  291.     if((NULL != trNode) && (NULL != pFunc))  
  292.     {  
  293.         recursive_display(trNode->node, pFunc, 0, gap, div);  
  294.     }  
  295. }  


 

Main.c  ：

             

[cpp] view plain copy
  1. #include <stdio.h>  
  2. #include "GTree.h"  
  3.   
  4. void printf_data(GTreeData* data)  
  5. {  
  6.     printf("%c", (int)data);  
  7. }  
  8.   
  9. int main(void)  
  10. {  
  11.     GTree* tree = GTree_Create();  
  12.       
  13.     int i = 0;  
  14.       
  15.     GTree_Insert(tree, (GTreeData*)'A', -1);  
  16.     GTree_Insert(tree, (GTreeData*)'B', 0);  
  17.     GTree_Insert(tree, (GTreeData*)'C', 0);  
  18.     GTree_Insert(tree, (GTreeData*)'D', 0);  
  19.     GTree_Insert(tree, (GTreeData*)'E', 1);  
  20.     GTree_Insert(tree, (GTreeData*)'F', 1);  
  21.     GTree_Insert(tree, (GTreeData*)'H', 3);  
  22.     GTree_Insert(tree, (GTreeData*)'I', 3);  
  23.     GTree_Insert(tree, (GTreeData*)'J', 3);  
  24.       
  25.     printf("Tree Height: %d\n", GTree_Height(tree));  
  26.     printf("Tree Degree: %d\n", GTree_Degree(tree));  
  27.     printf("Full Tree:\n");  
  28.       
  29.     GTree_Display(tree, printf_data, 2, '-');  
  30.       
  31.     printf("Get Tree Data: \n");  
  32.       
  33.     for(i=0; i<GTree_Count(tree); i++)  
  34.     {  
  35.         printf_data(GTree_Get(tree, i));  
  36.         printf("\n");  
  37.     }  
  38.       
  39.     printf("Get Root Data: \n");  
  40.       
  41.     printf_data(GTree_Root(tree));  
  42.     printf("\n");  
  43.       
  44.     GTree_Delete(tree, 3);  
  45.     printf("After Deleting D: \n");  
  46.     GTree_Display(tree, printf_data, 2, '-');  
  47.       
  48.     GTree_Clear(tree);  
  49.       
  50.     printf("After Clearing Tree:\n");  
  51.       
  52.     GTree_Display(tree, printf_data, 2, '.');  
  53.       
  54.     GTree_Destroy(tree);  
  55.       
  56.     return 0;  
  57. }  
数据结构通用树

相关推荐