抽象数据类型(ADT)-树
表、栈、队列都是线性数据结构，这次我们讲一个非线性数据结构 - 树。
树定义及相关概念
树可以用多种方式定义，用递归的方式定义是一种自然的方式。树是一些结点的集合，集合可以为空，若非空，则树由一个被称为根结点的 r 和零个或多个非空子树 T0, T1, ……, Tn 组成，这些子树的每一棵的根都由来自 r 的一条有向边所连接。
每一棵子树的根叫做结点 r 的儿子，r 称为每棵子树根的父亲，父亲的父亲结点称为祖父，儿子的儿子结点为孙子。如图中所示：结点 A 是结点 B, C, D, E, F 的父结点，B, C, D, E, F 是结点 A 的子结点，同理，C 是 G 的父结点，G 是 C 的子结点，H, I, J 是结点 D 的子结点，D 是 H, I, J 的父结点。G, H, I, J, K 是 A 的孙子结点，A 是 G, H, I, J, K 的祖父结点。
没有儿子的结点称为叶子结点，拥有相同父亲的结点称为兄弟结点。图中叶子结点有：B, G, H, I, J, E, K。B, C, D, E, F 互为兄弟结点，H, I, J 互为兄弟结点。
结点间的路径是指从结点一到结点二所经过的结点的序列。路径长指结点路径上所经过的边的条数。注意，结点间的路径都是有向的，即只能从祖先结点到子孙结点，结点一需要是结点二的祖先结点。
结点 ni 的深度是指从根结点到 ni 的路径长，结点 ni 的高度指的是从结点 ni 到叶子结点的最长路径的长。结点的深度和高度是不一样的，深度是指从根结点到该结点，高度是指从该结点到叶子结点。
树的实现
树实现时如果在结点在记录所有儿子结点指针是不现实的，因此采取一种方法，将一个结点的所有儿子结点连成一个链表 - 即在每个结点中记录下个兄弟结点的指针，然后在这个结点中记录它的第一个儿子的信息即可，如图所示：
结构定义为：
#define ELEMENT_TYPE int
typedef struct treeNode {
struct treeNode* firstChild;
struct treeNode* nextSibling;
ELEMENT_TYPE data;
}tagTreeNode;
实现接口：
#define TREE_OK (0) //成功
#define TREE_FAIL (-1) //失败
//遍历时结点操作函数指针
typedef void (*operateFunc)(tagTreeNode* node, int depth);
//创建根结点
tagTreeNode* createTree(ELEMENT_TYPE rootData);
//销毁树
int destroyTree(tagTreeNode* root);
//添加子结点
int addChild(tagTreeNode* parent, ELEMENT_TYPE data);
//删除子结点
int delChild(tagTreeNode* parent, ELEMENT_TYPE data);
//遍历树
void traversalTree(tagTreeNode* root, operateFunc func);
//查找结点
tagTreeNode* findNode(tagTreeNode* root, ELEMENT_TYPE data);
实现代码：
#define INIT_TREE_NODE(node, value) \
node->data = value; \
node->firstChild = NULL; \
node->nextSibling = NULL;
tagTreeNode* createTree(ELEMENT_TYPE rootData)
{
tagTreeNode* root = (tagTreeNode*)malloc(sizeof(tagTreeNode));
if (root == NULL)
return NULL;
INIT_TREE_NODE(root, rootData)
return root;
}
int destroyTree(tagTreeNode* root)
{
if (root == NULL)
return TREE_OK;
tagTreeNode* next;
for (tagTreeNode* node = root->firstChild; node != NULL; node = next) {
next = node->nextSibling;
destroyTree(node);
free(node);
}
return TREE_OK;
}
int addChild(tagTreeNode* parent, ELEMENT_TYPE data)
{
if (parent == NULL)
return TREE_FAIL;
tagTreeNode* node = (tagTreeNode*)malloc(sizeof(tagTreeNode));
if (node == NULL)
return TREE_FAIL;
INIT_TREE_NODE(node, data)
tagTreeNode* lastNode = parent->firstChild;
if (lastNode == NULL) {
parent->firstChild = node;
} else {
while (lastNode->nextSibling != NULL)
lastNode = lastNode->nextSibling;
lastNode->nextSibling = node;
}
return TREE_OK;
}
int delChild(tagTreeNode* parent, ELEMENT_TYPE data)
{
if (parent == NULL)
return TREE_FAIL;
tagTreeNode* pre = NULL;
for (tagTreeNode* node = parent->firstChild; node != NULL; pre = node, node = node->nextSibling) {
if (node->data == data) {
destroyTree(node);
if (pre == NULL)
parent->firstChild = node->nextSibling;
else
pre->nextSibling = node->nextSibling;
free(node);
return TREE_OK;
}
pre = node;
}
return TREE_OK;
}
static void traversalTreeInDepth(tagTreeNode* root, operateFunc func, int depth)
{
if (root == NULL)
return ;
if (func)
func(root, depth);
for (tagTreeNode* node = root->firstChild; node != NULL; node = node->nextSibling) {
traversalTreeInDepth(node, func, depth+1);
}
}
void traversalTree(tagTreeNode* root, operateFunc func)
{
int depth = 0;
traversalTreeInDepth(root, func, depth);
}
tagTreeNode* findNode(tagTreeNode* root, ELEMENT_TYPE data)
{
if (root == NULL)
return NULL;
if (root->data == data)
return root;
for (tagTreeNode* node = root->firstChild; node != NULL; node = node->nextSibling) {
tagTreeNode* result = findNode(node, data);
if (result != NULL)
return result;
}
return NULL;
}
测试代码：
void printNode(tagTreeNode* node, int depth)
{
for (int i = 0; i < depth; i++)
printf(" ");
printf("%d\n", node->data);
}
int main(int argc, char* argv[])
{
tagTreeNode* root;
root = createTree(0);
addChild(root, 1);
addChild(root, 2);
addChild(root, 3);
addChild(root, 4);
tagTreeNode* node = findNode(root, 1);
if (node != NULL) {
addChild(node, 11);
addChild(node, 13);
addChild(node, 15);
}
node = findNode(root, 2);
if (node != NULL) {
addChild(node, 22);
}
node = findNode(root, 4);
if (node != NULL) {
addChild(node, 45);
addChild(node, 48);
}
traversalTree(root, printNode);
node = findNode(root, 1);
if (node != NULL) {
delChild(node, 13);
printf("after del 13:\n");
traversalTree(root, printNode);
printf("after del 11:\n");
delChild(node, 11);
traversalTree(root, printNode);
printf("after del 15:\n");
delChild(node, 15);
traversalTree(root, printNode);
}
delChild(root, 2);
printf("after del 2:\n");
traversalTree(root, printNode);
return 0;
}
参考：
<数据结构与算法分析-C语言描述> P4- 版权声明：
