一.树是什么？
这个自己百度吧，不是此文重点。需了解基本概念才能更好理解代码。

二.开发环境
VC++ 6.0 比较老的一个环境，单文件测试。

三.主要记录
参考https://blog.csdn.net/huihuituboshu/article/details/79620056 设计。
但是发现代码还是有一些问题的，所以调试了一下，解解bug,包括以下方面：
1.原文并不是基于C语言写的，其中调用了vector.然后百度了一下，大概就是一个动态数组，考虑到程序中的动态添加节点信息问题，所以自己用链表实现。https://www.runoob.com/w3cnote/cpp-vector-container-analysis.html
2.添加孩子的时候，这个是有个逻辑问题的，如果第一个孩子已经存在，需要指针向后移一下，不然添加的兄弟节点就是父节点的兄弟节点了，实际应该是孩子的兄弟节点。

3.mytree_preorder_get_node() 原文这个函数这样写是有问题，结构体传出如果用形参的话要用二阶指针，因为一阶指针的地址是没有办法改变的。也可以return一阶指针。所以这个函数修改一下。

4.不足的地方，使用malloc申请的地方一定要记得释放，笔者是做嵌入式的，如果不释放就会内存泄漏，会带来很大的影响，所以也要添加树的释放。关于树的释放这个地方也是走了一点弯路的，所以记录一下，首先树的释放要后序释放，我一开始简单的想着就是递归遍历一样，先序释放，这里感谢https://blog.csdn.net/weixin_42889383/article/details/101274442
文中二叉树的销毁（本文的例子是树，二叉树是更特例一点的），但一个思路就是先把父节点释放了，那么就算是先把孩子节点指针记录下来，释放后也没有了，所以不能先序释放，要后序释放。其次释放的形参也要用二阶指针，如果不用二阶指针，当前节点指针是不能置空的，这样就造成了野指针。所以对文章中的函数也改写一下。

5.运行效果图

6.总结
代码一定要自己实际运行一下，不然出什么问题自己都不知道。另外感谢文中提及的各位前辈，仅当作技术交流

7.源码 main.c 单文件

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define Node_list 0#define MAX_NAME_LEN (50) //最大的名字长度
/*树结构体中数据成员*/
typedef struct _ElementType
{int id;char name[MAX_NAME_LEN];
}ElementType;/*树节点结构体*/
typedef struct _TreeNode
{int index;//结点的标识ElementType element;   //数据域struct _TreeNode *FirstChild; //第一个孩子指针	struct _TreeNode *NextSibling; //下一个兄弟 指针
}TreeNode;typedef struct _Index_vector
{int index;struct _Index_vector * next; 
}Index_vector;/*树结构体*/
typedef struct _CTree
{int num; //节点个数Index_vector *nodeIndexs;//存放所有的结点indexint rootIndex;//根节点的indexTreeNode *root; //根节点指针
}CTree;/*全局数据保存树信息*/
CTree g_tree;int add_index_node(Index_vector** p,int data)
{Index_vector * opreate =NULL;Index_vector * new_node =NULL;if(*p==NULL){*p=(Index_vector * )malloc(sizeof(Index_vector));if(*p==NULL){printf("malloc err  ***** add_index_node \r\n ");return -1;}else{printf("malloc head node success\r\n");(*p)->index=data;(*p)->next=NULL;return 0;}}else{//printf("head node has created \r\n");opreate=*p;new_node=(Index_vector * )malloc(sizeof(Index_vector));//printf("malloc ok\r\n");if(new_node==NULL){printf("malloc err  ***** add_index_node\r\n ");return -1;}else{//printf("malloc node success and add data is %d\r\n ",data);new_node->index=data;new_node->next=NULL;}while(opreate->next != NULL){opreate=opreate->next;}opreate->next=new_node;return 0;}
}int find_end_node(Index_vector* p)
{Index_vector * opreate =NULL;if(p == NULL){return 0;}else{opreate=p;while(opreate->next){opreate=opreate->next;}return opreate->index;}
}int free_index_list(Index_vector * p)
{Index_vector * opreate =NULL;Index_vector * free_node =NULL;if(p==NULL){return 0;}else{opreate=p;while(opreate){free_node=opreate;opreate=opreate->next;//printf("free node data is %d\r\n",free_node->index);free(free_node);}return 0;}
}int dump_index_list(Index_vector * p)
{Index_vector * opreate =NULL;if(p==NULL){return 0;}else{opreate=p;while(opreate){printf("dump node data is %d\r\n",opreate->index);opreate=opreate->next;}return 0;}
}/*
*    功能：检测结点的index是否正确
*	 入参：要检测的结点index
*	返回值：合法index返回true，不合法的index返回false
*/
static bool mytree_check_node_index(Index_vector * p,const int index)
{Index_vector * opreate =NULL;if(p==NULL){	printf("parent node address is NULL\r\n");return false;}else{opreate=p;while(opreate){if(opreate->index == index){printf("storage is %d and data is %d ******* done\r\n",opreate->index,index);return true;}else{printf("storage is %d and data is %d\r\n",opreate->index,index);opreate=opreate->next;}}return false;}
}/*
*    功能：获取指定的结点指针
*	 入参：父节点，比较参数index，出参nodeinfo
*	 返回值：NA
*/
void mytree_preorder_get_node(TreeNode *tree,	int index,   TreeNode **nodeinfo)
{if (NULL != tree){if (tree->index == index){*nodeinfo = tree;printf("mytree_preorder_get_node() tree is find and address is %p\r\n",nodeinfo);return;}mytree_preorder_get_node(tree->FirstChild, index, nodeinfo);mytree_preorder_get_node(tree->NextSibling, index, nodeinfo);}else{printf("mytree_preorder_get_node() tree is NULL\r\n");}return ;
}/*
*	功能：通过结点的index获取结点的指针信息
*	入参：查询结点的index
*	返回值：成功返回指向结点的指针，不成功返回NULL
*/
TreeNode *mytree_get_node_by_index(const int index)
{TreeNode *tmpNode = NULL;TreeNode *root = NULL;if(true != mytree_check_node_index(g_tree.nodeIndexs,index)) {printf("invalied index in get node by index\n");return NULL;}root = g_tree.root;//遍历当前的树，返回指定结点的指针printf("debug: root:%p index:%d\r\n",root,index);mytree_preorder_get_node(root, index, &tmpNode);printf("debug: tmpNode:%p\r\n",tmpNode);return tmpNode;
}/*
*	功能：设置一个孩子到树中
*	入参：parentIndex: 父节点的indexelement ：孩子结点的信息
*	返回值：插入成功返回0， 失败返回-1
*/
int mytree_set_child(int parentIndex, int index, ElementType element)
{TreeNode *parentNode = NULL;TreeNode *newNode = NULL;TreeNode *head = NULL;TreeNode *lastChild = NULL;//检测父节点是否有效if(true != mytree_check_node_index(g_tree.nodeIndexs,parentIndex)) {dump_index_list(g_tree.nodeIndexs);printf("invalied parent index ,index_num = %d,parent_index=%d\n",g_tree.num,parentIndex);return -1;}parentNode = mytree_get_node_by_index(parentIndex);if (NULL == parentNode){printf("parentNode is NULL\r\n");return -1;}//lastChild = mytree_get_last_child(parentNode);newNode = (TreeNode *)malloc(sizeof(TreeNode));if(NULL == newNode){printf("malloc tree node err\r\n");return -1;}memset(newNode, 0, sizeof(TreeNode));newNode->index = index;newNode->element.id = element.id;memcpy(newNode->element.name, element.name, MAX_NAME_LEN);add_index_node(&g_tree.nodeIndexs,index);g_tree.num++;//g_tree.nodeIndexs.push_back(index);//g_tree.num++;if (NULL == parentNode->FirstChild){parentNode->FirstChild = newNode;printf("add child node success and by firstchild and chile index is %d\r\n",newNode->index);return 0;}parentNode =parentNode->FirstChild;//需增加这一句if(NULL == parentNode->NextSibling){parentNode->NextSibling = newNode;printf("add child node success and by firstSibing and chile index is %d\r\n",newNode->index);return 0;}head = parentNode->NextSibling;while(head){lastChild = head;head = head->NextSibling;}printf("add child node success and by NextSibling and chile index is %d\r\n",newNode->index);lastChild->NextSibling = newNode;return 0;
}/*
*	功能：设置一个树的根节点
*	入参：  element ：根结点的信息
*	返回值：插入成功返回0， 失败返回-1
*/
int mytree_set_root( ElementType element,int root_index)
{//检测父节点是否有效TreeNode *newNode = NULL;newNode = (TreeNode *)malloc(sizeof(TreeNode));if (NULL == newNode){printf("malloc root node err\r\n");return -1; }memset(newNode, 0, sizeof(TreeNode));newNode->index = root_index;//根节点indexnewNode->FirstChild = NULL;newNode->NextSibling = NULL;newNode->element.id = element.id;memcpy(newNode->element.name, element.name, MAX_NAME_LEN);add_index_node(&g_tree.nodeIndexs,root_index);//g_tree.nodeIndexs.push_back(0);g_tree.num++;g_tree.root = newNode;return 0;
}/*
*	功能：初始化当前树
*	入参：无
*	返回值：无
*/
void mytree_init()
{g_tree.num = 0;g_tree.rootIndex = 0;g_tree.root = NULL;return;
}void mytree_preorder_visit(TreeNode *tree)
{if (NULL != tree){printf("tree index :%d\n", tree->index);printf("tree element id :%d\n", tree->element.id);printf("tree element id :%s\n", tree->element.name);mytree_preorder_visit(tree->FirstChild);mytree_preorder_visit(tree->NextSibling);}return ;
}void mytree_preorder_free(TreeNode **tree)
{printf("free node address is %p\r\n",tree);if(*tree == NULL)return;if((*tree)->FirstChild != NULL){mytree_preorder_free(&(*tree)->FirstChild);(*tree)->FirstChild = NULL;}if((*tree)->NextSibling != NULL){mytree_preorder_free(&(*tree)->NextSibling);(*tree)->NextSibling = NULL;}if(*tree != NULL){free(*tree);*tree = NULL;//printf("after free node address is %p\r\n",*tree);}return;
}void mytree_dump()
{// 各种遍历方式去访问树的各个结点if(g_tree.root==NULL){printf("tree is empty\r\n");}else{printf("tree root is %p\r\n",g_tree.root);}mytree_preorder_visit(g_tree.root);return ;
}void mytree_create()
{ElementType element;memset(&element, 0, sizeof(ElementType));//初始化一棵树mytree_init();//设置树的根节点element.id = 0;strncpy(element.name, "root", sizeof(element.name)-1);mytree_set_root(element,0);printf("set root tree node is ok\r\n");//设置叶子结点printf("start to set root-child-1 \r\n");memset(&element, 0, sizeof(ElementType));element.id = 1;strncpy(element.name, "root-child-1", sizeof(element.name)-1);mytree_set_child(0, 1, element);printf("set root-child-1 finish\r\n");memset(&element, 0, sizeof(ElementType));element.id = 2;strncpy(element.name, "root-child-2", sizeof(element.name)-1);mytree_set_child(0, 2, element);printf("set root-child-2 finish\r\n");memset(&element, 0, sizeof(ElementType));element.id = 3;strncpy(element.name, "root-child-3", sizeof(element.name)-1);mytree_set_child(0, 3, element);printf("set root-child-3 finish\r\n");memset(&element, 0, sizeof(ElementType));element.id = 4;strncpy(element.name, "root-child-1-1", sizeof(element.name)-1);mytree_set_child(1, 4, element);printf("set root-child-1-1 finish\r\n");memset(&element, 0, sizeof(ElementType));element.id = 5;strncpy(element.name, "root-child-1-2", sizeof(element.name)-1);mytree_set_child(1, 5, element);printf("set root-child-1-2 finish\r\n");return ;
}void mytree_free()
{printf("start to run mytree_free\r\n");mytree_preorder_free(&g_tree.root);printf("mytree_free run finish and root address is %p\r\n",g_tree.root);
}void main(void)
{int loop=0;#if (Node_list==1)printf("First test list node\r\n");for(loop;loop<100;loop++){if(add_index_node(&g_tree.nodeIndexs,loop)!=0){printf("add_index_node err!");break;}}printf("check %d is %d\r\n",123,mytree_check_node_index(g_tree.nodeIndexs,123));printf("End index is %d\r\n",find_end_node(g_tree.nodeIndexs));free_index_list(g_tree.nodeIndexs);
#endif//创建一棵树mytree_create();//打印树的结点mytree_dump();mytree_free();mytree_dump();
}

结束！