先序遍歷(Pre-order),按照根左右的順序沿一定路徑經過路徑上所有的結點。在二叉樹中,先根後左再右。巧記:根左右。
基本介紹
- 中文名:先序遍歷
- 解釋:先序遍歷
- 原始碼:C
- 參考資料:語言與基礎算法
先序遍歷
原始碼
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); }}