目錄：
- 代碼：
- 分析：
- 匯編：
代碼：
LinkList.h
LinkList.c
線性表
GTree.h
#ifndef _GTREE_H_
#define _GTREE_H_typedef void GTree;//定義樹類型
typedef void GTreeData;//定義節點中存放數據的類型
typedef void (GTree_Printf)(GTreeData*);//定義一個參數是一個節點中存放數據的類型指針并且無返回值的函數類型GTree* GTree_Create();//聲明創建樹函數void GTree_Destroy(GTree* tree);//聲明銷毀樹函數void GTree_Clear(GTree* tree);//聲明清空樹函數int GTree_Insert(GTree* tree, GTreeData* data, int pPos);//聲明插入節點函數GTreeData* GTree_Delete(GTree* tree, int pos);//聲明刪除節點函數GTreeData* GTree_Get(GTree* tree, int pos);//聲明獲取節點函數GTreeData* GTree_Root(GTree* tree);//聲明獲取根節點函數int GTree_Height(GTree* tree);//聲明獲取高度函數int GTree_Count(GTree* tree);//聲明獲取節點數量函數int GTree_Degree(GTree* tree);//聲明獲取度數函數void GTree_Display(GTree* tree, GTree_Printf* pFunc, int gap, char div);//聲明給每個節點數據進行操作函數#endifGTree.c
#include <stdio.h>
#include <malloc.h>
#include "GTree.h"
#include "LinkList.h"typedef struct _tag_GTreeNode GTreeNode;//定義實際使用的樹節點類型
struct _tag_GTreeNode
{GTreeData* data;//節點內存放的數據指針GTreeNode* parent;//節點的父節點LinkList* child;//節點的子節點（一個鏈表類型）
};typedef struct _tag_TLNode TLNode;//定義樹節點與鏈表關聯的類型（用于插入到鏈表的）
struct _tag_TLNode
{LinkListNode header;GTreeNode* node;
};static void recursive_display(GTreeNode* node, GTree_Printf* pFunc, int format, int gap, char div)
{int i = 0;if( (node != NULL) && (pFunc != NULL) )//判斷節點與函數指針不為空{for(i=0; i<format; i++)//format 大于0時將輸出格式符 div{printf("%c", div);}pFunc(node->data);//執行函數（進行節點數據輸出）printf("\n");for(i=0; i<LinkList_Length(node->child); i++)//給該節點的每個子節點 執行相同操作{TLNode* trNode = (TLNode*)LinkList_Get(node->child, i);//取得子節點recursive_display(trNode->node, pFunc, format + gap, gap, div);//在每層子節點以2個格式占位符遞增}}
}static void recursive_delete(LinkList* list, GTreeNode* node)//定義遞歸刪除節點函數
{if( (list != NULL) && (node != NULL) )//判斷鏈表與樹節點不為空{GTreeNode* parent = node->parent;//取得刪除節點的父節點int index = -1;int i = 0;for(i=0; i<LinkList_Length(list); i++)//在鏈表中找出要刪除的節點{TLNode* trNode = (TLNode*)LinkList_Get(list, i);//取出鏈表中節點if( trNode->node == node )//如果該節點是要刪除的樹節點{LinkList_Delete(list, i);//將該節點從鏈表中刪除free(trNode);//將該節點的空間釋放（就是Insert函數中trNode申請的）index = i;//取得刪除的下標break;}}if( index >= 0 )//如果在鏈表中刪除了節點{ if( parent != NULL )//如果父節點不為空{for(i=0; i<LinkList_Length(parent->child); i++)//在父節點中的子鏈表中找到要刪除的節點{TLNode* trNode = (TLNode*)LinkList_Get(parent->child, i);//在父節點中的子鏈表中取出要刪除的節點if( trNode->node == node )//如果取出的節點是要刪除的節點 {LinkList_Delete(parent->child, i);//將該節點從父節點的子鏈表中刪除free(trNode);//該空間釋放（就是Insert函數中cldNode申請的）break;}} }while( LinkList_Length(node->child) > 0 )//如果刪除節點還有子節點{TLNode* trNode = (TLNode*)LinkList_Get(node->child, 0);//取出刪除節點中的子節點recursive_delete(list, trNode->node);//將要每個子節點執行同樣操作}LinkList_Destroy(node->child);//這必須放在while后面，free(node);//釋放樹節點空間（就是Insert函數中cNode申請的）這必須放在while后面}}
}static int recursive_height(GTreeNode* node)//定義遞歸計算樹高度函數
{int ret = 0;if( node != NULL )//如果節點不為空{int subHeight = 0;int i = 0;for(i=0; i<LinkList_Length(node->child); i++){TLNode* trNode = (TLNode*)LinkList_Get(node->child, i);//取出子節點subHeight = recursive_height(trNode->node);//遞歸調用從最后一個子節點開始計算if( ret < subHeight )//如果當前層的的數量小于子層返回的數量{ret = subHeight;//將這個節點的高度設為子層數量表示這個節點下有這么多層子節點//下面ret+1。然后返回到上一個節點就相當再加上自己本身的這層}}ret = ret + 1;//加一 表示有一層子節點，只要node（傳來的子節點）不為空必須加一}return ret;
}static int recursive_degree(GTreeNode* node)//定義遞歸計算樹度數函數
{
int ret = -1;if( node != NULL )//如果節點不為空{int subDegree = 0;int i = 0;ret = LinkList_Length(node->child);//獲取該節點的子鏈表的長度for(i=0; i<LinkList_Length(node->child); i++){TLNode* trNode = (TLNode*)LinkList_Get(node->child, i);//取出子節點subDegree = recursive_degree(trNode->node);//將每個子節點執行同樣操作if( ret < subDegree )//如果子節點的數量大于當前節點的子節點數量{//將返回最大數量，就是找出子節點最多的總數ret = subDegree;}}}return ret;
}GTree* GTree_Create()//定義創建樹函數
{return LinkList_Create();//調用創建鏈表
}void GTree_Destroy(GTree* tree)//定義銷毀樹函數
{GTree_Clear(tree);LinkList_Destroy(tree);
}void GTree_Clear(GTree* tree)//定義清空樹函數
{GTree_Delete(tree, 0);//刪除根節點所有的子節點也會刪除
}int GTree_Insert(GTree* tree, GTreeData* data, int pPos)//定義插入節點函數
{LinkList* list = (LinkList*)tree;//將樹指針轉成鏈表指針int ret = (list != NULL) && (data != NULL) && (pPos < LinkList_Length(list));//判斷表不為空插入的數據不為空與pPos正常if( ret )//條件成功{TLNode* trNode = (TLNode*)malloc(sizeof(TLNode));//新建樹節點與鏈表關聯類型// 注意：如果是下面pNode==NULL 。比如插入第一個節點時，后面這個cldNode申請的空間釋放不了TLNode* cldNode = (TLNode*)malloc(sizeof(TLNode));//新建樹節點與鏈表關聯類型TLNode* pNode = (TLNode*)LinkList_Get(list, pPos);//獲取出pPos位置的節點GTreeNode* cNode = (GTreeNode*)malloc(sizeof(GTreeNode));//新建一個樹類型節點ret = (trNode != NULL) && (cldNode != NULL) && (cNode != NULL);//判斷三個申請的空間成功if( ret )//條件成功{cNode->data = data;//給新建樹節點中存放的數據賦值cNode->parent = NULL;//給新建樹節點的父節點賦空cNode->child = LinkList_Create();//給新建節點的子節點賦值（新創建一個鏈表）trNode->node = cNode;//cldNode->node = cNode;LinkList_Insert(list, (LinkListNode*)trNode, LinkList_Length(list));//將新建節點插入鏈表最后一個位置if( pNode != NULL )//如果該位置本來有節點{cNode->parent = pNode->node;//將該位置本來有的節點賦給新建樹節點的的父節點//使用樹節點與鏈表關聯類型將新建節點插入到該位置本來節點的子鏈表最后一個位置LinkList_Insert(pNode->node->child, (LinkListNode*)cldNode, LinkList_Length(pNode->node->child));}}else//如果條件不成功將申請的空間釋放{free(trNode);free(cldNode);free(cNode);}}return ret;
}GTreeData* GTree_Delete(GTree* tree, int pos)//定義刪除節點函數
{TLNode* trNode = (TLNode*)LinkList_Get(tree, pos);//從鏈表中獲取出刪除位置節點GTreeData* ret = NULL;//定義指向刪除節點中存放的數據的指針if( trNode != NULL )//如果有該位置節點{ret = trNode->node->data;//取得刪除節點存放的數據//執行遞歸刪除在總鏈表與其父節點子鏈表中移除該節點，再將該節點的子節點執行同樣操作recursive_delete(tree, trNode->node);}return ret;//返回刪除節點中存放的數據指針
}GTreeData* GTree_Get(GTree* tree, int pos)//定義獲取節點數據函數
{TLNode* trNode = (TLNode*)LinkList_Get(tree, pos);//從鏈表中獲取出節點GTreeData* ret = NULL;if( trNode != NULL ){ret = trNode->node->data;//取得節點數據指針}return ret;//返回點中存放的數據指針
}GTreeData* GTree_Root(GTree* tree)//定義獲取根節點數據函數
{return GTree_Get(tree, 0);//調用獲取節點數據函數
}int GTree_Height(GTree* tree)//定義獲取樹的高度函數
{TLNode* trNode = (TLNode*)LinkList_Get(tree, 0);//取出第一個節點（根節點）int ret = 0;if( trNode != NULL ){ret = recursive_height(trNode->node);//調用遞歸計算高度}return ret;
}int GTree_Count(GTree* tree)//定義返回樹節點總數量函數
{return LinkList_Length(tree);//返回鏈表數量
}int GTree_Degree(GTree* tree)//定義獲取樹的度數函數
{TLNode* trNode = (TLNode*)LinkList_Get(tree, 0);//取得根節點int ret = -1;if( trNode != NULL ){ret = recursive_degree(trNode->node);//調用遞歸計算度數}return ret;
}void GTree_Display(GTree* tree, GTree_Printf* pFunc, int gap, char div)//定義給每個節點數據進行操作函數
{TLNode* trNode = (TLNode*)LinkList_Get(tree, 0);//取得根節點if( (trNode != NULL) && (pFunc != NULL) )//根節點與函數指針不為空{ recursive_display(trNode->node, pFunc, 0, gap, div);//調用遞歸處理}
}main.c
#include <stdio.h>
#include "GTree.h"
void printf_data(GTreeData* data)
{printf("%c", (int)data);
}int main(int argc, char *argv[])
{GTree* tree = GTree_Create();int i = 0;GTree_Insert(tree, (GTreeData*)'A', -1);GTree_Insert(tree, (GTreeData*)'B', 0);GTree_Insert(tree, (GTreeData*)'C', 0);GTree_Insert(tree, (GTreeData*)'D', 0);GTree_Insert(tree, (GTreeData*)'E', 1);GTree_Insert(tree, (GTreeData*)'F', 1);GTree_Insert(tree, (GTreeData*)'H', 3);GTree_Insert(tree, (GTreeData*)'I', 3);GTree_Insert(tree, (GTreeData*)'J', 3);printf("Tree Height: %d\n", GTree_Height(tree));printf("Tree Degree: %d\n", GTree_Degree(tree));printf("Full Tree:\n");GTree_Display(tree, printf_data, 2, ' ');printf("Get Tree Data:\n");for(i=0; i<GTree_Count(tree); i++){printf_data(GTree_Get(tree, i));printf("\n");}printf("Get Root Data:\n");printf_data(GTree_Root(tree));printf("\n");GTree_Delete(tree, 3);printf("After Deleting D:\n");GTree_Display(tree, printf_data, 2, '-');GTree_Clear(tree);printf("After Clearing Tree:\n");GTree_Display(tree, printf_data, 2, '.');GTree_Destroy(tree);getchar();return 0;
}分析：
匯編：
)
