樹的實現與操作(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:
請按任意鍵繼續. . .








如有錯誤，望不吝指出。