複製鏈接
請複製以下鏈接發送給好友

前序遍歷

鎖定
前序遍歷(VLR), [1] 二叉樹遍歷的一種,也叫做先根遍歷、先序遍歷、前序周遊,可記做根左右。前序遍歷首先訪問根結點然後遍歷左子樹,最後遍歷右子樹。
中文名
前序遍歷
外文名
Preorder Traversal (VLR)
別    名
先根遍歷、先序遍歷、前序周遊
應用學科
計算機科學
時間複雜性
O (n)
空間複雜性
O(n)

前序遍歷簡介

前序遍歷首先訪問根結點然後遍歷左子樹,最後遍歷右子樹。在遍歷左、右子樹時,仍然先訪問根結點,然後遍歷左子樹,最後遍歷右子樹。
二叉樹為空則結束返回,否則:
(1)訪問根結點。
(2)前序遍歷左子樹
圖1 前序遍歷 圖1 前序遍歷
(3)前序遍歷右子樹 。
需要注意的是:遍歷左右子樹時仍然採用前序遍歷方法。
如圖1所示二叉樹
前序遍歷結果:ABDECF
已知後序遍歷和中序遍歷,就能確定前序遍歷。

前序遍歷數學表達式形式

當對一棵數學表達式樹進行中序,前序和後序遍歷時,就分別得到表達式的中綴、前綴和後綴形式。
在後綴(postfix)表達式中,每個操作符跟在操作數之後,操作數按從左到右的順序出現。在前綴(prefix)表達式中,操作符位於操作數之前。在前綴和後綴表達式中不會存在歧義。
因此,在前綴和後綴表達式中都不必採用括號或優先級。從左到右或從右到左掃描表達式並採用操作數棧,可以很容易確定操作數和操作符的關係。若在掃描中遇到一個操作數,把它壓入堆棧,若遇到一個操作符,則將其與棧頂的操作數相匹配。把這些操作數推出棧,由操作符執行相應的計算,並將所得結果作為操作數壓入堆棧。 [2] 

前序遍歷複雜性

設二叉樹中元素數目為n。這四種遍歷算法的空間複雜性均為O (n),時間複雜性為O(n)。
當t 的高度為n時(右斜二叉樹的情況),通過觀察其前序、中序和後序遍歷時所使用的遞歸棧空間即可得到上述結論。 [2] 

前序遍歷程序實現

前序遍歷C語言

樹節點結構和算法:
typedef struct TreeNode
{
    int data;
    TreeNode * left;
    TreeNode * right;
    TreeNode * parent;
}TreeNode;

void pre_order(TreeNode * Node)
{
    if(Node != NULL)
    {
        printf("%d ", Node->data);
        pre_order(Node->left);
        pre_order(Node->right);
    }
}
調用時:
pre_order(Root); //Root為樹的根

前序遍歷Pascal版本

核心代碼:
procedure first(i:longint);
begin
write(a[i]);
if a[i*2]0 then first(i*2);
if a[i*2+1]0 then first(i*2+1);
end;

前序遍歷Java版本

二叉樹定義
publicclassTreeNode{
    intval;
    TreeNodeleft;
    TreeNoderight;
    TreeNode(intx){
        val=x;
    }
}
遞歸實現
publicvoidpreOrder(TreeNodebiTree){
    System.out.printf(biTree.val+"");
    TreeNodeleftTree=biTree.left;
    if(leftTree!=null){
        preOrder(leftTree);
    }
    TreeNoderightTree=biTree.right;
    if(rightTree!=null){
        preOrder(rightTree);
    }
}
非遞歸實現
publicvoidpreOrder(TreeNodebiTree){
    Stack<TreeNode>stack=newStack<TreeNode>();
    while(biTree!=null||!stack.isEmpty()){
        while(node!=null){
            System.out.print(biTree.value+",");
            stack.push(biTree);
            biTree=biTree.left;
        }
        if(!stack.isEmpty()){
            biTree=stack.pop();
            biTree=biTree.right;
        }
    }
}
參考資料
  • 1.    梁田貴,張鵬.算法設計與分析:冶金工業出版社,2004.09:第149頁
  • 2.    AdamDrozdek .C++數據結構與算法 :清華大學出版社 ,2014