算法--Swift--二叉树

上一节讲了链表的基本实现,今天让我们来简单的了解下二叉树.
在二叉树中涉及到好多的基本概念,这些请自行百度,我们的主要目标使用swift实现简单的二叉树创建和操作.
下面是一个常见的二叉树:

屏幕快照 2017-12-08 上午11.03.35.png

下面我们创建一个树类和节点类:

/// 二叉树类
public class B_Tree<T>{
    /// 节点类
    public class TreeNode<T>{
        
        public var val: T
        public var left: TreeNode<T>?
        public var right: TreeNode<T>?
        public init(_ value: T){
            self.val = value
        }
        
        typealias Node = TreeNode<T>
    }
    
    /// 重新定义方便使用
    public typealias Node = TreeNode<T>
    
    /// 根节点
    var root: Node?
}

下面我们要给树添加相应的方法

/// 创建完全二叉树(添加节点)
    public func addNode(val: T){
        
        let newNode = Node(val)
        if self.root == nil {
            self.root = newNode
            return
        }
        
        var queue = [self.root]
        
        while queue.count != 0 {
            
            let curNode = queue[0]
            queue.remove(at: 0)
            
            if curNode!.left == nil {
                curNode!.left = newNode
                return
            }else{
                queue.append(curNode!.left)
            }
            
            if curNode!.right == nil {
                curNode!.right = newNode
                return
            }else{
                queue.append(curNode!.right)
            }
            
        }
    }

添加节点后,一颗完全二叉树就完成了
下面我要做的是遍历这颗树:
1.层次遍历:

/// 按照广度打印每一个节点
    public func width_print_node(){
        if self.root == nil {
            print("当前为空树")
            return
        }
        
        var text = "["
        var queue = [self.root]
        
        while queue.count != 0 {
            let curNode = queue[0]
            queue.remove(at: 0)
            
            text += " \(curNode!.val)"
            
            if curNode!.left != nil{
                queue.append(curNode!.left)
            }
            
            if curNode!.right != nil{
                queue.append(curNode!.right)
            }
        }
        
        text += " ]"
        
        print(text)
    }

2.先序遍历,中序遍历,后序遍历

/// 先序遍历
    public func pre_tra(curNode: Node?){
        guard let curNode = curNode else {return}
        
        print(curNode.val, terminator: "")
        pre_tra(curNode: curNode.left)
        pre_tra(curNode: curNode.right)
    }
    
    /// 中序遍历
    public func in_tra(curNode: Node?){
        guard let curNode = curNode else {return}
        
        in_tra(curNode: curNode.left)
        print(curNode.val, terminator: "")
        in_tra(curNode: curNode.right)
    }
    
    /// 后序遍历
    public func post_tra(curNode: Node?){
        guard let curNode = curNode else {return}
        
        post_tra(curNode: curNode.left)
        post_tra(curNode: curNode.right)
        print(curNode.val, terminator: "")
    }

最后我们检验一下我们的劳动成果:

let b_tree = B_Tree<Int>()
b_tree.addNode(val: 0)
b_tree.addNode(val: 1)
b_tree.addNode(val: 2)
b_tree.addNode(val: 3)
b_tree.addNode(val: 4)
b_tree.addNode(val: 5)
b_tree.addNode(val: 6)
b_tree.addNode(val: 7)
b_tree.addNode(val: 8)
b_tree.addNode(val: 9)

//层次遍历
b_tree.width_print_node()
print("*****************************")
//前序遍历
b_tree.pre_tra(curNode: b_tree.root)
print("\n*****************************")
//中序遍历
b_tree.in_tra(curNode: b_tree.root)
print("\n*****************************")
//后序遍历
b_tree.post_tra(curNode: b_tree.root)

看下控制台的输出结果:

[ 0 1 2 3 4 5 6 7 8 9 ]
*****************************
0137849256
*****************************
7381940526
*****************************
7839415620

关于面试:

1.用非递归实现先序遍历

/// 用栈实现的前序遍历
    func preorderTraversal(root: Node?) -> [Int]{
        guard let root = root else {
            return []
        }

        var ret = [Int]()
        var stack:Array<Node> = [Node]()
        var point: Node? = root
        
        while !stack.isEmpty || point != nil{
            if point != nil {
                stack.append(point!)
                ret.append(point!.val)
                point = point!.left
            }else{
                point = stack.removeLast().right
            }
        }
        
        return ret
    }

大工告成,以后相关的面试题会补充进来!