数据结构之通用树（使用链表实现树的存储结构，双亲孩子表示法）

时间：2021-08-15 13:00:07

树是一种非线性的数据结构，可以使用链表组织树的各个节点，描述树的一些常用操作。双亲孩子表示法是指每个结点都有一个指向其双亲的指针，每个结点都有若干个指向其孩子的指针。

头文件：

tree.h

#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
{
TreeNode *head;    //指向树节点链表头节点的指针
int len;   //树节点的个数
}Tree;

typedef void (*TreePrint)(TreeNode *node);

//创建一棵树
Tree *Create_tree ();

// pos 代表要插入结点父亲结点的位置
// 约定：
// 1 新插入的结点插入在当前父亲结点所有孩子的右边
// 2 根节点的位置是 0
int Insert_Tree(Tree *tree, TreeData data, int pos);

//打印树
void Display(Tree *tree, TreePrint pFunc);

//删除节点
int Delete(Tree *tree, int pos, TreeData *x);

//求指定位置树节点的值
int Tree_Get(Tree* tree, int pos, TreeData *x);

// 清空树中所有的节点
int Tree_Clear(Tree* tree);

// 树的销毁 
void Tree_Destroy(Tree* tree);

//获取树根节点的地址
TreeNode* Tree_Root(Tree* tree);

//求树节点个数
int Tree_Count(Tree* tree);

//求树的高度
int Tree_Height(Tree* tree);

//求树的度
int Tree_Degree(Tree* tree);

#endif   //__TREE_H__




源文件：

tree.c

#include <stdlib.h>
#include <stdio.h>
#include "tree.h"

//创建一棵树
Tree *Create_tree ()
{
//创建树
Tree *tree = (Tree *)malloc(sizeof(Tree)/sizeof(char));
if(tree == NULL)
{
errno = MALLOC_ERROR;
return NULL;
}
//空树节点为0
tree->len = 0;
//创建树节点链表头节点
tree->head = (TreeNode *)malloc(sizeof(TreeNode)/sizeof(char));
if (tree->head == NULL)
{
free(tree);
errno = MALLOC_ERROR;
return NULL;
}
//树中没有节点
tree->head->parent = NULL;
tree->head->next   = NULL;
tree->head->childlist    = NULL;

return tree;
}

// pos 代表要插入结点父亲结点的位置
// 约定：
// 1 新插入的结点插入在当前父亲结点所有孩子的右边
// 2 根节点的位置是 0
int Insert_Tree(Tree *tree, TreeData data, int pos)
{
if (tree == NULL || pos < 0 || pos > tree->len)
{
errno = ERROR;
return FALSE;
}
if (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->next = NULL;
childnode->childNode = node;
//加入到父亲节点子节点链表中
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;
}

//递归打印
void r_display (TreeNode *node,TreePrint pFunc,int gap)
{
if (node == NULL)
{
return;
}
//打印距离第一个节点的距离
int i;
for (i = 0; i < gap;i++)
{
printf ("-");
}
pFunc(node);  //打印节点自己
ChildNode * child = node->childlist->next;  //该节点的第一个孩子
//打印该节点的孩子
while(child)
{
r_display (child->childNode,pFunc,gap+4);
child = child->next;
}
}

//打印树
void Display(Tree *tree, TreePrint pFunc)
{
if (tree == NULL)
{
errno = ERROR;
return;
}
r_display (tree->head->next,pFunc,0);
}

//递归删除
void r_delete(Tree *tree,TreeNode *node)
{
if (tree == NULL || node == NULL)
{
return;
}
//从树节点链表中移除这个节点，找node的前一个节点
TreeNode *tmp = tree->head;  //链表的头节点
while (tmp->next)
{
if (tmp->next == node)
{
tmp->next = node->next;
tree->len --;
break;
}
tmp = tmp->next;
}

//将父亲节点中子节点链表中指向node的节点删除
TreeNode *parent = node->parent;
if (parent != NULL)
{
ChildNode *tmp = parent->childlist;  //子节点链表的头节点
while (tmp->next)
{
if (tmp->next->childNode == node)
{
ChildNode *p = tmp->next;
tmp->next = p->next;
free(p);
parent->degree --;
break;
}
tmp = tmp->next;
}
}

//将该节点的孩子节点删掉
ChildNode* child = node->childlist->next;//子节点链表中第一个节点
while (child)
{
ChildNode * pchild = child->next;
r_delete (tree,child->childNode);
child = pchild;
}
free(node->childlist);
free(node);
}

//删除节点
int Delete(Tree *tree, int pos, TreeData *x)
{
if (tree == NULL || pos < 0 || pos >= tree->len || x == NULL)
{
errno = ERROR;
return FALSE;
}
int i;
TreeNode *current = tree->head->next;
for (i = 0;i < pos;i++)
{
current = current->next;
}
*x = current->data;

r_delete (tree,current);
return TRUE;
}


//求指定位置树节点的值
int Tree_Get(Tree* tree, int pos, TreeData *x)
{
if (tree == NULL || pos < 0 || pos >= tree->len)
{
errno = ERROR;
return FALSE;
}

int i;
// 找结点
TreeNode* current = tree->head->next;  
for (i = 0; i < pos; i++)
{
current = current->next;
}

*x = current->data;

return TRUE;
}

// 清空树中所有的节点
int Tree_Clear(Tree* tree)
{
if (tree == NULL)
{
errno = ERROR;
return FALSE;
}

TreeData x;
return Delete (tree, 0, &x);
}

//树的销毁
void Tree_Destroy(Tree* tree)
{
if (tree == NULL)
{
errno = ERROR;
return;
}

Tree_Clear(tree);

free (tree->head);
free (tree);
}

//获取树根节点的地址
TreeNode* Tree_Root(Tree* tree)
{
if (tree == NULL)
{
errno = ERROR;
return NULL;
}

return tree->head->next;
}

//求树节点个数
int Tree_Count(Tree* tree)
{
if (tree == NULL)
{
errno = ERROR;
return FALSE;
}

return tree->len;
}

//递归求高度
int r_height (TreeNode* node)
{
if (node == NULL)
{
errno = ERROR;
return FALSE;
}
int Height = 0;
int max = 0;
ChildNode* child = node->childlist->next;
while (child)
{
Height = r_height (child->childNode);
if (Height > max)
{
max = Height;
}
child = child->next;
}
return max + 1;
}

//求树的高度
int Tree_Height(Tree* tree)
{
if (tree == NULL)
{
errno = ERROR;
return FALSE;
}

int height = r_height(tree->head->next);
return height;
}

//递归求度
int r_degree (TreeNode* node)
{
if (node == NULL)
{
errno = ERROR;
return FALSE;
}
int Degree = 0;
int max = node->degree;
ChildNode* child = node->childlist->next;
while (child)
{
Degree = r_degree (child->childNode);
if (Degree > max)
{
max = Degree;
}
child = child->next;
}
return max;
}

//求树的度
int Tree_Degree(Tree* tree)
{
if (tree == NULL)
{
errno = ERROR;
return FALSE;
}

int degree = r_degree(tree->head->next);
return degree;
}


关于用链表实现树的存储结构（双亲孩子表示法）以及更多的操作，可以大家一起去实现。

标签：

相关文章