中序遍历

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

中序遍历详细介绍

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

中序遍历定义

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

（1）中序遍历左子树

（2）访问根结点

（3）中序遍历右子树

如图1所示二叉树，中序遍历结果：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)。

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

中序遍历程序实现

中序遍历c++版本

树中节点结构为：

typedef struct TreeNode {    int data;    struct TreeNode *left;    struct TreeNode *right;    struct TreeNode *parent;} TreeNode;void middle_order(TreeNode *Node) {    if(Node != NULL) {        middle_order(Node->left);        printf("%d ", Node->data);        middle_order(Node->right);    }}调用时： middle_order(Root); //Root为树的根

中序遍历Java版本

class TreeNode{    public int data;    public TreeNode leftChild;    public TreeNode rightChild;    public static void inOrderTraversal(TreeNode node){        if(node == null){            return;        }else{            inOrderTraversal(node.leftChild);        System.out.println(node.data);        inOrderTRaversal(node.rightChild);        }    }}

中序遍历C#版本

public string InOrder(BTNode t){    btstr="";                             InOrder1(r);    return btstr;}public string InOrder1(BTNode t){    if(t!=null)    {        InOrder(t.lchild);        bster+=t.data.ToString()+" ";        InOrder(t.rchild);    }}

中序遍历pascal版本

核心代码：

procedure mid(bt:tree);begin    if bt<>nil then begin        mid (bt^.left);        write(bt^.data);        mid (bt^.right);    end;end;