-
前序遍歷
鎖定
- 中文名
- 前序遍歷
- 外文名
- Preorder Traversal (VLR)
- 別 名
- 先根遍歷、先序遍歷、前序周遊
- 應用學科
- 計算機科學
- 時間複雜性
- O (n)
- 空間複雜性
- O(n)
前序遍歷簡介
前序遍歷首先訪問根結點然後遍歷左子樹,最後遍歷右子樹。在遍歷左、右子樹時,仍然先訪問根結點,然後遍歷左子樹,最後遍歷右子樹。
若二叉樹為空則結束返回,否則:
(1)訪問根結點。
(2)前序遍歷左子樹。
需要注意的是:遍歷左右子樹時仍然採用前序遍歷方法。
如圖1所示二叉樹
前序遍歷結果:ABDECF
已知後序遍歷和中序遍歷,就能確定前序遍歷。
前序遍歷數學表達式形式
當對一棵數學表達式樹進行中序,前序和後序遍歷時,就分別得到表達式的中綴、前綴和後綴形式。
在後綴(postfix)表達式中,每個操作符跟在操作數之後,操作數按從左到右的順序出現。在前綴(prefix)表達式中,操作符位於操作數之前。在前綴和後綴表達式中不會存在歧義。
因此,在前綴和後綴表達式中都不必採用括號或優先級。從左到右或從右到左掃描表達式並採用操作數棧,可以很容易確定操作數和操作符的關係。若在掃描中遇到一個操作數,把它壓入堆棧,若遇到一個操作符,則將其與棧頂的操作數相匹配。把這些操作數推出棧,由操作符執行相應的計算,並將所得結果作為操作數壓入堆棧。
[2]
前序遍歷複雜性
設二叉樹中元素數目為n。這四種遍歷算法的空間複雜性均為O (n),時間複雜性為O(n)。
前序遍歷程序實現
前序遍歷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; } } }