简单给大家介绍一下树
树的定义
树是一种非线性的数据结构 树是由 n ( n ≥0 ) 个结点组成的有限集合 如果 n = 0，称为空树； 如果 n > 0，则： 有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱
除根以外的其它结点划分为 m (m ≥0) 个互不相交的有限集合T0,T1,…,Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)
树家族中的概念
树的结点包含一个数据及若干指向子树的分支 结点拥有的子树数称为结点的度 度为0的结点称为叶结点 度不为0的结点称为分支结点 注： 树的度定义为所有结点中的度的最大值
结点的直接后继称为该结点的孩子 相应的，该结点称为孩子的双亲 结点的孩子的孩子的……称为该结点的子孙 相应的，该结点称为子孙的祖先 同一个双亲的孩子之间互称兄弟
结点的层次 根为第1层 根的孩子为第2层 …… 注： 树中结点的最大层次称为树的深度或高度
如果树中结点的各子树从左向右是有次序的，子 树间不能互换位置，则称该树为有序树，否则为 无序树
下面是关于普通树的一些基本操作
#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; }
