二叉树广度优先遍历

发表于 | 分类于

所谓的二叉树广度遍历，就是从上到下依次一层一层遍历。
队列的特点是先进先出，正好可以利用这一特点做二叉树的广度优先遍历，所以遍历的时候需要借助一个队列。

以下是要遍历的二叉树：

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
76
77
78
79
80
81
82
83
84
85

class TreeNode{
    var value:String?;
    var leftChild:TreeNode?;
    var rightChild:TreeNode?;
    
    init(value:String, left:TreeNode?, right:TreeNode?) {
        self.value = value;
        self.leftChild = left;
        self.rightChild = right;
    }
}


class Queue{
    
    private var itemArray:Array<TreeNode>?;
    
    init() {
        self.itemArray = [];
    }
    
    func push(value:TreeNode) -> Void {
        self.itemArray?.append(value);
    }
    
    func pop() -> TreeNode? {
        
        if self.itemArray!.count > 0 {
            
            let headItem:TreeNode = self.itemArray!.first!;
            
            self.itemArray?.removeFirst();
            
            return headItem;
        }
        
        return nil;
    }
    
    func isEmpty() -> Bool {
        return self.itemArray!.count == 0;
    }
}


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

var readResult:Array<String> = [];
var treeQueue:Queue = Queue();


// 开始遍历，先把根节点放入队中
treeQueue.push(value: aNode);

// 一直到队列的所有元素出列
while (!(treeQueue.isEmpty())){
    
    // 队列里的第一个元素出列
    let root:TreeNode? = treeQueue.pop();
    
    if root != nil {
        
        readResult.append(root!.value!);
        
        // 如果存在左子树，就把它入队
        if (root!.leftChild != nil) {
            treeQueue.push(value: root!.leftChild!);
        }
        
        // 如果存在右子树，就把它入队
        if (root!.rightChild != nil) {
            treeQueue.push(value: root!.rightChild!);
        }
    }
}

print("广度优先遍历结果：");
print(readResult);

以下是输出结果：

1
2
3

广度优先遍历结果：
["A", "B", "C", "D", "E", "F"]