第一次写的代码备份：
1. 概念
二叉搜索树，BST（Binary Search Tree），即为特殊的二叉树。
以根节点为例，左子树中所有的值均小于根节点；右子树中所有的值均大于根节点。此结论对于任意节点有效。
二叉搜索树，为有序树。按照中序遍历的方式（左 - 中 - 右）得到的序列为从小到大的有序序列。
因此，最左侧的叶子节点为最小元素，左右侧的节点为最大元素。
2. 操作
2.1 二叉搜索树的创建及节点插入
二叉搜索树的创建过程，就是依次按需插入节点的过程。
整体插入过程类似于折半查找的分治思想：第一个插入的节点作为标识，小于的节点插入到左子树中，大于的节点插入到右子树中。然后每个节点上均递归此过程。
我们先创建二叉树的节点，创建过程如下：
/** 二叉树的节点 */
@interface TreeNode : NSObject
@property (nonatomic, strong) TreeNode *leftChild;
@property (nonatomic, strong) TreeNode *rightChild;
@property (nonatomic, assign) NSInteger data;
@end
@implementation TreeNode
- (NSString *)description {
// 中序遍历输出
NSString *desp = @"";
if (self.leftChild) {
desp = [NSString stringWithFormat:@"%@ %@", desp, self.leftChild];
}
desp = [NSString stringWithFormat:@"%@ %ld", desp, self.data];
if (self.rightChild) {
desp = [NSString stringWithFormat:@"%@ %@", desp, self.rightChild];
}
return desp;
}
@end
插入节点的实现如下：
// 向二叉查找树（BinarySearchTree）中插入节点
TreeNode *insertNodeToBST(TreeNode *treeNode, NSInteger data) {
// 空树，则直接创建为根节点
if (!treeNode) {
treeNode = [TreeNode new];
treeNode.data = data;
return treeNode;
}
// 树存在，则根据数据大小，查看需要插入到的子树
if (treeNode.data > data) {
// 插入到左子树，左子树更新
treeNode.leftChild = insertNodeToBST(treeNode.leftChild, data);
} else {
// 插入到右子树，右子树更新
treeNode.rightChild = insertNodeToBST(treeNode.rightChild, data);
}
return treeNode;
}
创建二叉搜索树的过程，即依次插入节点：
// 创建二叉查找树
TreeNode *createBST(NSArray *source) {
TreeNode *BST;
for (NSNumber *item in source) {
BST = insertNodeToBST(BST, item.integerValue);
}
return BST;
}
简单调用：
// 创建二叉查找树
TreeNode *BST = createBST(@[@34, @11, @998, @2, @45, @22]);
NSLog(@"%@", BST);
// 插入
BST = insertNodeToBST(BST, 0);
NSLog(@"%@", BST);
执行结果：
AlgorithmLearning[25055:10245382] 2 11 22 34 45 998
AlgorithmLearning[25055:10245382] 0 2 11 22 34 45 998
由此也可以看出，创建二叉查找树的过程，也是对数组进行排序的过程（需要按照中序遍历输出）。
2.2 二叉搜索树的节点删除
从二叉搜索树中删除节点的要求，是不能破坏二叉树的整体结构（中序遍历出的结果仍然有序）。
可以通过修改节点数据或移除节点的方式进行。
首先，我们可以将删除的节点进行分类：
- 删除的节点为叶子节点，没有左右子树；
- 删除的节点为根节点，只有右子树；
- 删除的节点为根节点，只有左子树；
- 删除的节点为根节点，包含左右子树。
解法：
- 对于没有左右子树的叶子节点，删除时，只要将其父节点的对应子节点置为NULL即可；（可以理解为单链表尾部节点的删除）
- 对于只有右子树的节点来说，删除时，只要将其父节点对应的右子节点设置为删除节点的右节点即可；（可以理解为单链表中间某节点的删除）
- 对于只有左子树的节点来说，删除时，只要将其父节点对应的左子节点设置为删除节点的左节点即可；（同上）
- 对于同时包含左右子树的节点，删除情况要复杂一些：
删除时，由于所有左节点均小于删除节点，因此，需要找一个大于所有左子树节点（大于左子节点即可），同时又是右子树中最小的节点即可。因此，只要选定待删除节点的右子树中，最左边的节点进行覆盖即可（没有则直接将待删节点的右节点提上即可）。
这里，需要两个额外功能，
- 在二叉查找树中，查找指定节点：
TreeNode *findNode(TreeNode *BST, NSInteger data) {
if (BST.data == data) {
return BST;
}
if (BST.data > data) {
return findNode(BST.leftChild, data);
} else {
return findNode(BST.rightChild, data);
}
return nil;
}
- 在二叉树中，查找指定节点的父节点：
TreeNode *findPrevNode(TreeNode *BST, NSInteger data) {
if (!BST) {
return nil;
}
if (BST.leftChild.data == data || BST.rightChild.data == data) {
return BST;
} else {
TreeNode *parent1 = findPrevNode(BST.leftChild, data);
TreeNode *parent2 = findPrevNode(BST.rightChild, data);
if (parent1) {
return parent1;
}
if (parent2) {
return parent2;
}
}
return nil;
}
删除子节点的实现如下：
// 从二叉查找树中删除指定数据
BOOL deleteNodeFromBST(TreeNode *BST, NSInteger data) {
// 查询数据所在节点
TreeNode *deleteNode = findNode(BST, data);
// 没有找到待删除数据，失败
if (!deleteNode) {
return NO;
}
// // 查看待删除节点是否存在左子树
// if (deleteNode.leftChild) {
// // 存在左子树，即有比待删除节点小的，需要重新调整
// // 根据中序访问“左-中-右”的顺序，左子树中最大的，即为最右端的子结点，故遍历查找之
// TreeNode *theRightNode = deleteNode.leftChild;
// TreeNode *superOfTheRightNode = theRightNode;
// while (theRightNode.rightChild) {
// superOfTheRightNode = theRightNode; // 记录最右的父节点
// theRightNode = theRightNode.rightChild;
// }
// // 将待删除结点数据赋值为左子树的最右端节点
// deleteNode.data = theRightNode.data;
//
// if (superOfTheRightNode == theRightNode) {
// // 没有最右节点，左子树都是左结点
// // 因此最大的就是待删除节点的左节点
// // 指向下一个左节点即可（没有就是nil）
// deleteNode.leftChild = theRightNode.leftChild;
// } else {
// // 最右节点的父节点，其右节点则替换为此右节点的左子树即可（没有就是nil）
// superOfTheRightNode.rightChild = theRightNode.leftChild;
// }
//
//
// } else {
// // 不存在左子树，则右子树如果存在，都比待删除节点大，
// // 根据中序访问“左-中-右”的顺序，可以直接移除，
//
// // 找到待删除节点的父节点
// TreeNode *parentNode = findPrevNode(BST, data);
//
// // 其父节点的左子树指向待删除节点的右子树即可
// parentNode.leftChild = deleteNode.rightChild; // 直接覆盖了待删除节点
// }
if (!deleteNode.leftChild && !deleteNode.rightChild) {
// 1. 左右子树都不存在
// 获取父节点
TreeNode *parentNode = findPrevNode(BST, data);
// 将对应的子节点置为nil
if (parentNode.leftChild == deleteNode) {
parentNode.leftChild = nil;
} else {
parentNode.rightChild = nil;
}
} else {
if (deleteNode.rightChild && !deleteNode.leftChild) {
// 2. 只存在右子树
// 获取父节点
TreeNode *parentNode = findPrevNode(BST, data);
if (!parentNode) {
deleteNode = deleteNode.rightChild;
} else if (parentNode.leftChild == deleteNode) {
// 是左子节点
// 父的相应子节点指向下一个右节点，完成删除
parentNode.leftChild = deleteNode.rightChild;
} else {
// 父的相应子节点指向下一个右节点，完成删除
parentNode.rightChild = deleteNode.rightChild;
}
} else if (deleteNode.leftChild && !deleteNode.rightChild) {
// 3. 只存在左子树
// 获取父节点
TreeNode *parentNode = findPrevNode(BST, data);
if (!parentNode) {
deleteNode = deleteNode.leftChild;
} else if (parentNode.leftChild == deleteNode) {
parentNode.leftChild = deleteNode.leftChild;
} else {
parentNode.rightChild = deleteNode.leftChild;
}
} else {
// 4. 左右子树均存在
// 查找待删除节点的右子树中，最小的节点（最左边的节点）
TreeNode *tmpNode = deleteNode.rightChild;
if (tmpNode.leftChild) {
TreeNode *prevNode = tmpNode; // 用于遍历过程中，顺便取到的tmpNode的父节点
// 找到最小节点
while (tmpNode.leftChild) {
prevNode = tmpNode; // 记录父节点
tmpNode = tmpNode.leftChild;
}
// 进行数据覆盖
deleteNode.data = tmpNode.data;
// 清除此最小节点
prevNode.leftChild = nil;
} else {
// 最小节点就是待删除节点的右节点，与2的情况相同
// 进行数据覆盖
deleteNode.data = tmpNode.data;
// 指向下一个
deleteNode.rightChild = tmpNode.rightChild;
}
}
}
return YES;
}
注：注释代码为更简略实现。
测试如下：
// 删除
BOOL deleteResult = deleteNodeFromBST(BST, 998);
NSLog(@"%hhd", deleteResult);
NSLog(@"%@", BST);
执行结果：
AlgorithmLearning[26968:10339083] 1
AlgorithmLearning[26968:10339083] 0 2 11 22 34 45
