先序遍歷

先序遍歷(Pre-order)，按照根左右的順序沿一定路徑經過路徑上所有的結點。在二叉樹中，先根後左再右。巧記：根左右。

基本介紹

• 中文名：先序遍歷
• 解釋：先序遍歷
• 原始碼：C
• 參考資料：語言與基礎算法

先序遍歷

先序遍歷也叫做先根遍歷、前序遍歷，可記做根左右（二叉樹父結點向下先左後右）。

首先訪問根結點然後遍歷左子樹，最後遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹，如果二叉樹為空則返回。

例如，下圖所示二叉樹的遍歷結果是：ABDECF

圖例

原始碼

C

#define CountOfNodes 0xFFFFtypedef struct tagNODE{    int value ;    struct tagNODE *left,*right,*parent;}NODE;void PreOrder(const NODE* root) // 遞歸實現{    printf("%d\n",root->value);    if( root->left )PreOrder(root->left);    if( root->right )PreOrder(root->right);    return ;}int PreOrder(const NODE* root) // 非遞歸實現{    NODE** stack = (NODE**)calloc(CountOfNodes,sizeof(NODE));    NODE* point = NULL ;    int top = 0 , count = 0 ;    stack[top++] = root ;    while( top > 0 )    {        point = stack[--top] ;        printf("%d\n",point->value);        count ++ ;        if( point->right )stack[top++] = point->right;        if( point->left )stack[top++] = point->left;    }    return count ;}

Java

/*class BiTree {    int value;    BiTree lchild;    BiTree rchild;   public BiTree() {}    public BiTree(int value) {   super();   this.value = value;    }}*//*** 非遞歸* @param b*/public static void preScan(BiTree b) {    int length = 0;    BiTree[] stack = new BiTree[20];    stack[length ++] = b;    BiTree temp;    while(length > 0) {   temp = stack[-- length];   System.out.print(temp.value + " "); if(temp.rchild != null) {  stack[length ++] = temp.rchild;   }   if(temp.lchild != null) {  stack[length ++] = temp.lchild;   }    }}    /*** 遞歸* @param b*/public static void scan(BiTree b) {    if(b != null) {   System.out.print(b.value + " ");    }    if(b.lchild != null) scan(b.lchild);    if(b.rchild != null) scan(b.rchild);}

C#

/*public class BTNode                  //二叉樹節點類型{    public BTNode lchild;    public BTNode rchild;    public char data;}*//*public string btstr                 //全局變數*/public string InOrder(BTNode t){    btstr="";                             InOrder1(r);    returen btstr;}public string InOrder(BTNode t){    if(t!=null)    {        bster+=t.data.ToString()+" ";        InOrder(t.lchild);        InOrder(t.rchild);    }}

Pascal

procedure preorder(bt:tree);beginif bt<>nil then beginwrite(bt^.data);preorder(bt^.left);precoder(bt^.right);end;end; 

PHP

//節點結構class Node {        public $value;        public $left;        public $right;}//非遞歸算法function preorder($root) {       $stack = [];        array_push($stack, $root);        while(!empty($stack)) {               $current_node = array_pop($stack);                echo $current_node->value;                if($current_node->right != null) {                        array_push($stack, $current_node->right);                }                if($current_node->left != null) {                        array_push($stack, $current_node->left);                }        }}//遞歸算法function preorder(Node $root) {        echo $root->value;        if($root->left != null) {                preorder2($root->left);        }        if($root->right != null) {                preorder2($root->right);       }}