在上一篇文章
Swift实现-Tree(树)、BaniryTree(二叉树)、BinarySearchTree(二叉搜索树)中，我们通过值类型（即枚举类型），实现了二叉搜索树的基本结构，及查找，插入等功能，现在我们通过类方法，来创建一个功能更加完善的二叉搜索树，这也是为了后面的红黑树等结构来坐下铺垫，因为上一篇文章已经对二叉搜索树进行了基本的介绍，这里就不多说了，有不清楚的，可以到上一篇文章去看看，下面直接上代码
基本实现
class ClassBinarySearchTree<T: Comparable> {
private(set) var value: T
private(set) var parent: ClassBinarySearchTree?
private(set) var leftChild: ClassBinarySearchTree?
private(set) var rightChild: ClassBinarySearchTree?
///是否为根节点
var isRoot: Bool {
return parent == nil
}
///是否为叶子节点
var isLeaf: Bool {
return leftChild == nil && rightChild == nil
}
var isLeftChild: Bool {
return parent?.leftChild === self
}
var isRightChild: Bool {
return parent?.rightChild === self
}
var hasLeftChild: Bool {
return leftChild != nil
}
var hasRightChild: Bool {
return rightChild != nil
}
var hasAnyChild: Bool {
return hasLeftChild || hasRightChild
}
var hasBothChildren: Bool {
return hasLeftChild && hasRightChild
}
var count: Int {
return (leftChild?.count ?? 0) + 1 + (rightChild?.count ?? 0)
}
init(_ value: T) {
self.value = value
}
}
上面是对树的一个节点的实现，它拥有对父，左子及右子的引用。同时他还拥有一些辅助的功能
插入
func insert(_ node: ClassBinarySearchTree) {
//1
if node.value > self.value {
//2
guard let right = rightChild else {
self.rightChild = node
node.parent = self
return
}
right.insert(node)
}else {
guard let left = leftChild else {
self.leftChild = node
node.parent = self
return
}
left.insert(node)
}
}
- 1.如果插入的值，大于当前值，则应该插入到右子树中
- 2.如果没有右子树，则用插入的值创建一个数，并成为右子树
左侧类同
类方法实现的二叉搜索树的插入操作，相对来说比通过枚举类型实现的二叉搜索树，做插入操作要容易的多，具体的可以到上一篇文章去查看
搜索
func search(_ value: T) -> ClassBinarySearchTree? {
if value == self.value {
return self
}else if value > self.value {
return self.rightChild?.search(value)
}else {
return self.leftChild?.search(value)
}
}
搜索同样通过递归引用实现，在处理树形结构时，很多操作都能通过递归实现，并且更加的易懂及方便，后面会写一篇关于递归应用的总结，有兴趣的也可以看看《图解算法》一书中，关于“分而治之”的章节，感觉讲解的很透彻及有趣
删除
由于删除节点后，仍然要维持二叉搜索树，所以操作有些复杂，它分为下面的几种情况：
假定要删除的是T树中的节点z
1、 如果z是叶子节点，则直接删除，将父节点对应的孩子指为nil
2、如果z只有一个孩子，那么删除z，用z的孩子替代z，即重新制定z孩子的父节点等等
3、z有左右两个子树，那么就需要找到z节点的后继，该后继一定在右子树中，且没有左孩子的节点，就是右子树数中最小的那个节点，假定这个节点是y，我们需要用y的有子树，来替代y，然后用y替代z
简单总结就是，如果有右子树，则从右子树中找最小的节点y，来替代要被删除的节点z，删除y，同时从y的右子树中，找最小的节点y1来替换y，循环往复
在这个过程中，如果没有右子树，只有左子树，那么就从左子树中找最大的节点y，循环往复的进行
有右找右，没右找左
extension ClassBinarySearchTree {
//1
private func reconnectParentToNode(node: ClassBinarySearchTree?) {
if let parent = parent {
if isLeftChild {
parent.leftChild = node
} else {
parent.rightChild = node
}
}
node?.parent = parent
}
//2
private func minNode() -> ClassBinarySearchTree {
var node = self
while let left = node.leftChild {
node = left
}
return node
}
//3
private func maxNode() -> ClassBinarySearchTree {
var node = self
while let right = node.rightChild {
node = right
}
return node
}
}
//4
extension ClassBinarySearchTree: CustomStringConvertible {
var description: String {
let value = self.value
let left: String = self.leftChild?.description ?? "空"
let right: String = self.rightChild?.description ?? "空"
return "\(value) " + "[\(value)左孩子 \(left)]" + "[\(value)右孩子 \(right)]"
}
}
上面是一些辅助方法
- 1这个方法就是删除自己后，用新的节点代替自己
- 2查找最小的子节点
- 3查找最大的子节点
- 4方便调试
var replaceMent: ClassBinarySearchTree?
if let right = rightChild {
replaceMent = right.minNode()
}else if let left = leftChild {
replaceMent = left.maxNode()
}else {
replaceMent = nil
}
let _ = replaceMent?.remove()
replaceMent?.leftChild = leftChild
replaceMent?.rightChild = rightChild
rightChild?.parent = replaceMent
leftChild?.parent = replaceMent
reconnectParentToNode(node: replaceMent)
parent = nil
leftChild = nil
rightChild = nil
return replaceMent
- 获得前驱，后继
func predecessor() -> ClassBinarySearchTree? {
if let left = leftChild {
return left.maxNode()
}else {
var node = self
while let parent = node.parent {
if parent.value < node.value {
return parent
}
node = parent
}
}
return nil
}
func successor() -> ClassBinarySearchTree? {
if let right = rightChild {
return right.minNode()
}else {
var node = self
while let parent = node.parent {
if parent.value > node.value {
return parent
}
node = parent
}
}
return nil
}
以中序遍历为例，一个节点的前驱，不一定会是该节点的左孩子，后继，也不一定是该节点的右孩子。上面的两个方法直接回返回节点的前驱和后继
前驱为例，如果该节点有左子树，那么前驱一定是左子树中最大的节点，如果没有左子树，那么前驱一定是父节点中最小的。
后继同样的道理。
