除根以外的其它结点划分为 m (m ≥0) 个互不相交的有限集合T0,T1,…,Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)
error.h
#ifndef __ERROR_H__ #define __ERROR_H__ #define TRUE 1 #define FALSE 0 #define ERROR -1 #define MALLOC_ERROR -2 int errno; void myError(char * str); char * myStrError(int num); #endif //__ERROR_H__error.c
#include "error.h" #include <stdio.h> void myError(char * str) { char * msg = myStrError(errno); printf ("%S:%S\n",str,msg); } char * myStrError(int num) { switch(errno) { case ERROR: return "参数错误"; case MALLOC_ERROR: return "空间分配失败"; } }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 _childNode * childList; struct _treeNode * next; int degree; }TreeNode; typedef struct _tree { struct _treeNode * head; int len; }Tree; //创建树 Tree * Create_Tree(); //插入树 int Insert_Tree(Tree * tree, TreeData data, int pos); //打印树 void Display(Tree * tree); //删除结点 void Delete(Tree * tree, int pos); #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; } 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; 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; } 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->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) { if (node == NULL) return; int i; for (i = 0; i < gap; i++) { printf ("%c",'-'); } printf ("%C\n",node->data); ChildNode * child = node->childList->next; while(child) { r_display (child->childNode,gap+4); child = child->next; } } //打印树 void Display(Tree * tree) { if (tree == NULL) return; r_display(tree->head->next,0); } void r_delete(Tree * tree, TreeNode * node) { } //删除结点 void Delete(Tree * tree, int pos) { 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_Clear(Tree * tree) { if (tree == NULL) { errno = ERROR; return FALSE; } TreeData x; return Delete (tree, 0,&x); }main.c
#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; }