二叉树实现

二叉树

树

树 是 N(N>=0)个节点的有限集。当N=0时称为空树。
在任意一棵非空树中：

• 1、有且仅有一个特定的称为根节点
• 2、当N>1时，其余节点可分为M个互不相交的有限集合，其中每一个集合本身又是一棵树，并且称为根的子树

树.png

结点拥有的子树树称为结点度

度为0的结点称为叶结点或者终端结点

度不为0的结点称为非终端结点或者分支结点

除根结点之外，分支节点也称为内部结点。树的度是树内部各结点的度的最大值

树1.png

节点间的关系

• 1、结点的子树的根称为该结点的孩子(Child)，相应的，该结点称为孩子的双亲(Parent)
• 2、同一个双亲的孩子之间称为兄弟

结点的层次从根开始定义起，根为第一层，根的孩子为第二层，依次类推

树2.png

为什么要有树结构

树结构是一种天然的组织结构，将数据使用树存储的时候，出奇的高效

我们生活中有很多树结构

树3.png 树4.png 树5.png

二叉树

• 1、每个结点最多有两棵树
• 2、左树和右树是有顺序的，次序不能颠倒
• 3、即使树中某个结点只有一棵树，也要区分它是左子树还是右子树
• 4、左斜树：所有的结点都只有左子斜树的二叉树叫左斜树
• 5、右斜树：所有的结点都只有右子斜树的二叉树叫右斜树
• 6、满二叉树：所有的结点都存在左子树和右子树，并且所有叶子都在同一层上
• 7、完全二叉树：所有的结点都存在左子树和右子树，左右两边不一定在同一层次

二叉树的基本数据结构

class Node: NSObject {
  var E:Int 
  var left:Node?
  var right:Node?
}

二分搜索树(Binary Search Tree)

二叉树.png

二分搜索树也是一种二叉树
二分搜索树的每个节点的值

• 大于其左子树的所有节点的值
• 小于其右子树的所有节点的值

我们现在就来实现一个简单的二分搜索树吧

节点

//节点
class Node: NSObject {
    var E:Int = 0
    var left:Node?
    var right:Node?
    override init() {
        super.init()
    }
    init(E:Int) {
        self.E = E
        self.left = nil
        self.right = nil
    }
   
}

我们实现的二分搜索树实现以下功能

• 1、判断树是否为空
• 2、添加元素
• 3、查看二分搜索树中是否包含某个元素
• 4、二分搜索树的前序遍历、中序遍历、后序遍历
• 5、寻找二分搜索树的最小元素，删除二分搜索树的最小元素
• 6、寻找二分搜索树的最大元素、删除二分搜索树的最大元素
• 7、删除任意的节点

我们创建一个BTS类，里面有两个成员变量

var size = 0     //树的大小
var root:Node!   //根节点

1、判断树是否为空

    //判断是否为空
    func isEmpty() -> Bool{
        return size == 0;
    }

2、添加元素

    //添加元素
    func add(E:Int) {
        if root == nil {
            size += 1
            root = Node(E: E)
        }else{
            addNode(E: E, node: root)
        }
        
    }


 // 向以node为根的二分搜索树中插入元素e，递归算法
    private
    func addNode(E:Int,node:Node) {
        //递归用法，先判断结束语句
        if node.E == E {
            return
        }else if((E < node.E) && (node.left == nil)){
            //遍历到最后，添加左叶子
            node.left = Node(E: E)
            size += 1
            return
        }else if((E > node.E) && (node.right == nil)){
            //遍历到最后，添加右叶子
            node.right = Node(E: E)
            size += 1
            return
        }
        
        //递归调用
        if E < node.E {
            addNode(E: E, node: node.left ?? Node())
        }else{
            addNode(E: E, node: node.right ?? Node())
        }
        
    }

思路：

• 1、首先判断root是否为空，如果root为空的话，第一个添加的元素就是root
• 2、在root不为空的时候，我们需要循环遍历，E>节点值的时候添加到右子树，E<节点值的时候添加到左子树，知道循环遍历到最后一个节点为空的时候，添加上去

3、查看二分搜索树中是否包含某个元素

//查看二分搜索树中是否包含某个元素
func contain(E:Int) -> Bool {
        return containNode(E: E, node: root)
  }

// 看以node为根的二分搜索树中是否包含元素e, 递归算法
    private
    func containNode(E:Int,node:Node?) -> Bool {
        if node == nil {
            return false
        }
        
        if node?.E == E{
            return true
        }else if (node?.E)! > E {
            //左
            return containNode(E: E, node: node?.left )
        }else{
            //右
            return containNode(E: E, node: node?.right)
        }
        
    }

4、前序遍历、中序遍历、后序遍历

前序遍历：规则是若二叉树为空，则空操作返回，否则先访问根节点，然后前续遍历左子树，然后再前序遍历右子树

前序遍历.png

//二分搜索树的前序遍历
    func preOrder() {
        preOrder(node: root)
    }
// 前序遍历以node为根的二分搜索树, 递归算法
    private
    func preOrder(node:Node?) {
        //结束条件
        if node == nil {
            return
        }
        print(node?.E ?? "nil")
        preOrder(node: node?.left)
        preOrder(node: node?.right)
    }

中序遍历：规则是若树为空，则空操作返回，否则从根节点开始（注意并不是先访问根节点），中序遍历根节点是左子树，然后是访问根节点，最后中序遍历右子树

中序遍历.png

// 二分搜索树的中序遍历
    func inOrder() {
        inOrder(node: root)
    }
// 中序遍历以node为根的二分搜索树, 递归算法
    private
    func inOrder(node:Node?) {
        //结束条件
        if node == nil {
            return
        }
        inOrder(node: node?.left)
        print(node?.E ?? "nil")
        inOrder(node: node?.right)
        
    }

后序遍历：规则是若树为空，则空操作返回，否则从左到右先子叶后节点的方式遍历访问左右子树，最后是访问根节点

后序遍历.png

// 二分搜索树的后序遍历
func postOrder() {
    postOrder(node: root)
}

// 后序遍历以node为根的二分搜索树, 递归算法
    private
    func postOrder(node:Node?) {
        //结束条件
        if node == nil {
            return
        }
        inOrder(node: node?.left)
        inOrder(node: node?.right)
        print(node?.E ?? "nil")
    }

5、寻找二分搜索树的最小元素，删除二分搜索树的最小元素

寻找二分搜索树的最小元素

// 从二分搜索树中删除最小值所在节点, 返回最小值
   func removeMin() -> Int {
       if size == 0 {
           return 10086
       }
       root = removeMin(node: root)
       return minimum()
   }

return minimum(node: root).E
}
//查找最小数据 递归算法
   private
   func minimum(node:Node?) -> Node{
       if node?.left == nil {
           return node ?? Node()
       }
   
       return minimum(node: node?.left)
   }

思路：

• 1、根据二分搜索树的定义我们知道，最小值一定在最左侧子节点上面，我们一直往最左侧子节点遍历就可以了

删除二分搜索树的最小元素

// 从二分搜索树中删除最小值所在节点, 返回最小值
func removeMin() -> Int {
if size == 0 {
return 10086
}
root = removeMin(node: root)
return minimum()
}

// 删除掉以node为根的二分搜索树中的最小节点
// 返回删除节点后新的二分搜索树的根
private
func removeMin(node:Node?) -> Node? {
if node?.left == nil {
size -= 1
let rightNode = node?.right
node?.right = nil
return rightNode
}
node?.left = removeMin(node: node?.left)
return node
}

删除最小元素.png

思考：
在删除最小元素的时候我们需要考虑两种情况

• 1、最小元素没有子树了
• 2、最小元素有右子树

针对上面这种，我们代码可以这样写

if node?.left == nil {
size -= 1
let rightNode = node?.right
node?.right = nil
return rightNode
}

在最小元素有有右子树的时候，我们需要把这个右子树占据我们删除的那个子树的位置

6、寻找二分搜索树的最大元素、删除二分搜索树的最大元素

寻找二分搜索树的最大元素

// 寻找二分搜索树的最大元素
func maximum() -> Int {
if size == 0 {
return 10086
}

return maximum(node: root)
}

//查找最大数据 递归算法
private
func maximum(node:Node?) -> Int {
if node?.right == nil {
return node?.E ?? 10086
}
return maximum(node: node?.right)
}

删除二分搜索树的最大元素

// 从二分搜索树中删除最大值所在节点, 返回最大值
func removeMax() -> Int {
if size == 0 {
return 10086
}
root = removeMax(node: root)
return maximum()
}

// 删除掉以node为根的二分搜索树中的最大节点
// 返回删除节点后新的二分搜索树的根
private
func removeMax(node:Node?) -> Node? {
if node?.right == nil {
size -= 1
let leftNode = node?.left
node?.left = nil
return leftNode
}
node?.right = removeMax(node: node?.right)
return node
}

7、删除任意的节点

// 删除为E的节点
func remove(E:Int) ->Node{
root = remove(E: E, node: root)
return root
}

// 删除掉以node为根的二分搜索树中值为e的节点, 递归算法
// 返回删除节点后新的二分搜索树的根
private
func remove(E:Int,node:Node?) -> Node? {
if node == nil {
return nil
}
if E < (node?.E)! {
node?.left = remove(E: E, node: node?.left)
return node
}else if E > (node?.E)! {
node?.right = remove(E: E, node: node?.right)
return node
}else{
//找到了
// 待删除节点左子树为空的情况
if node?.left == nil{
let rightNode = node?.right
node?.right = nil
size -= 1
return rightNode
}
// 待删除节点右子树为空的情况
if node?.right == nil{
let leftNode = node?.left
node?.left = nil
size -= 1
return leftNode
}
// 待删除节点左右子树均不为空的情况

// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
// 用这个节点顶替待删除节点的位置
let successor = minimum(node: node?.right)
successor.right = removeMin(node: node?.right)
successor.left = node?.left
node?.right = nil
node?.left = nil

return successor
}
}

思考：

• 1、在找到待删除节点以后，左节点为空时，这个时候跟删除最小值类似

// 待删除节点左子树为空的情况
if node?.left == nil{
let rightNode = node?.right
node?.right = nil
size -= 1
return rightNode
}

• 2、在找到待删除节点以后，右节点为空时，这个时候跟删除最大值类似

// 待删除节点右子树为空的情况
if node?.right == nil{
let leftNode = node?.left
node?.left = nil
size -= 1
return leftNode
}

• 3、待删除节点左右子树均不为空的情况
  找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点；用这个节点顶替待删除节点的位置

删除任意节点1.png 删除任意节点2.png

相关demo，可以在这里查看