之前写了好多篇文章关于数据结构的，既然讲到了数据结构，那么就必须要说一下树，树这个数据结构使用范围非常广，应用前景广阔。

关联文章：

这篇文章主要是讲解最简单的一个树的构成，并用代码实现。

声明节点结构体

/*树节点*/ typedef struct node{
     	int data; 	struct node * left; /*节点左边的树枝*/ 	struct node * right;/*节点右边的树枝*/ }Node;

data 是这个节点的数据，left是这个节点指向左边节点的指针，right 是指向右边节点的指针。

声明根节点结构体

/*树根*/ typedef struct tree{
     	Node * root; }Tree;

根节点也是一个节点，只不过这个节点代表了这棵树，这个节点存在，就代表这棵树没有死。

定义一个根节点

Tree tree;     tree.root = NULL;/*创建一个空树*/

像节点插入一个数据

我们现在模拟一下，插入一个数据 5

/*插入函数 向一个树里面插入数据*/ void insert(Tree* tree, int value) {
     	/*创建一个节点*/     Node* node=(Node*)malloc(sizeof(Node));     node->data = value;     node->left = NULL;     node->right = NULL;         /*判断树是不是空树*/     if (tree->root == NULL)     {
             tree->root = node;     }     //....... }

我们会先判断 这个树是不是空的，如果是空的，就把这树根指向这个 node 节点。

我们再插入一个数据 4

因为 4 小于 5，所以我们需要把 4插入到 5 的左边节点去。

insert(&tree, temp);

所以就变成这样

我们再插入一个数据 3

因为 3 小于 4，那我们就再插入到4的left节点。

如果我们再插入一个 5呢？

大于等于 当前节点的，都进入right节点，所以，插入 5 会变成这样。

遍历一棵树

遍历一棵树的方法有很多，前序遍历，中序遍历，后序遍历，我这里就不说了，无非就是递归判断节点是否为空，我这里使用的是中序遍历。

/*  遍历一整颗树  中序遍历:先左后根再右  */ void traverse(Node* node) {
         if(node != NULL)     {
             traverse(node->left);         printf("%d ",node->data);         traverse(node->right);     } }

traverse(node->left); 递归扫描所有的左子树节点 traverse(node->right); 递归扫描所有的右子树节点

销毁一棵树

既然我们是通过 malloc 来创建一棵树的，那么使用完后，肯定需要释放内存，要不然内存就会一直消耗占用。

/*销毁一棵树*/ void distory_tree(Node* node) {
     	 	if(node != NULL) 	{
     		distory_tree(node->left);         distory_tree(node->right);         printf("free node:%d\n",node->data); 		free(node); 		node = NULL; 	} }

使用递归很爽啊，一直使用一直爽啊。哈哈，那就一直使用递归好了。

完整代码

#include "stdio.h" #include "stdlib.h" /*树节点*/ typedef struct node{
     	int data; 	struct node * left; /*节点左边的树枝*/ 	struct node * right;/*节点右边的树枝*/ }Node; /*树根*/ typedef struct tree{
     	Node * root; }Tree; /*插入函数 向一个树里面插入数据*/ void insert(Tree* tree, int value) {
     	/*创建一个节点*/     Node* node=(Node*)malloc(sizeof(Node));     node->data = value;     node->left = NULL;     node->right = NULL;         /*判断树是不是空树*/     if (tree->root == NULL)     {
             tree->root = node;     }     else /*不是空树*/ 	{
             Node* temp = tree->root;/*从树根开始*/         while (temp != NULL)         {
                 if(value < temp->data)/*小于就进左儿子*/             {
                     if(temp->left == NULL)                 {
                         temp->left = node;                     return;                 }                 else /*继续判断*/ 				{
                         temp = temp->left;                 }             }             else /*否则进右儿子*/ 			{
                      if(temp->right == NULL)                 {
                         temp->right = node;                     return;                 }                 else /*继续判断*/ 				{
                         temp = temp->right;                 }             }         }     } } /*  遍历一整颗树  中序遍历:先左后根再右  */ void traverse(Node* node) {
         if(node != NULL)     {
             traverse(node->left);         printf("%d ",node->data);         traverse(node->right);     } } /*销毁一棵树*/ void distory_tree(Node* node) {
     	 	if(node != NULL) 	{
     		distory_tree(node->left);         distory_tree(node->right);         printf("free node:%d\n",node->data); 		free(node); 		node = NULL; 	} } /*主函数*/ int main() {
     	int i = 0; 	Tree tree;     tree.root = NULL;/*创建一个空树*/     int n;     printf("input total num:\n");     /*输入n个数并创建这个树*/     scanf("%d",&n);     for(i = 0; i < n; i++)     {
             int temp;         scanf("%d",&temp);         insert(&tree, temp);     }     /*遍历整个树*/     traverse(tree.root); 	 	/*销毁一棵树*/ 	distory_tree(tree.root); 	return 0; }

总结

数据结构里的树是一个难点和重点，变化也非常多，我们安卓系统里面的跨进程间通信，使用的binder，底层就是有使用到红黑树，大家如果通过这个小例子知道树这个概念，以后遇到就不至于一愣一愣的。

好吧，就说这么多，文章有问题的，欢迎批评指正，我们要在批评与指正中成长，觉得不错的，感谢转发和再看。

共勉~