1、树的概念
树形结构是节点之间以及分支关系定义的层次结构。作为一种重要的非线性结构,树形结构中一个节点最多只有一个前驱节点,但是可以有多个后继节点。
2、树的存储结构
在计算机中,树有多种的存储方式,下面介绍一种动态的“左子/右兄”二叉链表表示方法。
#include ""
#include <vector>
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<int> 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<int>::iterator it;
for(it = g_tree.(); it != g_tree.(); ++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\n");
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\n");
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-> = ;
memcpy(newNode->, , 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-> = ;
memcpy(newNode->, , 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\n", tree->index);
printf("tree element id :%d\n", tree->);
printf("tree element id :%s\n", tree->);
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();
//设置树的根节点
= 0;
strcncpy(, "root", sizeof()-1);
mytree_set_root(element);
//设置叶子结点
memset(&element, 0, sizeof(ElementType));
= 1;
strcncpy(, "root-child-1", sizeof()-1);
mytree_set_child(0, 1, element);
memset(&element, 0, sizeof(ElementType));
= 2;
strcncpy(, "root-child-2", sizeof()-1);
mytree_set_child(0, 2, element);
memset(&element, 0, sizeof(ElementType));
= 3;
strcncpy(, "root-child-3", sizeof()-1);
mytree_set_child(0, 3, element);
memset(&element, 0, sizeof(ElementType));
= 4;
strcncpy(, "root-child-1-1", sizeof()-1);
mytree_set_child(1, 4, element);
memset(&element, 0, sizeof(ElementType));
= 5;
strcncpy(, "root-child-1-2", sizeof()-1);
mytree_set_child(1, 5, element);
return ;
}
/*
* 功能:测试当前树结构
* 入参:无
* 返回值:无
*/
void tree_test()
{
//创建一棵树
mytree_create();
//打印树的结点
mytree_dump();
return ;
}