-
先序遍歷
鎖定
先序遍歷(Pre-order)，按照根左右的順序沿一定路徑經過路徑上所有的結點。在二叉樹中，先根後左再右。巧記：根左右。
- 中文名
- 先序遍歷
- 解 釋
- 先序遍歷
- 源代碼
- C
- 參考資料
- 語言與基礎算法
先序遍歷算法介紹
先序遍歷也叫做先根遍歷、前序遍歷，可記做根左右（二叉樹父結點向下先左後右）。
例如，圖1所示二叉樹的遍歷結果是：ABDECF
圖1
先序遍歷源代碼
C
#define CountOfNodes 0xFFFF
typedef 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); begin if bt<>nil then begin write(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);
}
}
