树（tree）是包含n（n>0）个结点的有穷集，其中：
（1）每个元素称为结点（node）；
（2）有一个特定的结点被称为根结点或树根（root）。
（3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。
树也可以这样定义：树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。
以下为树的基本操作：
#ifndef __TREE_H__
#define __TREE_H__
#include "error.h"
struct _treeNode;
// 孩子结点链表的类型
typedef struct _childNode
{
struct _treeNode * childNode;
struct _childNode *next; // 指向孩子结点链表下一个元素
}ChildNode;
// 树节点类型
typedef char TreeData;
typedef struct _treeNode
{
TreeData data;
struct _treeNode *parent; // 指向父节点的指针
struct _treeNode *next; // 指向链表的下一个结点
struct _childNode *childList; // 孩子链表的头节点
int degree; // 结点的度
}TreeNode;
typedef struct _tree
{
struct _treeNode *head; // 树链表的头节点
int len; // 树结点个数
}Tree;
Tree *Create_Tree();
// pos 代表要插入结点父亲结点的位置
// 约定：
// 1 新插入的结点插入在当前父亲结点所有孩子的右边
// 2 根节点的位置是 0
int Insert_Tree(Tree *tree, TreeData data, int pos);
#endif // __TREE_H__
#include "tree.h"
#include <stdlib.h>
Tree *Create_Tree()
{
// 创建树节点
Tree* tree = (Tree*)malloc(sizeof(Tree)/sizeof(char));
if (tree == NULL)
{
errno = MALLOC_ERROR;
return NULL;
}
// 给树结点链表创建头节点
tree->head = (TreeNode*)malloc(sizeof(TreeNode)/sizeof(char));
if (tree->head == NULL)
{
errno = MALLOC_ERROR;
free (tree);
return NULL;
}
tree->head->parent = NULL;
tree->head->childList = NULL;
tree->head->next = NULL; // 代表树中没有结点
// 空树结点为0
tree->len = 0;
return tree;
}
/*
TreeData data;
struct _treeNode *parent; // 指向父节点的指针 11111111111
struct _treeNode *next; // 指向链表的下一个结点
struct _childNode *childList; // 孩子链表的头节点
int degree; // 结点的度
typedef struct _childNode
{
struct _treeNode * childNode;
struct _childNode *next; // 指向孩子结点链表下一个元素
}ChildNode;
*/
int Insert_Tree(Tree *tree, TreeData data, int pos)
{
if (tree == NULL || pos < 0 || pos >= tree->len)
{
errno = ERROR;
return FALSE;
}
// 新建结点
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode)/sizeof(char));
if (node == NULL)
{
errno = MALLOC_ERROR;
return FALSE;
}
node->data = data;
node->next = NULL;
// 创建该新节点的孩子结点链表的头节点
node->childList = (ChildNode*)malloc(sizeof(ChildNode)/sizeof(char));
if (node->childList == NULL)
{
errno = MALLOC_ERROR;
free (node);
return FALSE;
}
node->childList->next = NULL;
node->childList->childNode = NULL;
node->degree = 0;
int i;
// 找父节点
TreeNode* parent = tree->head->next; // 当前树节点的第一个结点
for (i = 0; i < pos; i++)
{
parent = parent->next;
}
node->parent = parent;
// 在父亲结点的子结点链表中加入一个结点
if (parent != NULL)
{
// 创建一个孩子结点
ChildNode* childnode = (ChildNode*)malloc(sizeof(ChildNode)/sizeof(char));
if (childnode == NULL)
{
errno = MALLOC_ERROR;
free(node->childList);
free (node);
return FALSE;
}
childnode->childNode = node;
childnode->next = NULL;
// 加入到父亲结点子结点链表当中
ChildNode* tmp = parent->childList; // 子结点链表的头节点
while (tmp->next)
tmp = tmp->next;
tmp->next = childnode;
parent->degree += 1;
}
TreeNode* tmp = tree->head; // 树节点链表的头节点
while (tmp->next)
tmp = tmp->next;
tmp->next = node;
tree->len += 1;
return TRUE;
}
#include <stdio.h>
#include "tree.h"
int main()
{
Tree *tree = Create_Tree();
if (tree == NULL)
{
myError("Create_Tree");
return -1;
}
Insert_Tree(tree, 'A', 0);
Insert_Tree(tree, 'B', 0);
Insert_Tree(tree, 'C', 0);
Insert_Tree(tree, 'D', 0);
Insert_Tree(tree, 'E', 1);
Insert_Tree(tree, 'F', 1);
Insert_Tree(tree, 'H', 3);
Insert_Tree(tree, 'I', 3);
Insert_Tree(tree, 'J', 3);
display(tree);
return 0;
}
