二叉树就是这么简单

作者: | 更新日期:

基础的数据结构分享玩了

本文首发于公众号:天空的代码世界,微信号:tiankonguse
原文地址:https://mp.weixin.qq.com/s/Q0MgdrnJE4-U4PaPCrn5MQ

一、背景

本来之前写过《数组》、《链表》、《队列与栈》、《哈希》、《二分查找》,后面就开始写树相关的文章了。

结果上篇文章没介绍《二叉树》,直接介绍《二叉搜索树》了。
今天把《二叉树》的知识补上。

二、基础知识

树是一种经常用到的数据结构,用来模拟具有树状结构性质的数据集合。

树里的每一个节点有一个根植和一个包含所有子节点的列表。

二叉树是一种更为典型的树树状结构。
如它名字所描述的那样,二叉树是每个节点最多有两个子树的树结构,通常子树被称作“左子树”和“右子树”。

三、树的遍历

二叉树一般有三种遍历:前序遍历、中序遍历、后续遍历。

前序遍历首先访问根节点,然后遍历左子树,最后遍历右子树。
中序遍历是先遍历左子树,然后访问根节点,然后遍历右子树。
后序遍历是先遍历左子树,然后遍历右子树,最后访问树的根节点。

通常来说,使用递归进行这三种遍历都是非常简单的事情。
而使用迭代的方法实现这三种遍历,就需要使用自己维护栈这个数据结构了。

二叉树的前序遍历相对还算简单,对于当前树根节点,直接输出答案。
代码如下。

而对于中序和后续遍历,则存在一个问题:当前树的根节点怎么保存。
出栈的时候,我们怎么知道这是一个尚未处理的子树,还是已经处理的子树。

如果可以修改树的节点值,那处理过的节点置为空即可。

例如中序遍历的代码如下:

后续的代码和中序很类似,这里就不上代码了。

有时候,我们需要一层层的遍历树。
这个其实就是常见的 广度优先搜索,简称 BFS。
我们一般使用队列这个数据结构来实现 BFS,在队列的系列中已经教过大家了。

四、相关实践

树的问题一般有两种:
一种是递归到叶子节点就确定一个答案的。
一种是根据两个儿子的状态,再加当前节点的状态,综合得到一个答案。

比如树的最大深度,两种方法都可以。

对于判断树是否树对称二叉树,则只能使用第二种方法。

而对于是否存在一条根到叶子节点的路径和等于指定数字的问题,则使用第一种方法。

五、最后

好了,二叉树的基础知识相信你了解的差不多了。
随后我会把这些问题的题号留言放出来。
另外,对于其他文章,如果你发现对应的题号没放出来,可以留言告诉我,可能我之前忘记了。

-EOF-

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面打开下面的地址进行留言。如果下面没有地址,可以关注公众号留言。
原文地址:https://mp.weixin.qq.com/s/Q0MgdrnJE4-U4PaPCrn5MQ

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越