二叉树及常见遍历方法

在计算机科学中,二叉树是每个结点最多有两个子树的树结构。 通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。 二叉树常被用于实现二叉查找树和二叉堆。 一棵深度为k,且有2^k-1个结点的二叉树,称为满二叉树。

讲到二叉树,它的先序遍历、中序遍历、后续遍历和逐层遍历是最常见的话题。先来看二叉树的生成方法。

接下来是二叉树的前序遍历、中序遍历和后序遍历。

最后是二叉树的逐层遍历(从上往下逐层遍历)。这里只说一下思路。用上面的先序遍历方法遍历二叉树,将遍历到的内容一次加入一个队列。最后再从队头开始打印队列即可。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据