中序遍歷

中序遍歷（LDR）是二叉樹遍歷的一種，也叫做中根遍歷、中序週遊。在二叉樹中，中序遍歷首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。

基本介紹

• 中文名：中序遍歷
• 外文名：Inorder Traversal (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)。

複雜性

設二叉樹中元素數目為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 class BTNode                  //二叉樹節點類型{    public BTNode lchild;    public BTNode rchild;    public char data;}*//*public string btstr                 //全局變數*/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;