1. 树

1. 树: 除了根节点和叶子节点外，只有唯一前驱，但可以有多个后继，根节点没有前驱，叶子节点没有后继，所以树没有环，子树之间也不会相交。是数据结构中一种极具特点的逻辑结构。

2. 二叉树：每个节点最多有两个后继节点（子节点）的树，通常称作左子节点、右子节点，也叫左孩子、右孩子。二叉树运用广泛，作用也众多，本文重点介绍二叉树在C语言中的运用。

3. 二叉树的每个节点由左孩子指针（*lchild）、右孩子指针（*rchild）、数据域组成，所以我们选择用链式结构能更好的实现树的结构。

4. 现在我们准备三个文件：tree.c、tree.h、main.c。

5. 请大家多看注释可帮助理解运用！

2. 二叉树的创建

（1）tree.h

1. 在头文件中，我们定义一个节点结构体，里面包含了左、右孩子节点以及数据域（这里我们用节点编号来充当节点携带的数据，默认以根节点为1，根节点的左孩子为2，右孩子为3......依次编号），具体可参考下图。

2. 再将创建与回收二叉树的函数定义写入。

#ifndef _tree_h_
#define _tree_h_
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int data_t;
//二叉树节点结构体
typedef struct node{
    data_t data; //数据域：节点编号
    struct node *lchild; //左孩子
    struct node *rchild; //右孩子
}tree_node;

//创建二叉树
tree_node *tree_create(int i, int n); //编号、总结点数

//回收二叉树
void tree_destroy(tree_node *root);

#endif

（2）tree.c

1. 封装创建与回收二叉树的函数功能。

2. 因为二叉树根节点的左、右孩子又会作为根节点成为一个二叉树，所以在二叉树的创建与回收功能实现时多次运用递归的思想。递归虽然代码书写简单，但相对不是那么容易理解，同学们可多看注释寻找思路。

#include "tree.h"

//创建树
tree_node *tree_create(int i, int n) //编号、总结点数
{
    //为根节点分配空间
    tree_node *root = (tree_node *)malloc(sizeof(tree_node));
    if (NULL == root)
    {
        printf("malloc failed!\n");
        return NULL;
    }
    //为开辟的空间填充0
    memset(root, 0, sizeof(tree_node));
    //数据域为编号
    root->data = i;
    //为左孩子赋值
    if(2*i <= n)
        //把每个左孩子当作根节点，再为左孩子的左孩子赋值（递归）
        root->lchild = tree_create(2*i, n);
    else root->lchild = NULL;
    //为右孩子赋值
    if(2*i+1 <= n)
        //把每个右孩子当作根节点，再为右孩子的右孩子赋值（递归）
        root->rchild = tree_create(2*i+1, n);
    else root->rchild = NULL;

    return root;
}

//回收二叉树
void tree_destroy(tree_node *root)
{
    if (NULL == root)
        return;
    tree_destroy(root->lchild);
    tree_destroy(root->rchild);
    free(root);
}

3. 二叉树的先序、中序、后序、层次遍历

 二叉树的遍历是基础、常见且重要的二叉树知识点，让我们来看看C语言是怎么实现遍历功能的。

（1）tree.h

在头文件中加入先序、中序、后序、层次遍历的函数声明。

//先序遍历
void tree_preorder(tree_node *root);
//中序遍历
void tree_inorder(tree_node *root);
//后序遍历
void tree_postorder(tree_node *root);
//层次遍历
void tree_levelorder(tree_node *root);

（2）tree.c

封装先序、中序、后序、层次遍历的函数功能。

由于二叉树的递归性质，遍历算法也是递归的。三种基本的遍历算法如下 ：

1. 先序遍历（根左右）: 先访问树根，再访问左子树，最后访问右子树；

2. 中序遍历（左根右）: 先访问左子树，再访问树根，最后访问右子树；

3. 后序遍历（左右根）: 先访问左子树，再访问右子树，最后访问树根；

4. 层次遍历：按树的每一层进行遍历，使用队列实现。

//先序遍历
void tree_preorder(tree_node *root)
{
    //判断根节点左右孩子是否为空
    if(NULL == root)
        return;
    
    printf("%-3d",root->data); //不为空则打印数据域
   
    tree_preorder(root->lchild); //再以左孩子为根节点递归遍历
   
    tree_preorder(root->rchild);  //最后以右孩子为根节点递归遍历
}

//中序遍历
void tree_inorder(tree_node *root)
{
    //判断根节点左右孩子是否为空
    if(NULL == root)
        return;
    tree_inorder(root->lchild); //遍历左孩子
    printf("%-3d",root->data); //遍历根节点
    tree_inorder(root->rchild); //遍历右孩子
}

//后序遍历
void tree_postorder(tree_node *root)
{
    //判断根节点左右孩子是否为空
    if(NULL == root)
        return;
    tree_postorder(root->lchild); //遍历左孩子
    tree_postorder(root->rchild); //遍历右孩子
    printf("%-3d",root->data); //遍历根节点
}

//层次遍历
void tree_levelorder(tree_node *root)
{
    //创建队列
    tree_node *queue[20] = {NULL};
    int front, rear; //队头队尾指针
    front = rear = 0; //初始化头尾指针
    //把根节点加入队列
    queue[rear] = root; 
    rear += 1;
    //循环判断队列是否为空，为空则跳出循环
    while(front != rear)
    {
        //让第一个节点p出队
        tree_node *p = queue[front];
        front += 1;
        //访问p数据域
        printf("%-3d", p->data);
        //如果p有左右孩子，则让左右孩子入队
        if(NULL != p->lchild)
        {
            queue[rear] = p->lchild;
            rear += 1;
        }
        if(NULL != p->rchild)
        {
            queue[rear] = p->rchild;
            rear += 1;
        }
    }

}

4. 在主函数中验证树的遍历功能

（1）main.c

#include "tree.h"

int main(int argc, char *argv[])
{ 
    //创建二叉树
    printf("创建一棵十个节点的二叉树\n");
    tree_node *root = tree_create(1,10);
    if(NULL == root)
    {
        printf("malloc failed!\n");
        return -1;
    }
    //遍历
    printf("先序遍历：\n");
    tree_preorder(root);
    puts("");

    printf("中序遍历：\n");
    tree_inorder(root);
    puts("");

    printf("后序遍历：\n");
    tree_postorder(root);
    puts("");

    printf("层次遍历：\n");
    tree_levelorder(root);
    puts("");

    //回收二叉树
    tree_destroy(root);

    return 0;
} 

（2）运行结果展示

创建一棵十个节点的二叉树
先序遍历：
1  2  4  8  9  5  10 3  6  7  
中序遍历：
8  4  9  2  10 5  1  6  3  7  
后序遍历：
8  9  4  10 5  2  6  7  3  1  
层次遍历：
1  2  3  4  5  6  7  8  9  10 

5. 总结

1. 二叉树是树中很 “ 严谨 ” 的类型，它们最多有两个孩子，且必须严格区分谁是左孩子，谁是右孩子，是很特别的一类树。

2. 树的应用场景也很广泛，比如我们的文件系统就采用的是树结构，而二叉树也有很多作用，比如搜索算法、排序算法等。

3. 有一种很出名的二叉树——哈夫曼树，又称最优二叉树，是带权路径长度最短的树，可用来构造最优编码，用于信息传输、数据压缩等方面，是一种应用广泛的二叉树，许多考试都喜欢出关于哈夫曼树的题目，建议大家去了解一下这个特别的二叉树。

4. 除了树形结构，其他数据逻辑结构，顺序表、链表、栈、图等也各有各的特点，对它们感兴趣的同学，欢迎浏览主页其他文章！

感谢观看！如有疑问欢迎提出！

  ----香菜小猫祝这位uu天天开心----