C语言实现二叉树（纯新手向）_c语言建立二叉树

目录

一、二叉树的基本概念

二、二叉树的初始化

三、释放二叉树

四、前中后序遍历二叉树

五、主函数和效果截图

六、拓展时间

---

这是我这段时间学习c语言二叉树的成果，希望对大家有所帮助，共同进步！

一、二叉树的基本概念

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。定义结构体可以这样设计

代码如下

//定义二叉树的结构
 
typedef struct binary_tree
 
{
 
    int data;   // 节点保存的数据
 
    binary_tree* left; // 定义左节点指针
 
    binary_tree* right; // 定义右节点指针
 
}node;

二、二叉树的初始化

malloc分配内存，然后初始化节点左右指针域为空，以及数据域为gain，最后*tree=temp把节点安装到树上，并且返回上一级；对于已经存在的树节点，我们需要往左右两分子扩展；当gain小于上一级的data，那就创建左子树并把值赋给该节点，当gain大于上一级的data，那就创建右子树并把值赋给该节点。

代码如下：

//初始化二叉树
 
void insert(node** tree, int gain) //指向指针变量的指针，结果是指针tree所指向的值
 
{
 
    node* temp = NULL;
 
    if (!(*tree)) //判断根节点是否存在
 
    {
 
        temp = (node*)malloc(sizeof(node));
 
        temp->left = temp->right = NULL; //左右节点制空
 
        temp->data = gain;
 
        *tree = temp;
 
        return;
 
    }
 
 
 
    if (gain < (*tree)->data) //判断是左子树
 
    {
 
        insert(&(*tree)->left, gain); //等价于 &((*tree)->left)，创建左子树
 
    }
 
    else if (gain > (*tree)->data) //判断是右子树
 
    {
 
        insert(&(*tree)->right, gain);//等价于 &((*tree)->right)，创建右子树
 
    }
 
}

三、释放二叉树

节点创建好了，注意是用malloc创建；因此，在堆中分配的内存需要手动释放，需要用到free函数与之对应；

//释放节点内存
 
void deltree(node* tree)
 
{
 
    if (tree)
 
    {
 
        deltree(tree->left);//先往左子树一直寻找
 
        deltree(tree->right);//再往右子树一直寻找
 
        free(tree); //找不到了free返回上一级
 
    }
 
}

四、前中后序遍历二叉树

递归方式实现前序遍历,先访问根节点,再前序遍历左子树,最后前序遍历右子树

递归方式实现中序遍历，先中序遍历左子树，再访问根节点，最后中序遍历右子树

递归方式实现后序遍历，先后序遍历左子树，再后序遍历右子树，最后访问根节点

代码如下：

//前序遍历
 
void leader(node* tree)
 
{
 
    if (tree)
 
    {
 
        printf("%d\n", tree->data);
 
        leader(tree->left);
 
        leader(tree->right);
 
    }
 
}
 
//中序遍历
 
void inorder(node* tree)
 
{
 
    if (tree) {
 
        inorder(tree->left);
 
        printf("%d\n", tree->data);
 
        inorder(tree->right);
 
    }
 
}
 
//后序遍历
 
void lastder(node* tree)
 
 {
 
    if (tree) {
 
        lastder(tree->left);
 
        lastder(tree->right);
 
        printf("%d\n", tree->data);
 
    }
 
}

五、主函数和效果截图

主函数里面给二叉树赋值，顺序为ABCDEFG。

那么前序输出ABDECFG

中序输出DBEAFCG

后续输出DEBFGCA

代码如下：

int main(void)
 
{
 
    node* root;
 
    //int i;
 
    root = NULL;
 
    //将值赋给二叉树，下面是满二叉树形式
 
    insert(&root, 9);
 
    insert(&root, 4);
 
    insert(&root, 15);
 
    insert(&root, 6);
 
    insert(&root, 12);
 
    insert(&root, 16);
 
    insert(&root, 2);
 
 
 
    printf("前序遍历\n");
 
    leader(root);
 
    printf("中序遍历\n");
 
    inorder(root);
 
    printf("后序遍历\n");
 
    lastder(root);
 
    //释放掉二叉树
 
    deltree(root);
 
}

效果截图

验证结果无误！

六、拓展时间

在进行遍历过程中，对遍历的顺序产生了疑问，程序采用了递归方式进行遍历，但是怎么进行遍历这个过程不是很清楚，那么将程序展开。

//先序遍历
 
void leader(node* tree)
 
{
 
    if (tree)
 
    {
 
        printf("根节点 %d\n", tree->data);
 
        if (tree->left)
 
        {
 
            printf("%d 作为 %d 的左子树\n", tree->left->data,tree->data);
 
            leader(tree->left);
 
        }
 
        if(tree->right)
 
        {
 
            printf("%d 作为 %d 的右子树\n", tree->right->data,tree->data);
 
            leader(tree->right);
 
        }
 
    }//如果tree为空则没有递归操作
 
}

在这里我将根节点和叶子节点结合起来，打印输出观察结果。

可以观察到，在进行递归的过程中，下一个叶子节点又作为根节点进行遍历，直到没有叶子节点为止，而遍历的顺序就是作为根节点的顺序。

源码链接在这：c语言实现二叉树（源码）_徐徐而闻的博客-CSDN博客

最后，希望大家动动手指，点赞收藏起来，这是对新人的最好支持！谢谢大家！！