网站地图
中序遍历

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

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

(1)中序遍历左子树

(2)访问根结点

(3)中序遍历右子树

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

当对一棵数学表达式树进行中序,前序和后序遍历时,就分别得到表达式的中缀、前缀和后缀形式。中缀(infix)形式即平时所书写的数学表达式形式,在这种形式中,每个二元操作符(也就是有两个操作数的操作符)出现在左操作数之后,右操作数之前。在使用中缀形式时,可能会产生一些歧义。例如,x+y ×z可以理解为(x+y) ×z或x+ (y ×z)。为了避免这种歧义,可对操作符赋于优先级并采用优先级规则来分析中缀表达式。在完全括号化的中缀表达式中,每个操作符和相应的操作数都用一对括号括起来。更甚者把操作符的每个操作数也都用一对括号括起来。如( (x) + (y) ),( (x) + ( (y) * (z) ) )和( ( (x) + (y) ) * ( (y) + (z) ) ) * (w)。 [1]

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

当t的高度为n时(右斜二叉树的情况),通过观察其前序、中序和后序遍历时所使用的递归栈空间即可得到上述结论。 [1]

树中节点结构为:

核心代码:


相关文章推荐:
二叉树遍历 | 中根遍历 | 二叉树 | 中根遍历 | 二叉树 |
相关词汇词典