데이터 구조 - 트 리 의 실현 (C 언어)

1. 나무의 개념
    트 리 구 조 는 노드 간 과 분기 관계 가 정의 하 는 차원 구조 이다.중요 한 비 선형 구조 로 서 나무 구조 중의 한 노드 는 최대 하나의 전구 노드 만 있 지만 여러 개의 후계 노드 가 있 을 수 있다.
2. 나무의 저장 구조
    컴퓨터 에서 나 무 는 여러 가지 저장 방식 이 있 는데 다음은 동태 적 인 '왼쪽 / 오른쪽 형' 이 진 링크 표시 방법 을 소개 한다.

#include "mytree.h"
#include 

using namespace std;

#define OK 		(0)
#define ERROR	(-1)

#define MAX_NAME_LEN (50) //       

/*         */
typedef struct _ElementType
{
	int id;
	char name[MAX_NAME_LEN];
}ElementType;

/*      */
typedef struct _TreeNode
{
	int index;//     
	ElementType element;   //   
	struct _TreeNode *FirstChild; //       	
	struct _TreeNode *NextSibing; //        
}TreeNode;

/*    */
typedef struct _CTree
{
	int num; //    
	vector nodeIndexs;//       index
	int rootIndex;//    index
	TreeNode *root; //     
}CTree;

/*         */
CTree g_tree;

/*
*      ：     index    
*	   ：      index
*	   ：  index  true，    index  false
*/
static bool mytree_check_node_index(const int index)
{
	vector::iterator it;

	for(it = g_tree.nodeIndexs.begin(); it != g_tree.nodeIndexs.end(); ++it )
	{
		if(*it == index)
		{
			return true;
		}
	}

	return false;
}

/*
*      ：         
*	   ：   ，    index，  nodeinfo
*	    ：NA
*/
void mytree_preorder_get_node(TreeNode *tree,	int index,   TreeNode *nodeinfo)
{
	if (NULL != tree)
	{
		if (tree->index == index)
		{
			nodeinfo = tree;
			return;
		}
		mytree_preorder_get_node(tree->FirstChild, index, nodeinfo);
		mytree_preorder_get_node(tree->NextSibing, index, nodeinfo);
	}
	
	return ;
}

/*
*	  ：     index         
*	  ：     index
*	   ：           ，     NULL
*/
TreeNode *mytree_get_node_by_index(const int index)
{
	TreeNode *tmpNode = NULL;
	TreeNode *root = NULL;
		
	if(true != mytree_check_node_index(index)) 
	{
		printf("invalied index
");
		return NULL;
	}

	root = g_tree.root;

	//      ，         
	mytree_preorder_get_node(root, index, tmpNode);

	return tmpNode;
}


/*
*	  ：         
*	  ：parentIndex:     index
	  element ：       
*	   ：      0，     -1
*/
int mytree_set_child(int parentIndex, int index, ElementType element)
{
	TreeNode *parentNode = NULL;
	TreeNode *newNode = NULL;
	TreeNode *head = NULL;
	TreeNode *lastChild = NULL;
	
	//         
	if(true != mytree_check_node_index(parentIndex)) 
	{
		printf("invalied parent index
");
		return ERROR;
	}

	parentNode = mytree_get_node_by_index(parentIndex);
	if (NULL == parentNode)
	{
		return ERROR;
	}

	//lastChild = mytree_get_last_child(parentNode);
	newNode = (TreeNode *)malloc(sizeof(TreeNode));
	if(NULL == newNode)
	{
		return ERROR;
	}
	memset(newNode, 0, sizeof(TreeNode));
	newNode->index = index;
	newNode->element.id = element.id;
	memcpy(newNode->element.name, element.name, MAX_NAME_LEN);

	g_tree.nodeIndexs.push_back(index);
	g_tree.num++;

	if (NULL == parentNode->FirstChild)
	{
		parentNode->FirstChild = newNode;
		return OK;
	}
	
	if(NULL == parentNode->NextSibing)
	{
		parentNode->NextSibing = newNode;
		return OK;
	}

	head = parentNode->NextSibing;
	while(head)
	{
		lastChild = head;
		head = head->NextSibing;
	}

	lastChild->NextSibing = newNode;

	return OK;
}

/*
*	  ：         
*	  ：  element ：      
*	   ：      0，     -1
*/
int mytree_set_root( ElementType element)
{
	//         
	TreeNode *newNode = NULL;

	newNode = (TreeNode *)malloc(sizeof(TreeNode));
	if (NULL == newNode)
	{
		return ERROR; 
	}
	memset(newNode, 0, sizeof(TreeNode));

	newNode->index = 0;//   index
	newNode->FirstChild = NULL;
	newNode->NextSibing = NULL;
	newNode->element.id = element.id;
	memcpy(newNode->element.name, element.name, MAX_NAME_LEN);

	g_tree.nodeIndexs.push_back(0);
	g_tree.num++;
	g_tree.root = newNode;
	
	return OK;
}


/*
*	  ：      
*	  ： 
*	   ： 
*/
void mytree_init()
{
	g_tree.num = 0;
	g_tree.rootIndex = 0;
	g_tree.root = NULL;

	return;
}


/*
*      ：         
*	   ：   ，    index，  nodeinfo
*	    ：NA
*/
void mytree_preorder_visit(TreeNode *tree)
{
	if (NULL != tree)
	{
		printf("tree index :%d
", tree->index);
		printf("tree element id :%d
", tree->element.id);
		printf("tree element id :%s
", tree->element.name);
		mytree_preorder_get_node(tree->FirstChild);
		mytree_preorder_get_node(tree->NextSibing);
	}
	
	return ;
}


/*
*      ：        
*	   ：   ，    index，  nodeinfo
*	    ：NA
*/
void mytree_dump()
{
	//                
	mytree_preorder_visit(g_tree.root)
	return ;
}


/*
*	  ：     
*	  ： 
*	   ： 
*/

void mytree_create()
{
	ElementType element;

	memset(&element, 0, sizeof(ElementType));
	//      
    mytree_init();
	//       
	element.id = 0;
	strcncpy(element.name, "root", sizeof(element.name)-1);
	mytree_set_root(element);

	//      
	memset(&element, 0, sizeof(ElementType));
	element.id = 1;
	strcncpy(element.name, "root-child-1", sizeof(element.name)-1);
	mytree_set_child(0, 1, element);

	memset(&element, 0, sizeof(ElementType));
	element.id = 2;
	strcncpy(element.name, "root-child-2", sizeof(element.name)-1);
	mytree_set_child(0, 2, element);

	memset(&element, 0, sizeof(ElementType));
	element.id = 3;
	strcncpy(element.name, "root-child-3", sizeof(element.name)-1);
	mytree_set_child(0, 3, element);

	memset(&element, 0, sizeof(ElementType));
	element.id = 4;
	strcncpy(element.name, "root-child-1-1", sizeof(element.name)-1);
	mytree_set_child(1, 4, element);

	memset(&element, 0, sizeof(ElementType));
	element.id = 5;
	strcncpy(element.name, "root-child-1-2", sizeof(element.name)-1);
	mytree_set_child(1, 5, element);

	return ;
}

/*
*	  ：       
*	  ： 
*	   ： 
*/

void tree_test()
{
    //     
	mytree_create();

	//      
	mytree_dump();
	return ;
}