中序遍历是怎么遍历的?

中序遍历(LDR)是二叉树遍历的一种,也叫做中根遍历、中序周游。

遍历方式:

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

如下图所示二叉树,

1.jpg

中序遍历结果:DBEAFC

数学表达式形式

当对一棵数学表达式树进行中序,前序和后序遍历时,就分别得到表达式的中缀、前缀和后缀形式。

中缀(infix)形式即平时所书写的数学表达式形式,在这种形式中,每个二元操作符(也就是有两个操作数的操作符)出现在左操作数之后,右操作数之前。

在使用中缀形式时,可能会产生一些歧义。例如,x+y ×z可以理解为(x+y) ×z或x+ (y ×z)。

为了避免这种歧义,可对操作符赋于优先级并采用优先级规则来分析中缀表达式。

在完全括号化的中缀表达式中,每个操作符和相应的操作数都用一对括号括起来。

更甚者把操作符的每个操作数也都用一对括号括起来。如( (x) + (y) ),( (x) + ( (y) * (z) ) )和( ( (x) + (y) ) * ( (y) + (z) ) ) * (w)。

复杂性

设二叉树中元素数目为n,中序遍历算法的空间复杂性均为O (n),时间复杂性为(n)。

想要了解更多相关知识,请关注 html中文网!!

以上就是中序遍历是怎么遍历的?的详细内容,更多请关注web前端其它相关文章!

赞(0) 打赏
未经允许不得转载:web前端首页 » 其他答疑

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

前端开发相关广告投放 更专业 更精准

联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏