ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 二叉树的遍历

二叉树的遍历

原创 Linux操作系统 作者:fengzj 时间:2008-11-25 15:09:35 0 删除 编辑

二叉树的遍历

二叉树的三种遍历方式:先序遍历、中序遍历、后序遍历

先序:
    始终执行以下步骤,
    1、访问根节点
    2、遍历左子树
    3、遍历右子树
中序:
    始终执行以下步骤,
    1、遍历左子树
    2、访问根节点
    3、遍历右子树
后序:
    始终执行以下步骤,
    1、遍历左子树
    2、遍历右子树
    3、访问根节点

“始终”:为什么要说“始终”执行呢?因为二叉树的每一个子树又可以看成是一个新的二叉树,遍历步骤、方式都保持一样,所以应该“始终”执行同样的操作,我们也应该始终把它看成一棵新的二叉树。(还是用图来讲吧)

              图

先序:
   1、访问根节点,所以先序的第一个元素为A
   2、遍历左子树:
         (我们应该把左子树看成一棵新的二叉树,“始终”执行)
          1、访问根节点,所以第二个元素为B
          2、遍历左子树:
               (我们应该把左子树看成一棵新的二叉树,“始终”执行)
               1、访问根节点,所以第三个元素为D
               2、遍历左子树:(D没有左子树,则遍历右子树)
               3、遍历右子树:只有一个元素,所以第四个元素为G
          3、遍历右子树:(B没有右子树)
   3、遍历右子树:
          (我们应该把右子树看成一棵新的二叉树,“始终”执行)
          1、访问根节点:所以第五个元素为C
          2、访问左子树:只有一个元素,所以第六个元素为E
          3、访问右子树:只有一个元素,所以第七个元素为F
   三个步骤执行完了,先序遍历为:ABDGCEF

中序
   1、遍历左子树:
         (我们应该把左子树看成一棵新的二叉树,“始终”执行)
         1、遍历左子树:
               (我们应该把左子树看成一棵新的二叉树,“始终”执行)
               1、遍历左子树:(D没有左子树,所以下一步)
               2、访问根节点,所以第一个元素为D
               3、遍历右子树:只有一个元素,所以第二个元素为G
         2、访问根节点:所以第三个元素为B
         3、遍历右子树:(B没有右子树)
    2、访问根节点:所以第四个元素为A
    3、遍历右子树:
          (我们应该把右子树看成一棵新的二叉树,“始终”执行)
          1、遍历左子树:只有一个元素,所以第五个元素为E
          2、访问根节点:所以第六个元素为C
          3、遍历右节点:只有一个元素,所以第七个元素为F
    三个步骤执行完了,中序遍历为:DGBAECF

后序
    后序遍历就给大家练习吧~



一些技巧:
    1、先序遍历第一个元素一定是根节点
    2、中序遍历中,任何一个元素的前一个元素一定在二叉树中它的左边,比如D在G前面,则D在G左边
    3、后序遍历最后一个元素一定是根节点
    4、先、中、后意思是说访问根节点的先后顺序,而且始终从左往右,从上往下...
    5、等你来更新...
  (还有什么技巧不要吝啬哦,记得评论里讲一下我更新...)

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/219982/viewspace-503188/,如需转载,请注明出处,否则将追究法律责任。

下一篇: exp/imp命令详解
请登录后发表评论 登录
全部评论

注册时间:2008-11-11

  • 博文量
    76
  • 访问量
    178033