二叉树深度优先遍历

发表于 | 分类于

二叉树深度优先遍历分为：前序优先遍历、中序优先遍历、后序优先遍历。
所谓的前中后，是相对于读取根节点的顺序来说的。
以下是 swift 3.0 的实现

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

class TreeNode {
    
    var value:String?;
    var leftNode:TreeNode?;
    var rightNode:TreeNode?;
    
    init(value:String?, leftNode:TreeNode?, rightNode:TreeNode?) {
        self.value = value;
        self.leftNode = leftNode;
        self.rightNode = rightNode;
    }
}

var firstReadResult:Array<String> = [];
func firtRead(root:TreeNode?)
{
    guard root != nil else {
        return;
    }
    
    firstReadResult.append((root?.value)!);
    firtRead(root: root?.leftNode);
    firtRead(root: root?.rightNode);
}

var midReadResult:Array<String> = [];
func midRead(root:TreeNode?)
{
    guard root != nil else {
        return;
    }
    
    midRead(root: root?.leftNode);
    midReadResult.append((root?.value)!);
    midRead(root: root?.rightNode);
}

var lastReadResult:Array<String> = [];
func lastRead(root:TreeNode?)
{
    guard root != nil else {
        return;
    }
    
    lastRead(root: root?.leftNode);
    lastRead(root: root?.rightNode);
    lastReadResult.append((root?.value)!);
}

let dNode:TreeNode = TreeNode(value: "D", leftNode: nil, rightNode: nil);
let eNode:TreeNode = TreeNode(value: "E", leftNode: nil, rightNode: nil);
let fNode:TreeNode = TreeNode(value: "F", leftNode: nil, rightNode: nil);
let bNode:TreeNode = TreeNode(value: "B", leftNode: dNode, rightNode: eNode);
let cNode:TreeNode = TreeNode(value: "C", leftNode: fNode, rightNode: nil);
let aNode:TreeNode = TreeNode(value: "A", leftNode: bNode, rightNode: cNode);

// 前序遍历
firtRead(root: aNode);
print("前序遍历:");
print(firstReadResult);
print("\n");

// 中序遍历
midRead(root: aNode);
print("中序遍历:");
print(midReadResult);
print("\n");

// 后序遍历
lastRead(root: aNode);
print("后序遍历:");
print(lastReadResult);
print("\n");

以下是输出结果：

1
2
3
4
5
6
7
8
前序遍历:
["A", "B", "D", "E", "C", "F"]

中序遍历:
["D", "B", "E", "A", "F", "C"]

后序遍历:
["D", "E", "B", "F", "C", "A"]