C语言实现二叉树
我以前也学习过,但是一直没有总结;
网上找到的例子,要么是理论一大堆,然后是伪代码实现;
要么是复杂的代码,没有什么解释;
最终,还是靠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语言的关键字在代码中出现的频率;
我们会怎么做呢??(这个问题我会在另一篇文章讲解)