五分钟C语言实现数据结构 之 二叉树链式存储
五分钟C语言实现数据结构 之 二叉树链式存储
Python编程爱好者
发布于 2020-09-08 15:17:27
发布于 2020-09-08 15:17:27
五分钟C语言实现常见数据结构 之 二叉树链式存储
引例
在开始的时候，我们会采用数组的形式来定义树的数据结构，但是一定会造成空间的浪费...
举例来说「灰色底代表被浪费的空间」
很明显的可以看到，如果采用数组连续存储的话，会有大量的空间浪费，可能有的同学感觉浪费的也不是太多。那么咱们再增加一个看看:
在这里只增加了一个节点。但是由于树本身的原因，却要浪费8个单元格，仅仅一个节点确实浪费了大量的存储空间。
由于这种情况的发生，所以，经常也会用链式存储来进行树形的设计
树的链式设计
要点：给每一个节点增加两个指针节点，指向孩子节点，避免空间的浪费
这样来看是不是就避免了某些空间的浪费
然后用这样的实现方式来用图表示上述的树形结构
很清楚的采用链式结构来说，节省了很多的空间。
可能还有同学疑问，这样不会使得增加了指针节点的空间存储吗？
是有这部分开销，但是在日常生活中，比起指针节点空间开销，数组连续存储会占用更多的空间。感兴趣的同学可以自己画图实现看看。
伪代码描述
typedef struct BinTNode{
ElementType data; //数据储存
struct BinTNode * left; //左指针
struct BinTNode * right; //右指针
}BinTNode, *BinTree;C代码实现
下面代码是按照上述的树形结构整理的
# include <stdio.h>
# include <stdlib.h>
# define ElementType char
typedef struct BinTNode{
ElementType data;
struct BinTNode * left;
struct BinTNode * right;
} BinTNode, *BinTree;
BinTNode * CreateBinTree(BinTNode *T){
T=(BinTNode*)malloc(sizeof(BinTNode));
T->data='A';
T->left=(BinTNode*)malloc(sizeof(BinTNode));
T->left->data='B';
T->right=(BinTNode*)malloc(sizeof(BinTNode));
T->right->data='C';
T->right->left=NULL;
T->right->right=NULL;
T->left->left=(BinTNode*)malloc(sizeof(BinTNode));
T->left->left->data='D';
T->left->right=NULL;
T->left->left->left=NULL;
T->left->left->right=(BinTNode*)malloc(sizeof(BinTNode));
T->left->left->right->data='I';
T->left->left->right->left=NULL;
T->left->left->right->right=NULL;
return T;
}
int main() {
BinTNode * Tree;
Tree = CreateBinTree(Tree);
printf("%c\n",Tree->left->left->data);
return 0;
}很多同学说在学完了一些数据结构之后，说是实现起来难，确实课本和代码实现起来是有一点距离的
多看多理解！慢慢积累一定会有思想层面的改变!
作者：Johngo
图片：凡科快图
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-04-18，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录