中序遍歷

中序遍歷

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

基本介紹

  • 中文名:中序遍歷
  • 外文名:Inorder Traversal (LDR)
  • 類屬二叉樹遍歷
  • 別名中根遍歷
  • 遍歷方法:先左子樹,後根結點,最後右子樹
  • 套用學科:計算機科學
定義,數學表達式形式,複雜性,程式實現,c++版本,Java版本,C#版本,pascal版本,

定義

中序遍歷首先遍歷左子樹,然後訪問根結點,最後遍歷右子樹。若二叉樹為空則結束返回,否則:
(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;

相關詞條

熱門詞條

聯絡我們