二叉树-二叉搜索树OC封装

作者: 嗯o哼 | 来源:发表于2020-12-10 15:04 被阅读0次

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

二叉树-二叉搜索树OC封装

Node.h

Node.m

BinaryTree.h

// BinaryTree.m

BinarySearchTree.h

BinarySearchTree.m

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读