OC数据结构02：二叉树探索

张建 lol
  2020-08-26 16:35:40 2020-08-26 16:35 Created   2023-05-08 12:41:59 2023-05-08 12:41 Updated      

什么是二叉树

树形结构，两个节点 以内均称为 二叉树，分为 左子树 和 右子树，有顺序，不能颠倒；比如把人看做树：头是树根，左右是坐子树，右手是右子树。

二叉树遍历类型

  1. 深度优先遍历：采用栈
  • 先序遍历：对任一子树，先访问 根，然后遍历 左子树，最后遍历其 右子树
  • 中序遍历：对任一子树，先遍历 左子树，然后访问 根，最后遍历其 右子树
  • 后序遍历：对任一子树，先遍历其 左子树，然后遍历其 右子树，最后访问 根
  1. 广度优先遍历：采用队列

层次遍历，从上往下 对每一层依次访问，每一层从 左往右（或从右往左）访问节点，访问完一层就进入下一层，直到没有节点可以访问为止。

  1. 区别：

  • 深度优先算法：不全部保留节点，占用空间小，有回溯操作，运行速度慢，用时间换空间

  • 广度优先算法：保留全部节点，占用空间大，无回溯操作，运行速度快，用空间换时间

二叉排序树的好处？

二叉树是一种比较折中的方案；数组的搜索比较方便，可以直接用下标，但删除或插入比较耗时；
链表与之相反，删除或插入很快，但查找很慢；二叉排序树既有链表的好处，也有数组的好处，在处理大批量的动态数据是比较有用的

二叉排序树节点定义

采用单项链表的形式，只从根节点指向孩子节点，不保存父节点。

对于二叉搜索树这种数据类型，用简单的数组来表示是不适合的。所以要建立一个模型：

  • 值：就用最简单的整数来表示，实际使用中，这个整型值也是必不可少的，可以当做key来用，这是二叉搜索树排序的凭证。
  • 左子树：用一个同类型的指针表示
  • 右子树：用一个同类型的指针表示

以上3个是二叉搜索树必不可少的属性

1
2
3
4
5
6
7
8
9
// 二叉排序树节点
@interface BinaryTreeNode : NSObject
// 值
@property (nonatomic, assign) NSInteger value;
// 左节点
@property (nonatomic, strong) BinaryTreeNode *leftNode;
// 右节点
@property (nonatomic, strong) BinaryTreeNode *rightNode;
@end

如何验证两个二叉树是完全相等的？

递归 去判断每个节点的 值 是否相等，如果均相等，则两个二叉树完全相等

1
2
3
4
5
6
7
8
9
10
11
12
- (void)isSameTree:(TreeNode *)root1 tree:(TreeNode *)root2{
   if (root1 == null && root2 == null) {
		return true;
	}
	if ((root1 == null && root2 != null) || (root1 != null && root2 == null)){
		return false;
	}
	if (root1.val != root2.val) { // 判断每个节点的值是否相等，如果去除此判断，则判断两个二叉树是否结构相等
		return false;
	}
	return [self isSameTree:root1.left tree:root2.left] && [self isSameTree:root1.right tree:root2.right];
}

创建二叉排序树

  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
31
32
33
34
35
36
37
38
39
40
41
42
/**
 *  创建二叉排序树
 *  二叉排序树：左节点值全部小于根节点值，右节点值全部大于根节点值
 *  @param values 数组
 *  @return 二叉树根节点
 */
+ (BinaryTreeNode *)createTreeWithValues:(NSArray *)values {
    BinaryTreeNode *root = nil;
    for (NSInteger i=0; i<values.count; i++) {
        NSInteger value = [(NSNumber *)[values objectAtIndex:i] integerValue];
        root = [BinaryTree addTreeNode:root value:value];
    }
    return root;
}

/**
 *  向二叉排序树节点添加一个节点
 *
 *  @param treeNode 根节点
 *  @param value    值
 *
 *  @return 根节点
 */
+ (BinaryTreeNode *)addTreeNode:(BinaryTreeNode *)treeNode value:(NSInteger)value {
    //根节点不存在，创建节点
    if (!treeNode) {
        treeNode = [BinaryTreeNode new];
        treeNode.value = value;
        NSLog(@"node:%@", @(value));
    }
    else if (value <= treeNode.value) {
        NSLog(@"to left");
        // 值小于根节点，则插入到左子树
        treeNode.leftNode = [BinaryTree addTreeNode:treeNode.leftNode value:value];
    }else {
        NSLog(@"to right");
        // 值大于根节点，则插入到右子树
        treeNode.rightNode = [BinaryTree addTreeNode:treeNode.rightNode value:value];
    }
    
    return treeNode;
}
  1. 实际使用

1）创建一个二叉树类BinaryTreeNode，在类中实现如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN

@interface BinaryTreeNode : NSObject
// 值：当做key来用，是排序用的凭证
@property (nonatomic,assign)NSInteger value;
// 左子树
@property (nonatomic,strong)BinaryTreeNode * leftChild;
// 右子树
@property (nonatomic,strong)BinaryTreeNode * rightChild;

// 创建二叉排序树
+ (BinaryTreeNode *)createBinaryTreeWithValues:(NSArray *)values;
// 向二叉排序树中添加一个节点
+ (BinaryTreeNode *)addNode:(BinaryTreeNode *)rootNode value:(NSInteger)value;
@end

NS_ASSUME_NONNULL_END
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
/*
 创建二叉排序树
 二叉排序树：左节点值全部小于根节点值，右节点值全部大于根节点值
 @param values：数组
 @return 二叉排序树根节点
 */
+ (BinaryTreeNode *)createBinaryTreeWithValues:(NSArray *)values{
    BinaryTreeNode * rootNode = nil;
    for (NSNumber * number in values) {
        NSInteger value = [number integerValue];
        rootNode = [BinaryTreeNode addNode:rootNode value:value];
    }
    return rootNode;
}
/*
 向二叉排序树节点添加一个节点
 @param rootNode 根节点
 @param value    值
 
 @return 根节点
 */
+ (BinaryTreeNode *)addNode:(BinaryTreeNode *)rootNode value:(NSInteger)value{
    // 根节点不存在，创建节点
    if (rootNode == nil) {
        rootNode = [[BinaryTreeNode alloc] init];
        rootNode.value = value;
        NSLog(@"node:%@",@(value));
    }else if (value <= rootNode.value) {
        NSLog(@"to left");
        // 值小于根节点，则插入到左子树；这是递归，左子树将做同样的事儿
        rootNode.leftChild = [self addNode:rootNode.leftChild value:value];
    }else if (value > rootNode.value) {
        NSLog(@"to right");
        // 值大于根节点，则插入到右子树；这是递归，右子树将做同样的事儿
        rootNode.rightChild = [self addNode:rootNode.rightChild value:value];
    }else {
        NSLog(@"二叉排序树没有键值相等的节点，值%@已存在，不能插入",@(value));
    }
    return rootNode;
}

2）在controller中，用一个属性持有这个二叉搜索树。

1
2
3
4
5
6
7
8
#import "ViewController.h"
//二叉树
#import "BinaryTreeNode.h"

@interface ViewController ()
// 二叉搜索树的根节点，代表一棵树
@property (strong, nonatomic) BinaryTreeNode *rootNode;
@end

输入用一串值，得到一颗二叉搜索树

1
2
3
4
5
6
7
- (void)viewDidLoad {
    [super viewDidLoad];
    //创建一个二叉树
    NSArray *values = @[@200, @23, @456, @89, @23, @670, @5674, @15];
    self.rootNode = [BinaryTreeNode createBinaryTreeWithValues:values];
    
}

3）用断点，查看“链式”结构，同时通过log可以看出创建过程。

4）生成的二叉树图

先序遍历

  1. 先访问根，再遍历左子树，再遍历右子树。典型的递归思想。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 *  先序遍历
 *  先访问根，再遍历左子树，再遍历右子树
 *
 *  @param rootNode 根节点
 *  @param handler  访问节点处理函数
 */
+ (void)preOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler {
    if (rootNode) { // 先根
        if (handler) {
            handler(rootNode);
        }
        // 再左
        [self preOrderTraverseTree:rootNode.leftNode handler:handler];
        // 最后右
        [self preOrderTraverseTree:rootNode.rightNode handler:handler];
    }
}
  1. 实际使用
1
2
3
4
5
6
7
8
// 先序遍历
- (void)preOrderTraverse{
    NSMutableArray * preArr = [NSMutableArray array];
    [BinaryTreeNode preOrderTraverseTree:self.rootNode handler:^(BinaryTreeNode * _Nonnull treeNode) {
        [preArr addObject:[NSNumber numberWithInteger:treeNode.value]];
    }];
    NSLog(@"先序遍历：%@", preArr);
}

查看打印结果：

1
2
3
4
5
6
7
8
9
2020-08-26 22:45:09.310234+0800 OC-二叉树[50561:2829401] 先序遍历：(
    200,
    23,
    15,
    89,
    456,
    670,
    5674
)

中序遍历

  1. 先遍历左子树，再访问根，再遍历右子树。
    对于二叉排序树来说，中序遍历得到的序列是一个从小到大排序好的序列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 *  中序遍历
 *  先遍历左子树，再访问根，再遍历右子树
 *
 *  @param rootNode 根节点
 *  @param handler  访问节点处理函数
 */
+ (void)inOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler {
    if (rootNode) {
        [self inOrderTraverseTree:rootNode.leftNode handler:handler];
        if (handler) {
            handler(rootNode);
        }
        [self inOrderTraverseTree:rootNode.rightNode handler:handler];
    }
}
  1. 实际使用
1
2
3
4
5
6
7
8
//中序遍历
- (void)inOrderTraverse{
    NSMutableArray * inArr = [NSMutableArray array];
    [BinaryTreeNode inOrderTraverseTree:self.rootNode handler:^(BinaryTreeNode * _Nonnull treeNode) {
        [inArr addObject:[NSNumber numberWithInteger:treeNode.value]];
    }];
    NSLog(@"中序遍历：%@", inArr);
}

查看打印结果

1
2
3
4
5
6
7
8
9
2020-08-26 22:49:26.310344+0800 OC-二叉树[50591:2832806] 中序遍历：(
    15,
    23,
    89,
    200,
    456,
    670,
    5674
)

后续遍历

  1. 先遍历左子树，再遍历右子树，再访问根
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 *  后序遍历
 *  先遍历左子树，再遍历右子树，再访问根
 *
 *  @param rootNode 根节点
 *  @param handler  访问节点处理函数
 */
+ (void)afterOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler {
    if (rootNode) {
        [self afterOrderTraverseTree:rootNode.leftNode handler:handler];
        [self afterOrderTraverseTree:rootNode.rightNode handler:handler];
        if (handler) {
            handler(rootNode);
        }
    }
}
  1. 实际使用
1
2
3
4
5
6
7
8
//后序遍历
- (void)afterOrderTraverse{
    NSMutableArray * afterArr = [NSMutableArray array];
    [BinaryTreeNode afterOrderTraverseTree:self.rootNode handler:^(BinaryTreeNode * _Nonnull treeNode) {
        [afterArr addObject:[NSNumber numberWithInteger:treeNode.value]];
    }];
    NSLog(@"后序遍历：%@", afterArr);
}

查看打印结果

1
2
3
4
5
6
7
8
9
10
2020-08-26 22:51:50.637367+0800 OC-二叉树[50628:2835309] 后序遍历：(
    15,
    89,
    23,
    5674,
    670,
    456,
    200
)

翻转二叉树

  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
/*
 翻转二叉树（又叫：二叉树的镜像）
 @param rootNode 根节点
 @return 翻转后的树根节点（其实就是原二叉树的根节点）
 */
// 翻转二叉树
+ (BinaryTreeNode *)flipBinaryTree:(BinaryTreeNode *)rootNode{
    // 判空
    if(!rootNode){
        return nil;
    }
    
    // 没有子节点
    if(!rootNode.leftNode && !rootNode.rightNode){
        return rootNode;
    }
    
    // 左右子树递归
    [self flipBinaryTree:rootNode.leftNode];
    [self flipBinaryTree:rootNode.rightNode];
    
    // 左右节点交换
    BinaryTreeNode * tempNode = rootNode.leftNode;
    rootNode.leftNode = rootNode.rightNode;
    rootNode.rightNode = tempNode.leftNode;
    
    return rootNode;
}

  1. 实际使用
1
2
3
4
// 翻转二叉树
- (void)invertBinaryTree{
    self.rootNode = [BinaryTreeNode invertBinaryTree:self.rootNode];
}

查看打印结果

生成二叉树的图

查找二叉树中某个位置的结点

类似索引操作，按 层次 遍历，位置从0开始算。

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
/*
 查找二叉树某个位置的结点
 @param index 按层次便利树是的位置（从0开始）
 @param rootNode 树根结点
 @return 结点
 */
// 指定位置查找节点
+ (BinaryTreeNode *)findTreeNodeAtIndex:(int)index withRootTree:(BinaryTreeNode *)rootNode{
    // 如果节点不存在，查找位置不符合规范
    if (!rootNode || index < 0){
        return nil;
    }
    
    NSMutableArray * queueArr = [NSMutableArray arrayWithCapacity:0];
    // 压入根节点
    [queueArr addObject:rootNode];
    while (queueArr.count > 0) {
        BinaryTreeNode * node = [queueArr firstObject];
        // 如果是根节点，则直接返回
        if(index == 0){
            return node;
        }
        // 仿照队列先进先出FIFO，移除最前面的节点
        [queueArr removeObjectAtIndex:0];
        index --;
        
        // 按照从左往右依次压入节点
        if(node.leftNode){
            [queueArr addObject:node.leftNode];
        }
        if(node.rightNode){
            [queueArr addObject:node.rightNode];
        }
    }
    // 遍历完，还没有找到位置，返回nil
    return nil;
}

在controller中调用

1
2
3
4
5
6
7
8
// 查找某个位置的节点
- (void)searchNode{
    BinaryTreeNode * node = [BinaryTreeNode findTreeNodeAtIndex:4 withTree:self.rootNode];
    NSLog(@"node-------%@",[NSNumber numberWithInteger:node.value]);
}

********打印结果******
2020-08-27 11:29:47.724120+0800 OC-二叉树[51450:2892148] node-------89

层次遍历

  1. 按照从上到下、从左到右的次序进行遍历。先遍历完一层，再遍历下一层，因此又叫广度优先遍历。需要用到队列，在OC里可以用可变数组来实现。

    根改了：NSArray *values = @[@100, @23, @45, @89, @23, @67, @54, @15];

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
/*
层次遍历（广度优先）

@param rootNode 树根节点
@param handler 访问节点处理函数
*/
// 层次遍历
+ (void)levelTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *))handler{
    // 空节点
    if(!rootNode){
        return;
    }
    // 数组当成队列
    NSMutableArray * queueArr = [NSMutableArray array];
    // 压入根节点
    [queueArr addObject:rootNode];
    // 当队列有数据的时候去遍历
    while (queueArr.count > 0) {
        BinaryTreeNode * node = [queueArr firstObject];
        if (handler){
            handler(node);
        }
        // 仿照队列先进先出FIFO，移除最前面的节点
        [queueArr removeObjectAtIndex:0];
        
        // 按照从左往右依次压入节点
        if(node.leftNode){
            [queueArr addObject:node.leftNode];
        }
        if(node.rightNode){
            [queueArr addObject:node.rightNode];
        }
    }
}

  1. 在controller中调用
1
2
3
4
5
6
7
8
//层次遍历
- (void)levelTraverse{
    NSMutableArray * levelArr = [NSMutableArray array];
    [BinaryTreeNode levelTraverseTree:self.rootNode handler:^(BinaryTreeNode * _Nonnull treeNode) {
        NSLog(@"value:%ld",treeNode.value);
        [levelArr addObject:treeNode];
    }];
}

次遍历：查看打印结果

1
2
3
4
5
6
7
2020-08-31 17:18:50.185983+0800 OC-二叉树[59736:4179500] value:100
2020-08-31 17:18:50.186414+0800 OC-二叉树[59736:4179500] value:23
2020-08-31 17:18:50.186896+0800 OC-二叉树[59736:4179500] value:15
2020-08-31 17:18:50.187158+0800 OC-二叉树[59736:4179500] value:45
2020-08-31 17:18:50.187479+0800 OC-二叉树[59736:4179500] value:89
2020-08-31 17:18:50.187753+0800 OC-二叉树[59736:4179500] value:67
2020-08-31 17:18:50.188040+0800 OC-二叉树[59736:4179500] value:54

二叉树的深度

  1. 二叉树的深度定义为：从根节点到叶子结点依次经过的结点形成树的一条路径,最长路径的长度为树的深度。
    1）如果根节点为空，则深度为0；
    2）如果左右节点都是空，则深度为1；
    3）递归思想：二叉树的深度=max（左子树的深度，右子树的深度）+ 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
 二叉树的深度
 @param rootNode 二叉树根节点
 @return 二叉树的深度
 */
// 二叉树的深度
+ (NSInteger)depthOfTree:(BinaryTreeNode *)rootNode{
    if (!rootNode){
        return 0;
    }
    if (!rootNode.leftNode && !rootNode.rightNode){
        return 1;
    }
    // 左子树深度
    NSInteger leftDepth = [self depthOfTree:rootNode.leftNode];
    // 右子树深度
    NSInteger rightDepth = [self depthOfTree:rootNode.rightNode];
    // 二叉树深度
    NSInteger totalDepth = MAX(leftDepth, rightDepth) + 1;
    
    return totalDepth;
}
  1. 在controller中调用
1
2
3
4
5
//树的深度
- (void)depthTree{
    NSInteger depth = [BinaryTreeNode depthOfTree:self.rootNode];
    NSLog(@"depth:%ld",depth);
}

查看结果

1
2020-08-31 17:29:49.989752+0800 OC-二叉树[59816:4186549] depth:6

二叉树的宽度

二叉树的 宽度 定义为各层节点数的最大值。

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
/**
 *  二叉树的宽度
 *  @param rootNode 二叉树根节点
 *  @return 二叉树宽度
 */
+ (NSInteger)widthOfTree:(BinaryTreeNode *)rootNode {
    if (!rootNode) {
        return 0;
    }
    
    NSMutableArray * queueArray = [NSMutableArray array]; 
    [queueArray addObject:rootNode]; // 压入根节点
    NSInteger maxWidth = 1; // 最大的宽度，初始化为1（因为已经有根节点）
    NSInteger curWidth = 0; // 当前层的宽度
    
    while (queueArray.count > 0) {
        curWidth = queueArray.count;
        //依次弹出当前层的节点
        for (NSInteger i=0; i<curWidth; i++) {
            BinaryTreeNode * node = [queueArray firstObject];
             // 弹出最前面的节点，仿照队列先进先出原则
            [queueArray removeObjectAtIndex:0];
            // 压入左子数
            if (node.leftNode) {
                [queueArray addObject:node.leftNode];
            }
            // 压入右子树
            if (node.rightNode) {
                [queueArray addObject:node.rightNode];
            }
        }
        // 宽度 = 当前层节点数
        maxWidth = MAX(maxWidth, queueArray.count);
    }
    
    return maxWidth;
}

vc实现

1
2
3
// 二叉树宽度
NSInteger width = [BinaryTreeNode widthOfTree:self.rootNode];
NSLog(@"width-%ld",width);

打印结果

1
2022-11-26 16:21:36.767352+0800 二叉树[4523:170689] width-2

二叉树的所有节点数

递归思想：二叉树所有节点数 = 左子树节点数 + 右子树节点数 + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 *  二叉树的所有节点数
 *
 *  @param rootNode 根节点
 *
 *  @return 所有节点数
 */
// 二叉树所有节点数
+ (NSInteger)numberOfNodesInTree:(BinaryTreeNode *)rootNode{
    if (!rootNode){
        return 0;
    }
    // 总节点数 = 左子树节点数 + 右子树节点数 + 1
    NSInteger totalNode = [self numberOfNodesInTree:rootNode.leftNode] + [self numberOfNodesInTree:rootNode.rightNode] + 1;
    
    return totalNode;
}

vc实现

1
2
3
// 二叉树节点数
NSInteger totalNode = [BinaryTreeNode numberOfNodesInTree:self.rootNode];
NSLog(@"totalNode-%ld",totalNode);

打印结果

1
2022-11-26 16:10:38.371816+0800 二叉树[4369:160462] totalNode-5

二叉树某层中的节点数

1）根节点为空，则节点数为0；

2）层为1，则节点数为1（即根节点）

3）递归思想：二叉树第k层节点数 = 左子树第k-1层节点数 + 右子树第k-1层节点数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 *  二叉树某层中的节点数
 *
 *  @param level    层
 *  @param rootNode 根节点
 *
 *  @return 层中的节点数
 */
// 二叉树某层中的节点数
+ (NSInteger)numberOfNodesOnLevel:(NSInteger)level inTree:(BinaryTreeNode *)rootNode{
    // 根节点不存在 或 level < 0
    if (!rootNode || level < 1) {
            return 0;
        }
        // level = 1，返回1（根节点）
        if (level == 1) {
            return 1;
        }
        // 递归：level层节点数 = 左子树level-1层节点数 + 右子树level-1层节点数
        NSInteger levelNode = [self numberOfNodesOnLevel:level-1 inTree:rootNode.leftNode] + [self numberOfNodesOnLevel:level-1 inTree:rootNode.rightNode];
        return levelNode;
}

vc实现

1
2
3
// 某层节点数
NSInteger levelNode = [BinaryTreeNode numberOfNodesOnLevel:1 inTree:self.rootNode];
NSLog(@"levelNode-%ld",levelNode);

打印结果

1
2022-11-26 16:27:02.360866+0800 二叉树[4593:175705] levelNode-1

二叉树叶子节点数

叶子节点，又叫终端节点，是左右子树都是空的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 *  二叉树叶子节点数
 *
 *  @param rootNode 根节点
 *
 *  @return 叶子节点数
 */
+ (NSInteger)numberOfLeafsInTree:(BinaryTreeNode *)rootNode {
    if (!rootNode) {
        return 0;
    }
    // 左子树和右子树都是空，说明是叶子节点
    if (!rootNode.leftNode && !rootNode.rightNode) {
        return 1;
    }
    // 递归：叶子数 = 左子树叶子数 + 右子树叶子数
    return [self numberOfLeafsInTree:rootNode.leftNode] + [self numberOfLeafsInTree:rootNode.rightNode];
}

二叉树最大距离（二叉树的直径）

二叉树中任意两个节点都有且仅有一条路径，这个路径的长度叫这两个节点的距离。二叉树中所有节点之间的距离的最大值就是二叉树的直径。

有一种解法，把这个最大距离划分了3种情况：

1）这2个节点分别在根节点的左子树和右子树上，他们之间的路径肯定经过根节点，而且他们肯定是根节点左右子树上最远的叶子节点（他们到根节点的距离=左右子树的深度）。

2）这2个节点都在左子树上

3）这2个节点都在右子树上

综上，只要取这3种情况中的最大值，就是二叉树的直径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 *  二叉树最大距离（直径）
 *
 *  @param rootNode 根节点
 *
 *  @return 最大距离
 */
+ (NSInteger)maxDistanceOfTree:(BinaryTreeNode *)rootNode {
    if (!rootNode) {
        return 0;
    }
//    方案一：（递归次数较多，效率较低）
    //分3种情况：
    //1、最远距离经过根节点：距离 = 左子树深度 + 右子树深度
    NSInteger distance = [self depthOfTree:rootNode.leftNode] + [self depthOfTree:rootNode.rightNode];
    //2、最远距离在根节点左子树上，即计算左子树最远距离
    NSInteger disLeft = [self maxDistanceOfTree:rootNode.leftNode];
    //3、最远距离在根节点右子树上，即计算右子树最远距离
    NSInteger disRight = [self maxDistanceOfTree:rootNode.rightNode];
    
    return MAX(MAX(disLeft, disRight), distance);
}

这个方案效率较低，因为计算子树的深度和最远距离是分开递归的，存在重复递归遍历的情况。其实一次递归，就可以分别计算出深度和最远距离，于是有了第二种方案：

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
/**
 *  二叉树最大距离（直径）
 *
 *  @param rootNode 根节点
 *
 *  @return 最大距离
 */
+ (NSInteger)maxDistanceOfTree:(BinaryTreeNode *)rootNode {
    if (!rootNode) {
        return 0;
    }
// 方案2：将计算节点深度和最大距离放到一次递归中计算，方案一是分别单独递归计算深度和最远距离
    TreeNodeProperty *p = [self propertyOfTreeNode:rootNode];
    return p.distance;
}

/**
 *  计算树节点的最大深度和最大距离
 *
 *  @param rootNode 根节点
 *
 *  @return TreeNodeProperty
 */
+ (TreeNodeProperty *)propertyOfTreeNode:(BinaryTreeNode *)rootNode {
    
    if (!rootNode) {
        return nil;
    }
    
    TreeNodeProperty *left = [self propertyOfTreeNode:rootNode.leftNode];
    TreeNodeProperty *right = [self propertyOfTreeNode:rootNode.rightNode];
    TreeNodeProperty *p = [TreeNodeProperty new];
    //节点的深度depth = 左子树深度、右子树深度中最大值+1（+1是因为根节点占了1个depth）
    p.depth = MAX(left.depth, right.depth) + 1;
    //最远距离 = 左子树最远距离、右子树最远距离和横跨左右子树最远距离中最大值
    p.distance = MAX(MAX(left.distance, right.distance), left.depth+right.depth);
    
    return p;
}

二叉树中某个节点到根节点的路径

既是寻路问题，又是查找节点问题。

定义一个存放路径的栈（不是队列了，但是还是用可变数组来实现的）

1）压入根节点，再从左子树中查找（递归进行的），如果未找到，再从右子树中查找，如果也未找到，则弹出根节点，再遍历栈中上一个节点。

2）如果找到，则栈中存放的节点就是路径所经过的节点。

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
/**
 *  二叉树中某个节点到根节点的路径
 *
 *  @param treeNode 节点
 *  @param rootNode 根节点
 *
 *  @return 存放路径节点的数组
 */
+ (NSArray *)pathOfTreeNode:(BinaryTreeNode *)treeNode inTree:(BinaryTreeNode *)rootNode {
    NSMutableArray *pathArray = [NSMutableArray array];
    [self isFoundTreeNode:treeNode inTree:rootNode routePath:pathArray];
    return pathArray;
}

/**
 *  查找某个节点是否在树中
 *
 *  @param treeNode 待查找的节点
 *  @param rootNode 根节点
 *  @param path  根节点到待查找节点的路径
 *
 *  @return YES：找到，NO：未找到
 */
+ (BOOL)isFoundTreeNode:(BinaryTreeNode *)treeNode inTree:(BinaryTreeNode *)rootNode routePath:(NSMutableArray *)path {
    
    if (!rootNode || !treeNode) {
        return NO;
    }
    
    //找到节点
    if (rootNode == treeNode) {
        [path addObject:rootNode];
        return YES;
    }
    //压入根节点，进行递归
    [path addObject:rootNode];
    //先从左子树中查找
    BOOL find = [self isFoundTreeNode:treeNode inTree:rootNode.leftNode routePath:path];
    //未找到，再从右子树查找
    if (!find) {
        find = [self isFoundTreeNode:treeNode inTree:rootNode.rightNode routePath:path];
    }
    //如果2边都没查找到，则弹出此根节点
    if (!find) {
        [path removeLastObject];
    }
    
    return find;
}

二叉树中两个节点最近的公共父节点

首先需要明白，根节点肯定是二叉树中任意两个节点的公共父节点（不一定是最近的），因此二叉树中2个节点的最近公共父节点一定在从根节点到这个节点的路径上。因此我们可以先分别找到从根节点到这2个节点的路径，再从这两个路径中找到最近的公共父节点。

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
/**
 *  二叉树中两个节点最近的公共父节点
 *
 *  @param nodeA    第一个节点
 *  @param nodeB    第二个节点
 *  @param rootNode 二叉树根节点
 *
 *  @return 最近的公共父节点
 */
+ (BinaryTreeNode *)parentOfNode:(BinaryTreeNode *)nodeA andNode:(BinaryTreeNode *)nodeB inTree:(BinaryTreeNode *)rootNode {
    if (!rootNode || !nodeA || !nodeB) {
        return nil;
    }
    if (nodeA == nodeB) {
        return nodeA;
    }
    //从根节点到节点A的路径
    NSArray *pathA = [self pathOfTreeNode:nodeA inTree:rootNode];
    //从根节点到节点B的路径
    NSArray *pathB = [self pathOfTreeNode:nodeB inTree:rootNode];
    //其中一个节点不在树中，则没有公共父节点
    if (pathA.count == 0 || pathB == 0) {
        return nil;
    }
    //从后往前推，查找第一个出现的公共节点
    for (NSInteger i = pathA.count-1; i>=0; i--) {
        for (NSInteger j = pathB.count - 1; j>=0; j--) {
            if ([pathA objectAtIndex:i] == [pathB objectAtIndex:j]) {
                //找到
                return [pathA objectAtIndex:i];
            }
        }
    }
    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
/**
 *  二叉树中两个节点之间的路径
 *
 *  @param nodeA    第一个节点
 *  @param nodeB    第二个节点
 *  @param rootNode 二叉树根节点
 *
 *  @return 两个节点间的路径
 */
+ (NSArray *)pathFromNode:(BinaryTreeNode *)nodeA toNode:(BinaryTreeNode *)nodeB inTree:(BinaryTreeNode *)rootNode {
    if (!rootNode || !nodeA || !nodeB) {
        return nil;
    }
    NSMutableArray *path = [NSMutableArray array];
    if (nodeA == nodeB) {
        [path addObject:nodeA];
        [path addObject:nodeB];
        return path;
    }
    //从根节点到节点A的路径
    NSArray *pathA = [self pathOfTreeNode:nodeA inTree:rootNode];
    //从根节点到节点B的路径
    NSArray *pathB = [self pathOfTreeNode:nodeB inTree:rootNode];
    //其中一个节点不在树中，则没有路径
    if (pathA.count == 0 || pathB == 0) {
        return nil;
    }
    //从后往前推，查找第一个出现的公共节点
    for (NSInteger i = pathA.count-1; i>=0; i--) {
        [path addObject:[pathA objectAtIndex:i]];
        for (NSInteger j = pathB.count - 1; j>=0; j--) {
            //找到公共父节点，则将pathB中后面的节点压入path
            if ([pathA objectAtIndex:i] == [pathB objectAtIndex:j]) {
                j++; //j++是为了避开公共父节点
                while (j<pathB.count) {
                    [path addObject:[pathB objectAtIndex:j]];
                    j++;
                }
                
                return path;
            }
        }
    }
    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
/**
 *  二叉树两个节点之间的距离
 *
 *  @param nodeA    第一个节点
 *  @param nodeB    第二个节点
 *  @param rootNode 二叉树根节点
 *
 *  @return 两个节点间的距离（-1：表示没有找到路径）
 */
+ (NSInteger)distanceFromNode:(BinaryTreeNode *)nodeA toNode:(BinaryTreeNode *)nodeB inTree:(BinaryTreeNode *)rootNode {
    if (!rootNode || !nodeA || !nodeB) {
        return -1;
    }
    if (nodeA == nodeB) {
        return 0;
    }
    //从根节点到节点A的路径
    NSArray *pathA = [self pathOfTreeNode:nodeA inTree:rootNode];
    //从根节点到节点B的路径
    NSArray *pathB = [self pathOfTreeNode:nodeB inTree:rootNode];
    //其中一个节点不在树中，则没有路径
    if (pathA.count == 0 || pathB == 0) {
        return -1;
    }
    //从后往前推，查找第一个出现的公共节点
    for (NSInteger i = pathA.count-1; i>=0; i--) {
        for (NSInteger j = pathB.count - 1; j>=0; j--) {
            //找到公共父节点
            if ([pathA objectAtIndex:i] == [pathB objectAtIndex:j]) {
                //距离=路径节点数-1 （这里要-2，因为公共父节点重复了一次）
                return (pathA.count - i) + (pathB.count - j) - 2;
            }
        }
    }
    return -1;
}

判断二叉树是否完全二叉树

完全二叉树定义为：若设二叉树的高度为h，除第h层外，其它各层的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布。

完全二叉树必须满足2个条件：

1）如果某个节点的右子树不为空，则它的左子树必须不为空

2）如果某个节点的右子树为空，则排在它后面的节点必须没有孩子节点

这里还需要理解“排在它后面的节点”，回头看看层次遍历算法，我们就能知道在层次遍历时，是从上到下从左到右遍历的，先将根节点弹出队列，再压入孩子节点，因此“排在它后面的节点”有2种情况：

1）同层次的后面的节点

2）同层次的前面的节点的孩子节点（因为遍历前面的节点时，会弹出节点，同时将孩子节点压入队列）

通过上面的分析，我们可以设置一个标志位flag，当子树满足完全二叉树时，设置flag=YES。当flag=YES而节点又破坏了完全二叉树的条件，那么它就不是完全二叉树。

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
/**
 *  是否完全二叉树
 *  完全二叉树：若设二叉树的高度为h，除第h层外，其它各层的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布
 *
 *  @param rootNode 根节点
 *
 *  @return YES：是完全二叉树，NO：不是完全二叉树
 */
+ (BOOL)isCompleteBinaryTree:(BinaryTreeNode *)rootNode {
    if (!rootNode) {
        return NO;
    }
    //左子树和右子树都是空，则是完全二叉树
    if (!rootNode.leftNode && !rootNode.rightNode) {
        return YES;
    }
    //左子树是空，右子树不是空，则不是完全二叉树
    if (!rootNode.leftNode && rootNode.rightNode) {
        return NO;
    }
    
    //按层次遍历节点，找到满足完全二叉树的条件：
    //条件1：如果某个节点的右子树不为空，则它的左子树必须不为空
    //条件2：如果某个节点的右子树为空，则排在它后面的节点必须没有孩子节点
    //排在该节点后面的节点有2种：1）同层次的后面的节点 2）同层次的前面的节点的孩子节点（因为遍历前面的节点的时候，会将节点从队列里pop，同时把它的孩子节点push到队列里）
    NSMutableArray *queue = [NSMutableArray array];
    [queue addObject:rootNode];
    BOOL isComplete = NO; //是否已经满足完全二叉树
    while (queue.count > 0) {
        BinaryTreeNode *node = [queue firstObject];
        [queue removeObjectAtIndex:0];
        
        //左子树为空且右子树不为空，则不是完全二叉树
        if (!node.leftNode && node.rightNode) {
            return NO;
        }
        if (isComplete && (node.leftNode || node.rightNode)) {
            //前面的节点已满足完全二叉树,如果还有孩子节点，则不是完全二叉树
            return NO;
        }
        
        //右子树为空，则已经满足完全二叉树
        if (!node.rightNode) {
            isComplete = YES;
        }
        
        //压入
        if (node.leftNode) {
            [queue addObject:node.leftNode];
        }
        if (node.rightNode) {
            [queue addObject:node.rightNode];
        }
    }
    return isComplete;
}

判断二叉树是否满二叉树

满二叉树定义为：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树

满二叉树的一个特性是：叶子数=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
/**
 *  是否满二叉树
 *  满二叉树：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树
 *
 *  @param rootNode 根节点
 *
 *  @return YES：满二叉树，NO：非满二叉树
 */
+ (BOOL)isFullBinaryTree:(BinaryTreeNode *)rootNode {
    if (!rootNode) {
        return NO;
    }
    
    //二叉树深度
    NSInteger depth = [self depthOfTree:rootNode];
    //二叉树叶子节点数
    NSInteger leafNum = [self numberOfLeafsInTree:rootNode];
    
    //满二叉树特性：叶子数=2^(深度-1)
    if (leafNum == pow(2, (depth - 1))) {
        return YES;
    }
    return NO;
}

判断二叉树是否平衡二叉树

平衡二叉树定义为：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树又叫AVL树。

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
/**
 *  是否平衡二叉树
 *  平衡二叉树：即AVL树，它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
 *
 *  @param rootNode 根节点
 *
 *  @return YES：平衡二叉树，NO：非平衡二叉树
 */
+ (BOOL)isAVLBinaryTree:(BinaryTreeNode *)rootNode {
    static NSInteger height;
    if (!rootNode) {
        height = 0;
        return YES;
    }
    if (!rootNode.leftNode && !rootNode.rightNode) {
        height = 1;
        return YES;
    }
    
    BOOL isAVLLeft = [self isAVLBinaryTree:rootNode.leftNode];
    NSInteger heightLeft = height;
    BOOL isAVLRight = [self isAVLBinaryTree:rootNode.rightNode];
    NSInteger heightRight = height;
    
    height = MAX(heightLeft, heightRight)+1;
    
    if (isAVLLeft && isAVLRight && ABS(heightLeft-heightRight) <= 1) {
        return YES;
    }
    return NO;
}

总结

以上就是我目前整理的一些二叉树相关的算法，算法资料和思想都来源于网络，如有错误，欢迎指正！后续如果有新的算法，我也会更新进去。

  • Post title：OC数据结构02：二叉树探索
  • Post author：张建
  • Create time：2020-08-26 16:35:40
  • Post link：https://redefine.ohevan.com/2020/08/26/OC数据结构和算法/OC数据结构02：二叉树探索/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
On this page
OC数据结构02：二叉树探索
  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. 总结