Node.h
//
// Node.h
// BinarySearchTree
//
// Created by lee on 2020/12/1.
//
#import <Foundation/Foundation.h>
@interface Node : NSObject
/// 当前元素
@property(nonatomic,strong) id element;
/// 左子结点
@property(nonatomic,strong) Node *left;
/// 右子结点
@property(nonatomic,strong) Node *right;
/// 父结点
@property(nonatomic,weak) Node *parent;
// 是否为度为2的结点
-(BOOL)hasTwoNode;
-(instancetype)initWithElement:(id)element parent:(Node *)parent;
@end
Node.m
//
// Node.m
// BinarySearchTree
//
// Created by lee on 2020/12/1.
//
#import "Node.h"
@implementation Node
-(instancetype)initWithElement:(id)element parent:(Node *)parent{
if (self = [super init]) {
self.element = element;
self.parent = parent;
}
return self;
}
-(BOOL)hasTwoNode{
return self.left != nil && self.right != nil;
}
//
//-(void)dealloc{
// NSLog(@"结点已销毁");
//}
@end
BinaryTree.h
//
// BinaryTree.h
// BinarySearchTree
//
// Created by lee on 2020/12/9.
//
#import <Foundation/Foundation.h>
#import "Node.h"
typedef BOOL(^BinaryAction)(id);
@interface BinaryTree : NSObject
@property(nonatomic,assign) int size;
@property(nonatomic,strong) Node *root;
@property(nonatomic,assign) int height;
-(int)size;
-(BOOL)isEmpty;
-(void)clear;
/// 前序遍历
-(void)preorderTraversal:(BinaryAction) action;
/// 中序遍历
-(void)inorderTraversal:(BinaryAction) action;
/// 后序遍历
-(void)postorderTraversal:(BinaryAction) action;
/// 层序遍历
-(void)levelOrderTraversal:(BinaryAction) action;
/// 前驱结点
-(Node *)predecessorNode:(Node *)node;
/// 后继结点
-(Node *)successor:(Node *)node;
@end
// BinaryTree.m
//
// BinaryTree.m
// BinarySearchTree
//
// Created by lee on 2020/12/9.
//
#import "BinaryTree.h"
@interface BinaryTree()
@end
@implementation BinaryTree
-(BOOL)isEmpty{
return NO;
}
-(void)clear{
self.root = nil;
self.size = 0;
}
-(int)height{
if (self.root ==nil) {
return 0;
}
if (_height > 0) {
return _height;
}
_height = [self heightOfTree:self.root];
return _height;
}
-(int)heightOfTree:(Node *)node{
if (node == nil) {
return 0;
}
return 1 + MAX([self heightOfTree:node.left], [self heightOfTree:node.right]);
}
// 前序遍历
-(void)preorderTraversal:(BinaryAction) action{
// [self preorderTraversal:self.root,action:action];
[self preorderTraversal:self.root action:action];
}
-(void)preorderTraversal:(Node *)node action:(BinaryAction)action{
// 1.node 为空的时候，退出
if (node == nil) return;
// 2.前序遍历，首先访问根结点
if (action) {
if (action(node.element)) {
return;
}
}
// 3.再访问左结点
[self preorderTraversal:node.left action:action];// 递归，进入步骤1
// 4.在访问右结点
[self preorderTraversal:node.right action:action];
}
/// 中序遍历
-(void)inorderTraversal:(BinaryAction) action{
[self inorderTraversal:self.root action:action];
}
-(void)inorderTraversal:(Node *)node action:(BinaryAction) action{
if (node == nil) return;
[self inorderTraversal:node.left action:action];
if (action) {
if (action(node.element)) {
return;
}
}
[self inorderTraversal:node.right action:action];
}
/// 后序遍历
-(void)postorderTraversal:(BinaryAction) action{
[self postorderTraversal:self.root action:action];
}
-(void)postorderTraversal:(Node *)node action:(BinaryAction) action{
if (node == nil) return;
[self postorderTraversal:node.left action:action];
[self postorderTraversal:node.right action:action];
if (action) {
if (action(node.element)) {
return;
}
}
}
/// 层序遍历
-(void)levelOrderTraversal:(BinaryAction) action{
if(self.root == nil) return;
/// 1.先将根结点入队
NSMutableArray *mArray = [NSMutableArray array];
[mArray addObject:self.root];
while (mArray.count != 0) {
Node *node = mArray.firstObject;
[mArray removeObjectAtIndex:0];
// 2.访问结点
if (action) {
if (action(node.element)) {
return;
}
}
// 3.查看是否具有左右子结点
if (node.left != nil) {
[mArray addObject:node.left];
}
if (node.right != nil) {
[mArray addObject:node.right];
}
}
}
/// 前驱结点
-(Node *)predecessorNode:(Node *)node{
// 1.如果该节点的left不为空,前驱结点在左子树中的最右边
Node *tempNode = node.left;
if (tempNode != nil) {
while (tempNode.right != nil) {
tempNode = tempNode.right;
}
return tempNode;
}
// 2.如果left为空，parent中
while (node.parent != nil && node == node.parent.right) {
node = node.parent;
}
return node.parent;
}
/// 后继结点
-(Node *)successor:(Node *)node{
// 1.如果该节点的right不为空，后继结点就在它的右子树中
Node *tempNode = node.right;
if (tempNode != nil) {
while (tempNode.right != nil) {
tempNode = tempNode.right;
}
return tempNode;
}
// 2.如果right为空，parent不为空
while (node.parent != nil && node == node.parent.left) {
node = node.parent;
}
return node;
}
-(Node *)searchNode:(id)element{
return nil;
}
@end
BinarySearchTree.h
//
// BinarySearchTree.h
// BinarySearchTree
//
// Created by lee on 2020/11/30.
//
#import <Foundation/Foundation.h>
#import "Node.h"
#import "BinaryTree.h"
typedef int(^CompareBlock)(id,id);
@interface BinarySearchTree : BinaryTree
@property(nonatomic,copy) CompareBlock compare;
-(instancetype)initWithCompare:(CompareBlock)compare;
/// 添加元素
/// @param element 新增的元素
-(void)add:(id)element;
/// 根据值查找结点
/// @param element 元素值
-(Node *)searchNode:(id)element;
/// 是否包含元素
/// @param element 元素值
-(BOOL)contain:(id)element;
/// 移除元素
/// @param element 元素值
-(void)remove:(id)element;
@end
BinarySearchTree.m
//
// BinarySearchTree.m
// BinarySearchTree
//
// Created by lee on 2020/11/30.
//
#import "BinarySearchTree.h"
@interface BinarySearchTree()
@end
@implementation BinarySearchTree
-(instancetype)init{
if (self = [super init]) {
self.size = 0 ;
self.root = nil;
}
return self;
}
-(instancetype)initWithCompare:(CompareBlock)compare{
if (self = [super init]) {
self.size = 0 ;
self.root = nil;
self.compare = compare;
}
return self;
}
/// 添加元素
/// @param element 新增的元素
-(void)add:(id)element{
// 检查参数不能为空
[self nodeNotNilCheck:element];
// 1.首先判断是否具有根结点
if (self.root == nil) {
self.root = [[Node alloc] initWithElement:element parent:nil];
self.size++;
return;
}
// 添加其余的结点
Node *parent = nil;
Node *tempNode = self.root;
int cmp = 0; // 记录插入到左边还是右边
while (tempNode != nil) {
cmp = [self compare:element e2:tempNode.element];
parent = tempNode;
if (cmp > 0) { // 左结点
tempNode = tempNode.right;
}else if(cmp < 0){ // 右结点
tempNode = tempNode.left;
}else{ // 相等进行覆盖
tempNode.element = element;
return;
}
}
Node *newNode = [[Node alloc] initWithElement:element parent:parent];
if (cmp > 0) {
parent.right = newNode;
}else if(cmp < 0){
parent.left = newNode;
}
self.size++;
}
-(void)remove:(id)element{
// 1.查询该值所在的结点
Node *node = [self searchNode:element];
[self removeNode:node];
if (self.size >0) {
self.size--;
}
}
-(void)removeNode:(Node *)node{
if (node == nil) return;
// 2.删除度为2的结点
if ([node hasTwoNode]) {
// 找到前驱或后继结点，用它的值覆盖改结点的值
Node *preNode = [self predecessorNode:node];
node.element = preNode.element;
node = preNode;
// 删除前驱或后继结点
}
// 删除度为1/0的结点
Node *replacement = node.left != nil ? node.left : node.right;
if (replacement != nil) {// 度为1
// 如果度为1，将父结点的子节点指向该节点的子节点到对应的位置
replacement.parent = node.parent;
// 判断子结点存在的位置
if(node.parent == nil){// 如果度为1且为根结点
self.root = replacement;
}else if (node == node.parent.left) {
node.parent.left = replacement;
}else if(node == node.parent.right){
node.parent.right = replacement;
}
}else if(node.parent == nil){ // 度为0，且为根结点
self.root = nil;
}else{ // 度为0，但不是根结点，直接删除结点，将它的父结点的left或right置为nil
if (node == node.parent.left) {
node.parent.left = nil;
}else{
node.parent.right = nil;
}
}
}
-(BOOL)contain:(id)element{
Node *node = [self searchNode:element];
return node == nil;
}
// 根据值，查找结点位置
-(Node *)searchNode:(id)element{
Node *node = self.root;
while (node != nil) {
int cmp = [self compare:element e2:node.element];
if (cmp == 0) {
return node;
}else if (cmp > 0){
node = node.right;
}else{
node = node.left;
}
}
return nil;
}
/// 返回0 e1 = e2 ， 大于0 e1 > e2，小于0 e1 < e2
-(int)compare:(id)e1 e2:(id)e2{
if (self.compare) {
return self.compare(e1, e2);
}
return 0;
}
-(void)nodeNotNilCheck:(Node *)node{
if (node == nil) {
NSLog(@"node 不能为空");
@throw [NSException exceptionWithName:@"node 不能为空" reason:nil userInfo:nil];
}
}
@end
网友评论