[数据结构]C语言二叉树的实现

树和图是数据结构中比较麻烦的东西,里面涉及的概念比较多,也最有用, 就比如一般树广泛应用于人工智能的博弈上,而基于图的广度优先和深度优先搜索也广泛应用于人工智能寻路上面

首先我们要把树进行分类: >一般树:任意节点子节点个数不限

>二叉树:任意节点子节点个数大于等于0,小于等于2,也即是说0<=n<=2

>森林:N个不相交的树的集合

在讲下面之前你有必要搞懂一些概念,这里我引入一张图片并试图说明这些概念:

根:我们习惯吧最上面的A节点表示为root(根),这个概念可以与生活联系,只不过这里的根是在最上面,

深度:也就是树的层数,比如上图有4层,所以深度为4

节点,就是每一个矩形,树是由节点组成的,因此根也叫做根节点

子节点/孩纸:就是一个节点的下面离它最近的的节点,比如A的子节点是BC而不是BCDEFG,E的子节点是G,G没有子节点

父节点/父亲:这里就是倒置了一下,比如G的父节点是E,EF的父节点是C,BC的父节点是A

堂兄弟:D的堂兄弟是EF

根据上面的概念和上面对树的定义你应该知道这是一个二叉树。

由于二叉树的广泛应用与研究,所以这里我们讨论二叉树,其实森林和一般树都可以转化为一个一般树,转换原则就是把一个节点的第一个子节点变成二叉树的左节点,然后其他堂兄弟就是右节点,这句话不指望你能看懂,因为我都感觉没有表述清楚,我认为这个视频讲得比较好http://pan.baidu.com/s/1i3yYd2t

然后我们再细分二叉树,它分为:

空二叉树:就是什么都没有

满二叉树:每个节点都有两个子节点

完全二叉树:把一颗完全二叉树的最后一层从右往左删除一些节点得到的就是完全二叉树

二叉树也分顺序存储和链式存储,因为顺序存储比较浪费内存,所以这里考虑用链式存储实现

struct node{
	char data;
	struct node *lchild;
	struct node *rchild;
};

这样我们就定义了一个简单的二叉树节点,它包含一个数据域和两个指针域,两个指针域分别用来指向左孩纸(左节点)和右孩纸(右节点),然后再看看这图,我们接下来将定义一个如图所示的二叉树:

struct node *create_binary_tree(){
	struct node *root;
	struct node *a=new node,*b=new node,*c=new node,*d=new node,*e=new node,*f=new node,*g=new node;
	a->data='A';
	b->data='B';
	c->data='C';
	d->data='D';
	e->data='E';
	f->data='F';
	g->data='G';
	a->lchild=b;
	a->rchild=c;
	b->lchild=d;
	b->rchild=NULL;	
	c->lchild=e;
	c->rchild=f;
	d->lchild=NULL;
	d->rchild=NULL;
	e->lchild=g;
	e->rchild=NULL;
	f->lchild=NULL;
	f->rchild=NULL;
	g->lchild=NULL;
	g->rchild=NULL;
	root=a;
	return root;
}

上面代码非常简单,结合上图可以很容易理解

接下来讲的就是重点了:二叉树的遍历

二叉树的遍历分为前序遍历,中序遍历,后序遍历,层序遍历

你得用心才能看懂下面的内容,还是再次建议看一下这个视频http://pan.baidu.com/s/1i3yYd2t

首先讲讲最简单的层序遍历,顾名思义,从上至下一层一层的遍历,所以遍历顺序就是ABCDEFG

然后是前序遍历,前序遍历的原则就是先遍历根节点(注意这里的根节点是相对意义上的),然后再遍历左节点,然后遍历右节点,所以遍历顺序是ABDCEGF

接下来就是中序遍历,中序遍历就是先遍历左节点,然后遍历根,最后右节点,所以遍历顺序就是DBAGECF

最后是后序遍历,后序遍历是先遍历左节点然后右节点最后根,所以遍历顺序是DBGEFCA

这里看似很麻烦,但是如果我们用代码写其实很简单,主要运用了递归的思想,代码如下:

//ABDCEGF前序
void PreTraversal(struct node *root){
	if(root!=NULL){
		std::cout<<root->data;
		PreTraversal(root->lchild);
		PreTraversal(root->rchild);
	}
}
//DBAGECF中序

void InTraversal(struct node *root){
	if(root!=NULL){
		InTraversal(root->lchild);
		std::cout<<root->data;
		InTraversal(root->rchild);
	}
}

void insert(struct node *root){
}

//DBGEFCA后序
void NexTraversal(struct node *root){
	if(root!=NULL){
		NexTraversal(root->lchild);
		NexTraversal(root->rchild);
		std::cout<<root->data;
	}
}

到这里就结束了,我们没有讲动态二叉树的创建,这里提供一份资料以供参考[1]

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java爬坑系列

【Java入门提高篇】Day24 Java容器类详解(七)HashMap源码分析(下)

13330
来自专栏于晓飞的专栏

Java 容器---实现

然而,之前在开发中使用仅仅是容器的一小部分。这次从源码的角度进行深入的理解,一点总结分享给大家。

12510
来自专栏互扯程序

Java集合深度解析之TreeMap

红黑树简介 TreeMap是基于红黑树实现的,这里只对红黑树做个简单的介绍,红黑树是一种特殊的二叉排序树,红黑树通过一些限制,使其不会出现二叉树排序树中极端的一...

40850
来自专栏用户画像

4.5.3 哈弗曼树(Huffman)树和哈弗曼编码

树中结点被赋予一个表示某种意义的数值,称为该结点的权。从树根结点到任意结点的路径长度(经过的边数)与该结点上权值的乘积称为该结点的带权路径长度。树中所有叶结点的...

8210
来自专栏数据结构与算法

洛谷P2827 蚯蚓(单调队列)

有$m$个时间,每个时间点找出长度最大的蚯蚓,把它切成两段,分别为$a[i] * p$和$a[i] - a[i] * p$,除这两段外其他的长度都加一个定值$q...

7720
来自专栏mathor

线性表(一)

12320
来自专栏算法channel

二叉树非递归版的后序遍历算法

本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有,分而治之,搜索,动态规划,回溯,贪心等,结合这些思想再去思考如今很火的大数据,云计算和机器学习,...

434100
来自专栏java小白

Jdk7HashMap源码分析

21750
来自专栏Java爬坑系列

【Java入门提高篇】Day26 Java容器类详解(八)HashSet源码分析

  前面花了好几篇的篇幅把HashMap里里外外说了个遍,大家可能对于源码分析篇已经讳莫如深了。

11840
来自专栏数据结构与算法

约瑟夫环 队列+链表

设有n个人依次围成一圈,从第1个人开始报数,数到第m个人出列,然后从出列的下一个人开始报数,数到第m个人又出列,…,如此反复到所有的人全部出列为止。设n个人的编...

40270

扫码关注云+社区

领取腾讯云代金券