欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C语言实现二叉树

程序员文章站 2022-05-06 23:03:44
二叉树的重要性就不用多说啦;   我以前也学习过,但是一直没有总结;   网上找到的例子,要么是理论一大堆,然后是伪代码实现;   要么是...
二叉树的重要性就不用多说啦;

 

我以前也学习过,但是一直没有总结;

 

网上找到的例子,要么是理论一大堆,然后是伪代码实现;

 

要么是复杂的代码,没有什么解释;

 

最终,还是靠FQ找到一些好的文章,参考地址我会在See Also部分给大家贴出来

 

 

 

Problem

 

假设我们要生成的二叉树如下图;

 

 

 

 

 

Solution

 

显然,我们需要在节点保存的数据只有一个整数;

 

struct binary_tree {

    int data    ;   // Data area

    //TODO

};

所以在结构体里面,我们的代码应该类似上面的写法;

 

通过观察我们还发现,每一个节点都指向左右两边(除了最后的叶子节点外);

 

因此,我们需要让它有两个指针域;

 

可能你会想到类似如下的写法;

 

struct binary_tree {

    int data    ;   // Data area

    void * left;

    void * right;

}; 

上面的定义格式似乎是正确的,但是类型好像并不是我们想要的;

 

例如:当left指向左边的子节点时,子节点应该也是一个包涵数据域的节点;

 

因此我们需要再定义一个与它本身相同的结构体;

 

struct binary_tree {

    int data    ;   // Data area

    struct binary_tree * left;

    struct binary_tree * right;

};

所以,我们会这样去定义它;

 

显然,这是一个递归定义;

 

如果我们要实例化一个节点,我们可以:

 

struct binary_tree * tree;

显然我们需要定义一个实例写那么长的类型名字,实在让人难受;

 

因此,我们可以这样;

 

typedef struct binary_tree node;

node * tree;

好啦!到此为止我们的数据域就定义好啦!你现在的代码应该是下面的样子啦;

 

 

struct binary_tree {
    int data    ;   // Data area
    binary_tree * left;
    binary_tree * right;
};  

typedef struct binary_tree node;

 

 

 

接下来我们需要把数据插入到对应的位置上;

 

我们希望树左边分支的的数据总是比树右边分支的要小;

 

 

void insert(node ** tree, int val) {
    node * temp = NULL;
    if(!(*tree)) {
        //TODO
        return ;
    }
    
    if (val < (*tree)->data) {
        //TODO
    }else if (val > (*tree)->data) {
        //TODO
    }
}

 

 

 

因此我们代码会像上面这样写;

 

第一个if语句判断这个树节点是否存在;

 

若是不存在,我们应该生成一个节点,然后添加到树上来;

 

第二个if-else呢,则是判断这个给定要存入的数据是大于当前节点的呢还是小于;

 

小于呢,存在左分支。大于存在右分支;

 

 

    if(!(*tree)) {
        temp = (node *)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return ;
    }
    
 

 

 

分析上面代码片段,我们发现temp的作用是临时变量正如其名;

 

malloc分配内存,然后初始化节点左右指针域为空,以及数据域为val;

 

最后*tree=temp 把节点安装到树上;

 

并且返回上一级;

 

对于已经存在的树节点,我们需要往左右两分子扩展;

 

因此我们的代码会是这样的;

 

 if (val < (*tree)->data) {

        insert(&(*tree)->left,val);

  }else if (val > (*tree)->data) {

        insert(&(*tree)->right,val);

  }

从代码中可以看出,只对小于和大于两个方向的数据进行操作;

 

你也许会考虑到万一等于呢。

 

注意,在这里应该是数据的唯一性有要求的,它类似于数学里的集合,不会有重复的;

 

它的这种特性对我们往后要写得单词统计程序非常有帮助;

 

那么这个函数的所有代码如下:

 

 

void insert(node ** tree, int val) {
    node * temp = NULL;
    if(!(*tree)) {
        temp = (node *)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return ;
    }
    
    if (val < (*tree)->data) {
        insert(&(*tree)->left,val);
    }else if (val > (*tree)->data) {
        insert(&(*tree)->right,val);
    }
}

 

 

 

节点创建好了,注意我们用malloc创建;

 

因此,我们是在堆中分配的内存,因此我们需要手动释放;

 

那显然需要用到free函数与之对应;

 

所以我们释放节点的函数应该是这样的;

 

void deltree(node * tree) {

    if(tree) {

        free(tree);

    }

}  

这样似乎也没有问题啦!但是仔细观察我们发现;

 

直接释放啦free就只是释放啦根节点;

 

就好比,我们去拔花生;我们只是简单的用剪刀把上面的叶子剪断啦;

 

没有想过把花生沿着根一直挖下去是不可能把所有花生弄出来的;

 

因此,我们需要这样做;

 

 

void deltree(node * tree) {
    if(tree) {
        deltree(tree->left);
        deltree(tree->right);
        free(tree);
    }
}

 

 

 

这样我们找到左边的根啦,又继续往左边找;

 

找不到啦,就往右边找;

 

再找不到啦,就执行到free释放节点然后返回上一级;

 

好啦!树也有函数建啦,也有办法“砍”啦!

 

接下来是怎么展示我们的树啦;

 

树的遍历有三种;

 

前,中,后;

 

void print_preorder(node * tree) {

    if(tree) {

        //TODO

 

    }

}  

首先我们需要判断tree是否空;

 

要是空的,我们就没有必要看里面还有什么数据啦;

 

 

void print_preorder(node * tree) {
    if(tree) {
        printf("%d\n",tree->data);
        print_preorder(tree->left);
        print_preorder(tree->right);
    }
}

void print_inorder(node * tree) {
    if(tree) {
        print_inorder(tree->left);
        printf("%d\n",tree->data);
        print_inorder(tree->right);
    }
}

void print_postorder(node * tree) {
    if(tree) {
        print_postorder(tree->left);
        print_postorder(tree->right);
        printf("%d\n",tree->data);
    }
}

 

x

 

同样的我们把中序和后序写出来;

 

 

void print_preorder(node * tree) {
    if(tree) {
        printf("%d\n",tree->data);
        print_preorder(tree->left);
        print_preorder(tree->right);
    }
}

void print_inorder(node * tree) {
    if(tree) {
        print_inorder(tree->left);
        printf("%d\n",tree->data);
        print_inorder(tree->right);
    }
}

void print_postorder(node * tree) {
    if(tree) {
        print_postorder(tree->left);
        print_postorder(tree->right);
        printf("%d\n",tree->data);
    }
}

 

 

 

好啦!该有的函数都有啦;

 

我们该写测试函数啦;

 

 

 

 

 

 

int main(void)
{
    node * root;
    node * tmp;
    //int i;

    root = NULL;
    /* Inserting nodes into tree */
    insert(&root,9);
    insert(&root,4);
    insert(&root,15);
    insert(&root,6);
    insert(&root,12);
    insert(&root,17);
    insert(&root,2);

    printf("Pre Order Display\n");
    print_preorder(root);

    printf("In Order Display\n");
    print_inorder(root);

    printf("Post Order Display\n");
    print_postorder(root);


    /* Deleting all nodes of tree */
    deltree(root);
}

 

 

运行结果如下:

 

 

二叉树的重要性就不用多说啦;

我以前也学习过,但是一直没有总结;

网上找到的例子,要么是理论一大堆,然后是伪代码实现;

要么是复杂的代码,没有什么解释;

最终,还是靠FQ找到一些好的文章,参考地址我会在See Also部分给大家贴出来

 

Problem

假设我们要生成的二叉树如下图;



 

Solution

显然,我们需要在节点保存的数据只有一个整数;

struct binary_tree {
    int data    ;   // Data area
    //TODO
};
所以在结构体里面,我们的代码应该类似上面的写法;

通过观察我们还发现,每一个节点都指向左右两边(除了最后的叶子节点外);

因此,我们需要让它有两个指针域;

可能你会想到类似如下的写法;

struct binary_tree {
    int data    ;   // Data area
    void * left;
    void * right;
}; 
上面的定义格式似乎是正确的,但是类型好像并不是我们想要的;

例如:当left指向左边的子节点时,子节点应该也是一个包涵数据域的节点;

因此我们需要再定义一个与它本身相同的结构体;

struct binary_tree {
    int data    ;   // Data area
    struct binary_tree * left;
    struct binary_tree * right;
};
所以,我们会这样去定义它;

显然,这是一个递归定义;

如果我们要实例化一个节点,我们可以:

struct binary_tree * tree;
显然我们需要定义一个实例写那么长的类型名字,实在让人难受;

因此,我们可以这样;

typedef struct binary_tree node;
node * tree;
好啦!到此为止我们的数据域就定义好啦!你现在的代码应该是下面的样子啦;

复制代码
struct binary_tree {
    int data    ;   // Data area
    binary_tree * left;
    binary_tree * right;
};  

typedef struct binary_tree node;
复制代码
接下来我们需要把数据插入到对应的位置上;

我们希望树左边分支的的数据总是比树右边分支的要小;

至于为什么我们暂时不解释;

复制代码
void insert(node ** tree, int val) {
    node * temp = NULL;
    if(!(*tree)) {
        //TODO
        return ;
    }
    
    if (val < (*tree)->data) {
        //TODO
    }else if (val > (*tree)->data) {
        //TODO
    }
}
复制代码
因此我们代码会像上面这样写;

第一个if语句判断这个树节点是否存在;

若是不存在,我们应该生成一个节点,然后添加到树上来;

第二个if-else呢,则是判断这个给定要存入的数据是大于当前节点的呢还是小于;

小于呢,存在左分支。大于存在右分支;

复制代码
    if(!(*tree)) {
        temp = (node *)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return ;
    }
    
复制代码
分析上面代码片段,我们发现temp的作用是临时变量正如其名;

malloc分配内存,然后初始化节点左右指针域为空,以及数据域为val;

最后*tree=temp 把节点安装到树上;

并且返回上一级;

对于已经存在的树节点,我们需要往左右两分子扩展;

因此我们的代码会是这样的;

 if (val < (*tree)->data) {
        insert(&(*tree)->left,val);
  }else if (val > (*tree)->data) {
        insert(&(*tree)->right,val);
  }
从代码中可以看出,只对小于和大于两个方向的数据进行操作;

你也许会考虑到万一等于呢。

注意,在这里应该是数据的唯一性有要求的,它类似于数学里的集合,不会有重复的;

它的这种特性对我们往后要写得单词统计程序非常有帮助;

那么这个函数的所有代码如下:

复制代码
void insert(node ** tree, int val) {
    node * temp = NULL;
    if(!(*tree)) {
        temp = (node *)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return ;
    }
    
    if (val < (*tree)->data) {
        insert(&(*tree)->left,val);
    }else if (val > (*tree)->data) {
        insert(&(*tree)->right,val);
    }
}
复制代码
节点创建好了,注意我们用malloc创建;

因此,我们是在堆中分配的内存,因此我们需要手动释放;

那显然需要用到free函数与之对应;

所以我们释放节点的函数应该是这样的;

void deltree(node * tree) {
    if(tree) {
        free(tree);
    }
}  
这样似乎也没有问题啦!但是仔细观察我们发现;

直接释放啦free就只是释放啦根节点;

就好比,我们去拔花生;我们只是简单的用剪刀把上面的叶子剪断啦;

没有想过把花生沿着根一直挖下去是不可能把所有花生弄出来的;

因此,我们需要这样做;

复制代码
void deltree(node * tree) {
    if(tree) {
        deltree(tree->left);
        deltree(tree->right);
        free(tree);
    }
}
复制代码
这样我们找到左边的根啦,又继续往左边找;

找不到啦,就往右边找;

再找不到啦,就执行到free释放节点然后返回上一级;

好啦!树也有函数建啦,也有办法“砍”啦!

接下来是怎么展示我们的树啦;

树的遍历有三种;

前,中,后;

void print_preorder(node * tree) {
    if(tree) {
        //TODO

    }
}  
首先我们需要判断tree是否空;

要是空的,我们就没有必要看里面还有什么数据啦;

复制代码
void print_preorder(node * tree) {
    if(tree) {
        printf("%d\n",tree->data);
        print_preorder(tree->left);
        print_preorder(tree->right);
    }
}
复制代码
同样的我们把中序和后序写出来;

复制代码
void print_preorder(node * tree) {
    if(tree) {
        printf("%d\n",tree->data);
        print_preorder(tree->left);
        print_preorder(tree->right);
    }
}

void print_inorder(node * tree) {
    if(tree) {
        print_inorder(tree->left);
        printf("%d\n",tree->data);
        print_inorder(tree->right);
    }
}

void print_postorder(node * tree) {
    if(tree) {
        print_postorder(tree->left);
        print_postorder(tree->right);
        printf("%d\n",tree->data);
    }
}
复制代码
好啦!该有的函数都有啦;

我们该写测试函数啦;

 

 

复制代码
int main(void)
{
    node * root;
    node * tmp;
    //int i;

    root = NULL;
    /* Inserting nodes into tree */
    insert(&root,9);
    insert(&root,4);
    insert(&root,15);
    insert(&root,6);
    insert(&root,12);
    insert(&root,17);
    insert(&root,2);

    printf("Pre Order Display\n");
    print_preorder(root);

    printf("In Order Display\n");
    print_inorder(root);

    printf("Post Order Display\n");
    print_postorder(root);


    /* Deleting all nodes of tree */
    deltree(root);
}
复制代码
运行结果如下:

复制代码
Pre Order Display
9
4
2
6
15
12
17
In Order Display
2
4
6
9
12
15
17
Post Order Display
2
6
4
12
17
15
9
复制代码
 

Discussion

 然后这个例子似乎太简单了!它没有对树进行查询的函数;

也没有树的高度进行测量;

但是,它的简洁是为了更加容易理解;

可是呢!太简洁了,以至于我们都不知道为什么要把数据弄成树形结构;

为什么,难道线性结构的数据还不能解决我们身边的问题吗?

这个问题,不知道大家有没有问过自己。反正我以前经常问自己;

那么,为了让大家理解存在树形结构的数据的必要性;

我们,设想要统计C语言的关键字在代码中出现的频率;

我们会怎么做呢??(这个问题我会在另一篇文章讲解)

 

x

 

 

 

Discussion

 

 然后这个例子似乎太简单了!它没有对树进行查询的函数;

 

也没有树的高度进行测量;

 

但是,它的简洁是为了更加容易理解;

 

可是呢!太简洁了,以至于我们都不知道为什么要把数据弄成树形结构;

 

为什么,难道线性结构的数据还不能解决我们身边的问题吗?

 

这个问题,不知道大家有没有问过自己。反正我以前经常问自己;

 

那么,为了让大家理解存在树形结构的数据的必要性;

 

我们,设想要统计C语言的关键字在代码中出现的频率;

 

我们会怎么做呢??(这个问题我会在另一篇文章讲解)