美文网首页数据结构和算法分析
数据结构-二叉树的遍历

数据结构-二叉树的遍历

作者: 小明同学机器人 | 来源:发表于2020-02-13 12:56 被阅读0次

  在学习数据结构二叉树这块的时候,遍历二叉树无疑是一个重中之重,比如我们在做一个学生管理系统的时候,我们要查某个学生基本信息表数据库,还得访问他的家庭信息,成绩信息,生平信息等却不再一个表上,但是能从表A读取到表B和C,表B读取到表D和表E,环环相扣,如果要将这些数据遍历出来,那也是需要一定算法的。今天我就用四种算法来遍历二叉树。


例子图P

1.先序遍历

  • 先访问根节点
  • 再访问左子树
  • 最后访问右子树
    例子图P 先序 访问的结果为 ABCDEF

先序解析:

根据上述的三点原则,我用一串 小明语言代码来解释下,代码而非判断,而是根据例子图P来做的解释

小明代码:把例子图p的排序规则转换为代码形式,代码形式能又转换为口头语言,非运行语言。
1.  A start
2. A=true=getA;  //A
3. A.left=true=getB;//B
4. B.left=C=true=getC;//C
5. C.left=null;C.right=null; return B;
6. B.right=true=getD;//D
7. D.left=null;D.right=null;return B;return A;
8. A.right=true=getE;//E
9. E.left=null; E.right=true=getF;//F
//连起来就是先序遍历的结果

从上述的小明语言代码可以发现每个结点都是先get它(取出打印此结点,也就是先访问根结点),然后访问的该节点的左节点,然后右节点,后面的大体原理一样


例子图P

2.中序遍历

  • 先访问左子树
  • 再访问根节点
  • 最后访问右子树

例子图P 中序 访问的结果为 CBDAEF

中序解析:

1. start A
2. A.left.left=B.left=true=getC; //C
3.return B;getB;//B
4.B.right=true=getD;//D
5.return B;return A;getA;//A
6.A.right.left=E.left=null;getE;//E
7.E.right=true=getF;//F

例子图P

3.后序遍历

  • 先访问左子树
  • 再访问右子树
  • 最后访问根节点
    例子图P 后序 访问的结果为CDBFEA

后序解析:

start A
A.left.left=B.left=true=getC;
B.right=true=getD;
return B;getB;
return A;
A.right.left=E.left=null;
E.right=true=getF;
return E;getE;
return A;getA;

例子图P

4.层序遍历

  • 一层一层来遍历
    例子图P 层序遍历 访问的结果为ABECDF

层序解析:

在代码中 我们以队列的方式进行遍历,根据先进先出的原则。

getA
getA.left=B;
getA.right=E
getB.left=C; getB.right=D;
getE.left=null;getE.right=F;

最后让你们看个好看的视频 点击下方

      !!!!!!!我的奇葩生涯!!!!!!!!

相关文章

  • 二叉树的遍历

    数据结构算法 二叉树的遍历

  • python实现二叉树的遍历

    二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有深度遍历和广度遍历,...

  • 算法系列--二叉树的三种遍历的六种实现

    0. 二叉树是常见的数据结构,二叉树常见的遍历方式有前序遍历,中序遍历和后序遍历。前序遍历就是中-左-右节点的顺序...

  • 二叉树的四种遍历方法

    二叉树的数据结构 1、前序遍历(递归) 2、中序遍历(递归) 3、后序遍历(递归) 4、层次遍历(队列)

  • Python实现深度优先与广度优先

    二叉树的两种遍历是数据结构的经典考察题目, 广度遍历考察队列结构, 深度遍历考察递归 二叉树 深度优先 先序遍历(...

  • 数据结构第12讲 二叉树的层次遍历

    数据结构第12讲 二叉树的层次遍历 二叉树的遍历一般有先序遍历、中序遍历和后序遍历,这三种遍历比较简单。今天我们讲...

  • 算法学习

    ### 实现二叉树以及二叉树遍历数据结构递归比较重要 1.先序遍历 先序遍历,就是先遍历根节点然后再遍历左子树,最...

  • 二叉树的总结

    1、二叉树的数据结构 2、二叉树的创建 树的结构: 输入:AB#C##D## ; 3、二叉树的遍历 二叉树的遍历分...

  • 数据结构之二叉树

    数据结构之二叉树 递归构造二叉树 二叉树节点: 递归构造: 图示: 递归遍历 递归实现先序遍历 图示: 递归实现中...

  • 数据结构之二叉树

    数据结构之二叉树 本文讲解二叉树的基本操作: 查找节点 计算树的高度 清空树 递归遍历:先序遍历、中序遍历、后序遍...

网友评论

    本文标题:数据结构-二叉树的遍历

    本文链接:https://www.haomeiwen.com/subject/dhykfhtx.html