程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 樹的實現與操作(C語言實現)

樹的實現與操作(C語言實現)

編輯:關於C語言

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



如有錯誤,望不吝指出。



  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved