遍历

作者: 偷了月光的猫 | 来源:发表于2019-12-12 10:01 被阅读0次

    前序遍历

    前序遍历(DLR),是二叉树遍历的一种,也叫做先根遍历、先序遍历、前序周游,可记做根左右。前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。

    前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。

    二叉树为空则结束返回,否则:

    (1)访问根结点。

    (2)前序遍历左子树

    (3)前序遍历右子树 。

    前序遍历

    需要注意的是:遍历左右子树时仍然采用前序遍历方法。

    如右图所示二叉树

    前序遍历结果:ABDECF

    已知后序遍历和中序遍历,就能确定前序遍历。

    中序遍历

    中序遍历(LDR)是二叉树遍历的一种,也叫做中根遍历、中序周游。在二叉树中,中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。

    中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。若二叉树为空则结束返回,否则:

    (1)中序遍历左子树

    (2)访问根结点

    (3)中序遍历右子树

    中序遍历

    如右图所示二叉树,中序遍历结果:DBEAFC

    后序遍历

    后序遍历(LRD)是二叉树遍历的一种,也叫做后根遍历、后序周游,可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中,先左后右再根,即首先遍历左子树,然后遍历右子树,最后访问根结点。

    后序遍历首先遍历左子树,然后遍历右子树,最后访问根结点,在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后遍历根结点。即:

    二叉树为空则结束返回,

    否则:

    (1)后序遍历左子树

    (2)后序遍历右子树

    (3)访问根结点

    后序遍历

    如右图所示二叉树

    后序遍历结果:DEBFCA

    已知前序遍历和中序遍历,就能确定后序遍历。

    相关文章

      网友评论

          本文标题:遍历

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