再写二叉树遍历 olr lor lro leveltraverse depthtraverse

class Bitree<T>{
 var value:T
 var left:Bitree?
 var right:Bitree?
 init(_ value:T) {
 self.value = value
 }
}
由于我们需要用到堆栈的操作，我们就对Array做扩展来完成
// MARK: - 使用数组构造出 栈的特性 push pop
extension Array{
 mutating func pop() -> Element {
 return removeFirst()
 }
 mutating func push(node:Element) -> Void {
 insert(node, at: 0)
 }
}
基本的数据访问
/// 访问节点
///
/// - Parameter t:
func visit<T>(_ t:Bitree<T>){
 print("\(t.value)")
}
/// 广度优先遍历
///
/// - Parameter tree: 根节点
func levelTraverse<T>(tree:Bitree<T>?){
 if tree == nil{
 return
 }
 var queue:Array<Bitree<T>> = [Bitree<T>]()
 if queue.isEmpty {
 queue.append(tree!)
 }
 /**
 利用队列FIFO实现广度优先
 */
 while queue.isEmpty == false {
 let q = queue.first
 queue.removeFirst()
 visit(q!)
 if q?.left != nil {
 queue.append((q?.left)!)
 }
 if q?.right != nil {
 queue.append((q?.right)!)
 }
 }
}
/// 深度优先遍历 实质 就是 olr（先序遍历）
/// 利用FILO 符合stac的特点
/// - Parameter tree: 根节点
func depthTracerse<T>(tree:Bitree<T>?){
 if tree == nil {
 return
 }
 var stack:[Bitree<T>] = [Bitree<T>]()
 stack.push(node: tree!)
 while !stack.isEmpty {
 let p = stack.pop()
 print("\(p.value)")
 if p.right != nil {
 stack.push(node: p.right!)
 }
 if p.left != nil {
 stack.push(node: p.left!)
 }
 }
}

//中序
func lor<T>(tree:Bitree<T>?){
 if tree != nil {
 lor(tree: tree?.left)
 visit(tree!)
 lor(tree: tree?.right)
 }
}
//先序
func olr<T>(tree:Bitree<T>?){
 if tree != nil {
 visit(tree!)
 olr(tree: tree?.left)
 olr(tree: tree?.right)
 }
}
func lro<T>(tree:Bitree<T>?){
 if tree != nil{
 lro(tree: tree?.left)
 lro(tree: tree?.right)
 visit(tree!)
 }
}