樹的實現與操作(C語言實現)
首先來簡單說下一些關於的基本概念。
樹是一種非線性的數據結構
1，樹是由 n(n>=0)個結點組成的有限集合
如果n = 0 ,稱為空樹
如果n > 0,則：
有一個特定的稱之為根（root）的結點，它只有直接後繼，但沒有直接前驅
除了根以外的其他結點劃分為：m(m>=0)個互不相交的有限集合，T0,T1,T2…Tn-1,每個集合又是一棵樹，並且稱之為根的子樹
2，樹中的概念：
樹的結點包括一個數據及若干指向子樹的分支
結點擁有的子樹樹稱為結點的度
度為0的結點稱為葉結點
度不為0的結點稱為分支結點
樹的度的定義為所有結點中的度的最大值
3,樹中結點之間的關系
(1)結點的直接後繼稱為該結點的孩子
(2)相應的該結點稱為孩子的雙親
(3)結點的孩子的孩子的……稱為該結點的子孫
(4)相應的該結點稱為子孫的祖先
(5)同一個雙親的孩子之間互稱兄弟
4，樹的深度或高度
(1)結點的層次
(2)根為第1層
(3)根的孩子為第2層
(4)……
(5)樹中結點的最大層次稱為樹的深度或高度
5，如果樹中結點的各子樹從左向右是有次序的,子樹間不能互換位置,則稱該樹為有序樹,否則為無序樹。
6，森林是由 n(n >=0)棵互不相交的樹組成的集合
7，樹的相關操作
樹的操作
樹的一些常用操作
->創建樹
->銷毀樹
->清空樹
->插入結點
->刪除結點
->獲取結點
->獲取根結點
->獲取樹的結點數
->獲取樹的高度
->獲取樹的度
樹在程序中表現為一種特殊的數據類型
樹的操作在程序中的表現為一組函數
Tree:
Tree*Tree_Create();
voidTree_Destroy(Tree* tree);
voidTree_Clear(Tree* tree);
intTree_Insert(Tree* tree, TreeNode* node, int pos);
TreeNode*Tree_Delete(Tree* tree, int pos);
TreeNode*Tree_Get(Tree* tree, int pos);
TreeNode*Tree_Root(Tree* tree);
intTree_Height(Tree* tree);
intTree_Count(Tree* tree);
intTree_Degree(Tree* tree);
再來說下，這裡樹的基本存儲結構。假定我們初始有一棵樹，那麼我們如何來規定他的存儲結構呢？
首先，我們規定每個樹結點中有三個屬性(1)表示其父親的指針(2)表示結點中的數據(3)表示孩子的鏈表，這裡為什麼是個鏈表呢？因為一個結點的的孩子可能有一個，也有可能有多個，所以用一個鏈表表示最為合適了。
第二，每個樹之間的關系，我們可以模仿二叉樹中的先序遍歷思想，對這顆樹進行遍歷，我們知道，遍歷的結果肯定是個序列，那麼我們此時就可以果斷的把這種序列認為是一種鏈表結構，那麼後期對於樹的操作也就可以移植到鏈表上來了。
最後，關於樹的深度、度、刪除、根結點的獲取與計算，都是在表示那顆樹的結點上來操作的。那麼這裡特別說明一下，由於整個樹存在兩個鏈表，所以對於每次刪除，插入都要向兩個鏈表中刪除和插入。（一個結點既要存在於他父親的孩子鏈表中，又要存在於表示整棵樹的鏈表中）
這裡我們用到了鏈表的知識，如果對於鏈表不熟悉，可以參閱鏈表的實現與操作(C語言實現)。這裡有詳盡的代碼。
源代碼：
#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);
#endif
CPP實現部分：
#include "stdafx.h"
#include
#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; idata);
printf("\n");
for(i=0; ichild); i++)
{
TLNode* trNode = (TLNode*)LinkList_Get(node->child, i);
recursive_display(trNode->node, pFunc, format + gap, gap, div);
}
}
}
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; inode == node )
{
LinkList_Delete(list, i);
free(trNode);
index = i;
break;
}
}
//如果index>0,則表明他有父親
if( index >= 0 )
{
if( parent != NULL )
{
//將他從他父親的孩子鏈表中刪除
for(i=0; ichild); i++)
{
TLNode* trNode = (TLNode*)LinkList_Get(parent->child, i);
if( trNode->node == node )
{
LinkList_Delete(parent->child, i);
free(trNode);
break;
}
}
}
//如果他有兒子，將他的兒子們都殺死
while( LinkList_Length(node->child) > 0 )
{
TLNode* trNode = (TLNode*)LinkList_Get(node->child, 0);
recursive_delete(list, trNode->node);
}
LinkList_Destroy(node->child);
free(node);
}
}
}
static int recursive_height(GTreeNode* node)
{
int ret = 0;
if( node != NULL )
{
int subHeight = 0;
int i = 0;
for(i=0; ichild); i++)
{
TLNode* trNode = (TLNode*)LinkList_Get(node->child, i);
subHeight = recursive_height(trNode->node);
if( ret < subHeight )
{
ret = subHeight;
}
}
ret = ret + 1;
}
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; ichild); 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 < LinkList_Length(list)
if( ret )
{
TLNode* trNode = (TLNode*)malloc(sizeof(TLNode)); //創建一個結點，用於記錄保存樹的鏈表中的結點
TLNode* cldNode = (TLNode*)malloc(sizeof(TLNode)); //孩子（是個鏈表）
TLNode* pNode = (TLNode*)LinkList_Get(list, pPos); //從表示樹的鏈表中獲取要插入結點父母親
GTreeNode* cNode = (GTreeNode*)malloc(sizeof(GTreeNode)); //要插入的結點，用於接收傳進來的data
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);
}
}
主函數操作部分：
// 樹.cpp : 定義控制台應用程序的入口點。
//
#include "stdafx.h"
#include "GTree.h"
#include
void printf_data(GTreeData* data)
{
printf("%c", (int)data);
}
int _tmain(int argc, _TCHAR* 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
運行結果：
Tree Height: 3
Tree Degree: 3
Full Tree:
A
B
E
F
C
D
H
I
J
Get Tree Data:
A
B
C
D
E
F
H
I
J
Get Root Data:
A
After Deleting D:
A
--B
----E
----F
--C
After Clearing Tree:
請按任意鍵繼續. . .
如有錯誤，望不吝指出。
