二叉树的四种遍历算法 |
您所在的位置:网站首页 › 算法二叉树 › 二叉树的四种遍历算法 |
文章目录
前言
递归版本:
非递归版本:
前言
二叉树在作为一种重要的数据结构,它的很多算法的思想在很多地方都用到了,比如说大名鼎鼎的 STL 算法模板,里面的优先队列(priority_queue)、集合(set、map)等等都用到了二叉树里面的思想,如果有兴趣的小伙伴可以去查找一些这些方面的资料。但是我们现在先不讨论那么高深的数据结构,我们先从二叉树的遍历开始: 先来看一下二叉树长什么样子: 这是百度来的一张二叉树图,我们可以看到, 这棵二叉树一共有 7 个节点, 其中, 0 号节点叫做“根节点”, 下面的 1 号节点和 2 号节点是 0 号节点的子节点,1 号节点为 0 号节点的**“左子节点**, 2 号节点为 0 号节点的 右子节点 同时 1 号节点和 2 号节点又是 3 号节点、 4 号节点和 5 号节点、6号节点的双亲节点, 0 号节点有分别以 1 号节点和 2 号节点作为根节点的左右子树。 5 号节点和 6 号节点没有子节点(子树),那么它们被称为“叶子节点”。 好了,一些常用的基本概念就到这了,能理解就行,如果还想了解更多专业术语,可以去找一些别的资料。 下面进入正题,二叉树的遍历: 一般来说,二叉树常用的遍历方式有:前序遍历、中序遍历、后序遍历、层序遍历 四种遍历方式,不同的遍历算法,其思想略有不同,我们来看一下这四种遍历方法主要的算法思想: 1、先序遍历二叉树顺序:根节点 --> 左子树 --> 右子树,即先访问根节点,然后是左子树,最后是右子树。 上图中二叉树的前序遍历结果为:0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6 2、中序遍历二叉树顺序:左子树 --> 根节点 --> 右子树,即先访问左子树,然后是根节点,最后是右子树。 上图中二叉树的中序遍历结果为:3 -> 1 -> 4 -> 0 -> 5 -> 2 -> 6 3、后续遍历二叉树顺序:左子树 --> 右子树 --> 根节点,即先访问左子树,然后是右子树,最后是根节点。 上图中二叉树的后序遍历结果为:3 -> 4 -> 1 -> 5 -> 6 -> 2 -> 0 4、层序遍历二叉树顺序:从最顶层的节点开始,从左往右依次遍历,之后转到第二层,继续从左往右遍历,持续循环,直到所有节点都遍历完成 上图中二叉树的层序遍历结果为:0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 下面给出这四种算法思想的伪代码: 递归版本:前序遍历: preOrderParse(int n) { if(tree[n] == NULL) return ; // 如果这个节点不存在,那么结束 cout |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |