二叉搜索树

第一次写的代码备份：

1. 概念

二叉搜索树，BST（Binary Search Tree），即为特殊的二叉树。
以根节点为例，左子树中所有的值均小于根节点；右子树中所有的值均大于根节点。此结论对于任意节点有效。
二叉搜索树，为有序树。按照中序遍历的方式（左 - 中 - 右）得到的序列为从小到大的有序序列。
因此，最左侧的叶子节点为最小元素，左右侧的节点为最大元素。

2. 操作

2.1 二叉搜索树的创建及节点插入

二叉搜索树的创建过程，就是依次按需插入节点的过程。
整体插入过程类似于折半查找的分治思想：第一个插入的节点作为标识，小于的节点插入到左子树中，大于的节点插入到右子树中。然后每个节点上均递归此过程。

我们先创建二叉树的节点，创建过程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/** 二叉树的节点 */
@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

插入节点的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 向二叉查找树（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;
}

创建二叉搜索树的过程，即依次插入节点：

1
2
3
4
5
6
7
8
// 创建二叉查找树
TreeNode *createBST(NSArray *source) {
    TreeNode *BST;
    for (NSNumber *item in source) {
        BST = insertNodeToBST(BST, item.integerValue);
    }
    return BST;
}

简单调用：

1
2
3
4
5
6
7
// 创建二叉查找树
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 二叉搜索树的节点删除

从二叉搜索树中删除节点的要求，是不能破坏二叉树的整体结构（中序遍历出的结果仍然有序）。
可以通过修改节点数据或移除节点的方式进行。

首先，我们可以将删除的节点进行分类：

  1. 删除的节点为叶子节点，没有左右子树；
  2. 删除的节点为根节点，只有右子树；
  3. 删除的节点为根节点，只有左子树；
  4. 删除的节点为根节点，包含左右子树。

解法：

  1. 对于没有左右子树的叶子节点，删除时，只要将其父节点的对应子节点置为NULL即可；（可以理解为单链表尾部节点的删除）
  2. 对于只有右子树的节点来说，删除时，只要将其父节点对应的右子节点设置为删除节点的右节点即可；（可以理解为单链表中间某节点的删除）
  3. 对于只有左子树的节点来说，删除时，只要将其父节点对应的左子节点设置为删除节点的左节点即可；（同上）
  4. 对于同时包含左右子树的节点，删除情况要复杂一些：
    删除时，由于所有左节点均小于删除节点，因此，需要找一个大于所有左子树节点（大于左子节点即可），同时又是右子树中最小的节点即可。因此，只要选定待删除节点的右子树中，最左边的节点进行覆盖即可（没有则直接将待删节点的右节点提上即可）。

这里，需要两个额外功能，

  1. 在二叉查找树中，查找指定节点：
1
2
3
4
5
6
7
8
9
10
11
12
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;
}
  1. 在二叉树中，查找指定节点的父节点：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
}

删除子节点的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
// 从二叉查找树中删除指定数据
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;
}

注：注释代码为更简略实现。

测试如下：

1
2
3
4
//  删除
BOOL deleteResult = deleteNodeFromBST(BST, 998);
NSLog(@"%hhd", deleteResult);
NSLog(@"%@", BST);

执行结果：
AlgorithmLearning[26968:10339083] 1
AlgorithmLearning[26968:10339083] 0 2 11 22 34 45

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

嘿嘿嘿~<br><br>移动端小猿一个，努力学习中~<br>谢谢大家
Fork me on GitHub