共找到2條詞條名為先序遍歷的結果 展開

先序遍歷

按左右的順序經過路上所有的結點

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

目錄
1簡介 2源代碼 C

簡介

先序遍歷也叫做先根遍歷、前序遍歷，可記做根左右（二叉樹父結點向下先左後右）。
首先訪問根結點然後遍歷左子樹，最後遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹，如果二叉樹為空則返回。
例如，下圖所示二叉樹的遍歷結果是：ABDECF
圖例
圖例

源代碼

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
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;
}
}
}
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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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
1
2
3
4
5
6
7
8
9
procedure preorder(bt:tree);
begin
if bt<>nil then begin
write(bt^.data);
preorder(bt^.left);
precoder(bt^.right);
end;
end;
PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//節點結構
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);
}
}

基本信息

中文名
先序遍歷
別名
先根遍歷、前序遍歷
參考
語言與基礎演算法
源代碼
C
解釋
先序遍歷