n叉树 数据结构

树:
树有多种: 二叉树, 三叉树, 四叉树....n叉树.
每一个树中的元素, 称为树的节点,
起始元素称为根节点,
显示了一个层次关系的集合.
每一个层次之间又形成了新的子树.

树的重要概念
1.> 度:  节点的子树个数叫做这个节点的度.

2.> 叶子(终端节点): 度为0的节点称作是叶子, 通
俗的说就是这个节点没有子树了, 那这个节点就是一片叶子.

3.> 分支节点: 就是度不为0的节点叫做分支节点, 通俗的说
就是每一个包含有子树的节点就是分支节点.

4.> 不管是哪一种树, 都会有父亲节点, 孩子节点以及兄弟节点.

5.> 祖先节点/孙子节点, 从某一个树(子树)的根节点到该节点所经过的分支上的所有节点.

6.> 节点的层次: 从根节点开始算起, 根节点为第一层, 根的孩子为第二层.

7.> 深度: 从根到树的最大层次叫做深度(高度), 简单来说从根算起到他的最后一个孙子
所在的层次.

8.> 有序树: 从左到右的子树有次序, 否则就是无序树.

9.> 森林: 互不相交的树的一个集合.

定义部分:

struct TreeNode;
// 新建节点初始化
static struct TreeNode* InitTreeNode(int id, const char* name, int grade, const char* class);
// 树节点插入头
static struct TreeNode* InsertTreeNodeHead(struct TreeNode* root, struct TreeNode* node);
static void InsertTreeNodeHead_ptrToptr(struct TreeNode** root, struct TreeNode* node);
// 树节点插入尾
static struct TreeNode* InsertTreeNodeTail(struct TreeNode* root, struct TreeNode* node);
static void InsertTreeNodeTail_ptrToptr(struct TreeNode** root, struct TreeNode* node);
// 移除树
static void RemoveTree(struct TreeNode* node);
// 树遍历
static void TransTree(struct TreeNode* root);
static void DeleteTranser(struct TreeNode* node);

树结构以及初始化描述部分:

// 树的单个节点结构
struct TreeNode {// 数据部分int s_id;char s_name[10];int s_grade;char s_class[20];// 结构部分struct TreeNode* parent;struct TreeNode* brother;struct TreeNode* child;
};static struct TreeNode*
InitTreeNode(int id,const char* name,int grade,const char* class) {struct TreeNode* s_node = malloc(sizeof(struct TreeNode));memset(s_node, 0, sizeof(struct TreeNode));strcpy(s_node->s_name, name);s_node->s_id = id;s_node->s_grade = grade;strcpy(s_node->s_class, class);return s_node;
}

插入实现部分:

// 两种头插方式
static struct TreeNode*
InsertTreeNodeHead(struct TreeNode* root, struct TreeNode* node) {node->parent = root;node->brother = root->child;root->child = node;return root;
}static void 
InsertTreeNodeHead_ptrToptr(struct TreeNode** root, struct TreeNode* node) {node->parent = *root;node->brother = (*root)->child;(*root)->child = node;
}// 两种尾插方式
static struct TreeNode*
InsertTreeNodeTail(struct TreeNode* root, struct TreeNode* node) {node->parent = root;struct TreeNode* transer = root->child;while (transer->brother) {transer = transer->brother;}transer->brother = node;return root;
}static void
InsertTreeNodeTail_ptrToptr(struct TreeNode** root, struct TreeNode* node) {node->parent = *root;struct TreeNode** transer = &(*root)->child;while (*transer) {transer = &(*transer)->brother;}*transer = node;
}

树的遍历描述部分:

static void 
TransTree(struct TreeNode* root) {struct TreeNode* transer = root;while (transer) {printf("%d %s %d %s 0x%x\n", transer->s_id, transer->s_name, transer->s_grade, transer->s_class, transer->parent);TransTree(transer->child);transer = transer->brother;}
}

树的移除描述部分:

static void 
RemoveTree(struct TreeNode* node) {struct TreeNode* Parent = node->parent;struct TreeNode** transer = &(Parent->child);while (*transer) {if (*transer == node) {DeleteTranser(*transer);*transer = (*transer)->brother;return;}transer = &(*transer)->brother;}
}static void
DeleteTranser(struct TreeNode* node) {struct TreeNode* transer = node;while (transer) {struct TreeNode* currentNode = transer;DeleteTranser(transer->child);if (transer == node) {return;}transer = transer->brother;currentNode->child = NULL;currentNode->brother = NULL;currentNode->parent = NULL;free(currentNode);}
}