數據結構學習：完全二叉樹的判斷

[問題描述]
　　建立一棵二叉樹，判斷其是否為完全二叉樹，打印輸出判斷結果。

[基本要求]
　　從鍵盤接受輸入（先序），以二叉鏈表作為存儲結構，建立二叉樹（以先序來建立），並對其進行層次遍歷，並判斷它是否為完全二叉樹，然後打印輸出判斷結果。

//
//  main.swift
//  CompleteBinaryTreeTester
//
//  Created by 潘岸平 on 2017/11/22.
//  Copyright © 2017年 潘岸平. All rights reserved.
//

import Foundation

class BinaryTree {
    
    class BiTNode {
        
        private var _data: T
        private var _leftSubNode, _rightSubNode: BiTNode?
        
        public var data: T {
            get {
                return self._data
            }
            set {
                self._data = newValue
            }
        }
        
        public var leftSubNode: BiTNode? {
            get {
                return self._leftSubNode
            }
            set {
                self._leftSubNode = newValue
            }
        }
        
        public var rightSubNode: BiTNode? {
            get {
                return self._rightSubNode
            }
            set {
                self._rightSubNode = newValue
            }
        }
        
        init(_ data: T) {
            self._data = data
        }
    }
    
    public enum TraverseMethod {
        case Preorder
        case Inorder
        case Postorder
    }
    
    private var _rootBiTNode: BiTNode?
    
    public var isEmptyTree: Bool {
        return self._rootBiTNode == nil
    }
    
    public var leftSubTree: BinaryTree {
        get {
            return BinaryTree(node: self._rootBiTNode?.leftSubNode)
        }
    }
    
    public var rightSubTree: BinaryTree {
        get {
            return BinaryTree(node: self._rootBiTNode?.rightSubNode)
        }
    }
    
    init(data rootBiTNodeData: T?) {
        if rootBiTNodeData != nil {
            self._rootBiTNode = BiTNode(rootBiTNodeData!)
        } else {
            self._rootBiTNode = nil
        }
    }
    
    init(node rootBiTNode: BiTNode?) {
        self._rootBiTNode = rootBiTNode
    }
    
    convenience init() {
        self.init(data: nil)
    }
    
    public func replaceLeftNode(data: T) -> Void {
        if !self.isEmptyTree {
            self._rootBiTNode!.leftSubNode = BiTNode(data)
        }
    }
    
    public func replaceRightNode(data: T) -> Void {
        if !self.isEmptyTree {
            self._rootBiTNode!.rightSubNode = BiTNode(data)
        }
    }
    
    public func traverse(tree: BinaryTree? = nil, level: Int = 1, method: TraverseMethod, todo: (T?, Int) -> Void) -> Void {
        let currentTree = tree != nil ? tree! : self
        if currentTree.isEmptyTree {
            todo(nil, level)
            return
        }
        if method == TraverseMethod.Preorder {
            todo(currentTree._rootBiTNode!.data, level)
        }
        self.traverse(tree: currentTree.leftSubTree, level: level + 1, method: method, todo: todo)
        if method == TraverseMethod.Inorder {
            todo(currentTree._rootBiTNode!.data, level)
        }
        self.traverse(tree: currentTree.rightSubTree, level: level + 1, method: method, todo: todo)
        if method == TraverseMethod.Postorder {
            todo(currentTree._rootBiTNode!.data, level)
        }
    }
}

var treeString = readLine()
if treeString != nil && treeString!.count >= 1 {
    var root: BinaryTree = BinaryTree(data: treeString!.removeFirst())
    func extendTree(tree: BinaryTree, dataSource: () -> Character?) -> Void {
        if tree.isEmptyTree {
            return
        }
        if let ch = dataSource() {
            tree.replaceLeftNode(data: ch)
            extendTree(tree: tree.leftSubTree, dataSource: dataSource)
        }
        if let ch = dataSource() {
            tree.replaceRightNode(data: ch)
            extendTree(tree: tree.rightSubTree, dataSource: dataSource)
        }
    }
    extendTree(tree: root) { () -> Character? in
        if treeString!.isEmpty {
            return nil
        }
        let ch = treeString!.removeFirst()
        if ch == " " {
            return nil
        }
        return ch
    }
    var traverseQueue: [Int : [Character]] = [Int : [Character]]()
    root.traverse(method: BinaryTree.TraverseMethod.Preorder) { ch, level in
        if traverseQueue[level] == nil {
            traverseQueue[level] = [Character]()
        }
        traverseQueue[level]!.append(ch != nil ? ch! : " ")
    }
    var traverseString = ""
    for level in 1 ... traverseQueue.count {
        let currentLevel = traverseQueue[level]!
        for charIndex in 0 ..< currentLevel.count {
            traverseString.append(currentLevel[charIndex])
        }
    }
    print("層次遍歷序列：\(traverseString)")
    var traverseArray = [Character](traverseString)
    var isCompleteBinaryTree = true
    for charIndex in 1 ..< traverseArray.count {
        if traverseArray[charIndex - 1] == " " && traverseArray[charIndex] != " " {
            isCompleteBinaryTree = false
            break
        }
    }
    print("該二叉樹\(isCompleteBinaryTree ? "是" : "不是")完全二叉樹")
}