干货7：树

#ifndef __TREE_H__ #define __TREE_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; // 定义一个函数指针类型 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__

#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; // 指向父节点的指针 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; } if (pos != 0 && tree->len == pos) { 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; } // 递归打印结点 void r_display(TreeNode* node, int gap, TreePrint pFunc) { if (node == NULL) return; // 打印距离前一个结点的距离 int i; for (i = 0; i < gap; i++) { printf ("%c", '-'); } // 打印结点自己 // printf ("%c\n", node->data); pFunc (node); ChildNode* child = node->childList->next; // 该结点的第一个孩子 // 打印该结点的孩子 while (child) { r_display (child->childNode, gap+4, pFunc); child = child->next; // 下一个孩子 } } void Display(Tree *tree, TreePrint pFunc) { if (tree == NULL) return; r_display(tree->head->next, 0, pFunc); } 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) { errno = ERROR; return FALSE; } if (pos != 0 && tree->len == pos) { 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; } if (pos != 0 && tree->len == pos) { 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) return 0; int subHeight = 0; int max = 0; ChildNode* child = node->childList->next; while (child) { subHeight = r_height(child->childNode); if (subHeight > max) max = subHeight; 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) return 0; int max = node->degree; int subDegree = 0; ChildNode* child = node->childList->next; while (child) { subDegree = r_degree(child->childNode); if (subDegree > max) max = subDegree; 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; }