数据结构与算法 - 二叉树

发表于 | 分类于

在计算机科学中，二叉树(Binary Tree)是包含n个节点的有限集合，该集合或者为空集（此时，二叉树称为空树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

前文

本文主要讲述了对二叉排序树的创建及其它操作，二叉排序树具有以下几个特点：

1
2
3
4
1、若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2、若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3、任意节点的左、右子树也分别为二叉查找树；
4、没有键值相等的节点。

接下来我们通过用OC代码实现的方式完成对二叉排序树的一些基础操作，其中主要就是考察我们的递归思想。
首先我们以二叉树的节点为一个类创建一个类，这个类拥有两个属性，分别是左节点和右节点。如下所示：

1
2
3
4
@interface DyBinaryTreeNode : NSObject

@property (nonatomic, strong) DyBinaryTreeNode *leftNode;
@property (nonatomic, strong) DyBinaryTreeNode *rightNode;

接着，我们便可以依次定义并实现其操作方法了。

0x01 创建二叉排序树

1、创建二叉树
1
2
3
4
5
6
7
8
9
10
11
12
/
 *  @param values 数组
 *  @return 二叉树根节点
 */
+ (DyBinaryTreeNode *)createTreeWithValues:(NSArray *)values {
    DyBinaryTreeNode *root = nil;
    for (NSInteger i=0; i<values.count; i++) {
        NSInteger value = [(NSNumber *)[values objectAtIndex:i] integerValue];
        root = [DyBinaryTreeNode addTreeNode:root value:value];
    }
    return root;
}

我们通过以下方法调用：

1
2
3
NSArray *arr = [NSArray arrayWithObjects:@(7),@(6),@(3),@(2),@(1),@(9),@(10),@(12),@(14),@(4),@(15),nil];
DyBinaryTreeNode *tree = [DyBinaryTreeNode new];
tree = [DyBinaryTreeNode createTreeWithValues:arr];

会生成如下图所示的二叉排序树：

2、获取某个位置的节点（层序）

大致思路
1、将根节点加到队列中，当队列有元素时循环。
2、循环一次将队列的第一个元素出队列，index-1
3、当index=0时返回此时的根节点。
4、遍历队列第一个元素(根节点)的左节点和右节点，加到队列中。

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
 /*  @param index    按层次遍历树时的位置(从0开始算)
 *  @param rootNode 树根节点
 *  @return 节点
 */
+ (DyBinaryTreeNode *)treeNodeAtIndex:(NSInteger)index inTree:(DyBinaryTreeNode *)rootNode {
    //按层次遍历
    if (!rootNode || index < 0) {
        return nil;
    }
    //数组当成队列
    NSMutableArray *queueArray = [NSMutableArray array];
    //压入根节点
    [queueArray addObject:rootNode];
    while (queueArray.count > 0) {
        DyBinaryTreeNode *node = [queueArray firstObject];
        if (index == 0) {//返回根节点。
            return node;
        }
        //弹出最前面的节点，仿照队列先进先出原则
        [queueArray removeObjectAtIndex:0];
        //移除节点，index减少
        index--;
        if (node.leftNode) {
            [queueArray addObject:node.leftNode]; //压入左节点
        }
        if (node.rightNode) {
            [queueArray addObject:node.rightNode]; //压入右节点
        }
    }
    //层次遍历完，仍然没有找到位置，返回nil
    return nil;
}

调用当index==8时，打印的值为1。

1
2
DyBinaryTreeNode *tree1 = [DyBinaryTreeNode treeNodeAtIndex:8 inTree:tree];
NSLog(@"节点值为==%ld\n",tree1.value);

0x02 二叉树遍历

分为先序遍历、中序遍历、后序遍历、层序遍历。
先、中、后主要是指遍历根的顺序，如果先遍历根便是先序，其它类似。左节点和右节点的遍历顺序固定(先左后右)。
层序遍历：从上至下，从左至右依次遍历。
可参考wiki的树的遍历

1、先序遍历

先访问根，再遍历左子树，再遍历右子树。典型的递归思想。
通过block，依次将遍历到的node值回调回去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/ *  
 根-左-右
@param rootNode 根节点
 *  @param handler  访问节点处理函数
 */
+ (void)preOrderTraverseTree:(DyBinaryTreeNode *)rootNode handler:(void(^)(DyBinaryTreeNode *treeNode))handler {
    if (rootNode) {
        if (handler) {
            handler(rootNode);//根
        }
        [DyBinaryTreeNode preOrderTraverseTree:rootNode.leftNode handler:handler];//左
        [DyBinaryTreeNode preOrderTraverseTree:rootNode.rightNode handler:handler];//右
    }
}
2、中序遍历

先遍历左子树，再访问根，再遍历右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 *  左 根 右
 *  @param rootNode 根节点
 *  @param handler  访问节点处理函数
 */
+ (void)inOrderTraverseTree:(DyBinaryTreeNode *)rootNode handler:(void(^)  (DyBinaryTreeNode *treeNode))handler {
    if (rootNode) {
        [DyBinaryTreeNode inOrderTraverseTree:rootNode.leftNode handler:handler];//左
        if (handler) {
            handler(rootNode);//中
        }
        [DyBinaryTreeNode inOrderTraverseTree:rootNode.rightNode handler:handler];//右
    }
}
3、后序遍历

先遍历左子树，再遍历右子树，再访问根

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 *  @param rootNode 根节点
 *  @param handler  访问节点处理函数
 */
+ (void)postOrderTraverseTree:(DyBinaryTreeNode *)rootNode handler:(void(^)(DyBinaryTreeNode *treeNode))handler {
    if (rootNode) {
        [DyBinaryTreeNode postOrderTraverseTree:rootNode.leftNode handler:handler];
        [DyBinaryTreeNode postOrderTraverseTree:rootNode.rightNode handler:handler];
        if (handler) {
            handler(rootNode);
        }
    }
}

以上三种遍历方式依次打印为：

1
2
3
先序遍历结果：7,6,3,2,1,4,9,10,12,14,15
中序遍历结果：1,2,3,4,6,7,9,10,12,14,15
后序遍历结果：1,2,4,3,6,15,14,12,10,9,7
3、层序遍历

同上根据index获取节点的值的思想一样。
通过数组模拟队列，进行遍历操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
+ (void)levelTraverseTree:(DyBinaryTreeNode *)rootNode handler:(void(^)(DyBinaryTreeNode *treeNode))handler {
    if (!rootNode) {
        return;
    }
    NSMutableArray *queueArray = [NSMutableArray array]; //数组当成队列
    [queueArray addObject:rootNode]; //压入根节点
    while (queueArray.count > 0) {
        DyBinaryTreeNode *node = [queueArray firstObject];
        if (handler) {
            handler(node);
        }
        [queueArray removeObjectAtIndex:0]; //弹出最前面的节点，仿照队列先进先 出原则
        if (node.leftNode) {
            [queueArray addObject:node.leftNode]; //压入左节点
        }
        if (node.rightNode) {
            [queueArray addObject:node.rightNode]; //压入右节点
        }
    }
}

0x03 获取二叉树的属性

1、获取二叉树的深度

二叉树的深度
从根节点到叶子节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度包含的节点数为树的深度。
可以理解为二叉树有多少层。

递归思想：二叉树的深度 = MAX(左子树深度，右子树深度)+1
1:根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
 *  @param rootNode 二叉树根节点
 *
 *  @return 二叉树的深度
 */
+ (NSInteger)depthOfTree:(DyBinaryTreeNode *)rootNode {
    if (!rootNode) {
        return 0;
    }
    if (!rootNode.leftNode && !rootNode.rightNode) {
        return 1;
    }
    
    //左子树深度
    NSInteger leftDepth = [DyBinaryTreeNode depthOfTree:rootNode.leftNode];
    //右子树深度
    NSInteger rightDepth = [DyBinaryTreeNode depthOfTree:rootNode.rightNode];
    
    return MAX(leftDepth, rightDepth) + 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
/*
 *  @param rootNode 二叉树根节点
 *
 *  @return 二叉树宽度
 */
+ (NSInteger)widthOfTree:(DyBinaryTreeNode *)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++) {
            DyBinaryTreeNode *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;
}
3、获取二叉树的节点数

递归思想：节点数=左子树节点数+右子树节点数+1（根节点）

1
2
3
4
5
6
7
+ (NSInteger)numberOfNodesInTree:(DyBinaryTreeNode *)rootNode {
    if (!rootNode) {
        return 0;
    }
    //节点数=左子树节点数+右子树节点数+1（根节点）
    return [DyBinaryTreeNode numberOfNodesInTree:rootNode.leftNode] + [DyBinaryTreeNode numberOfNodesInTree:rootNode.rightNode] + 1;
}
4、获取二叉树某一层的节点数

递归思想：level层节点数 = 左子树level-1层节点数+右子树level-1层节点数

1
2
3
4
5
6
7
8
9
10
+ (NSInteger)numberOfNodesOnLevel:(NSInteger)level inTree:(DyBinaryTreeNode *)rootNode {
    if (!rootNode || level < 1) { //根节点不存在或者level<0
        return 0;
    }
    if (level == 1) { //level=1，返回1（根节点）
        return 1;
    }
    //递归：level层节点数 = 左子树level-1层节点数+右子树level-1层节点数
    return [DyBinaryTreeNode numberOfNodesOnLevel:level-1 inTree:rootNode.leftNode] + [DyBinaryTreeNode numberOfNodesOnLevel:level-1 inTree:rootNode.rightNode];
}
5、获取叶子节点数

叶子节点：左子树和右子树都是空的节点。
递归思想：叶子数 = 左子树叶子数 + 右子树叶子数

1
2
3
4
5
6
7
8
9
10
11
+ (NSInteger)numberOfLeafsInTree:(DyBinaryTreeNode *)rootNode {
    if (!rootNode) {
        return 0;
    }
    //左子树和右子树都是空，说明是叶子节点
    if (!rootNode.leftNode && !rootNode.rightNode) {
        return 1;
    }
    //递归：叶子数 = 左子树叶子数 + 右子树叶子数
    return [DyBinaryTreeNode numberOfLeafsInTree:rootNode.leftNode] + [DyBinaryTreeNode numberOfLeafsInTree:rootNode.rightNode];
}
6、获取二叉树的最大直径

二叉树看成一个图，父子节点之间的连线看成是双向的，定义“距离”为两个节点之间的边数。

递归思想：
分为三种情况
1、最远距离经过根节点：距离 = 左子树深度 + 右子树深度
2、最远距离在根节点左子树上，即计算左子树最远距离
3、最远距离在根节点右子树上，即计算右子树最远距离

1
2
3
4
5
6
7
8
9
10
11
+ (NSInteger)maxDistanceOfTree:(DyBinaryTreeNode *)rootNode {
    if (!rootNode) {
        return 0;
    }
    //方案一：（递归次数较多，效率较低）
    NSInteger distance = [DyBinaryTreeNode depthOfTree:rootNode.leftNode] + [DyBinaryTreeNode depthOfTree:rootNode.rightNode];
    NSInteger disLeft = [DyBinaryTreeNode maxDistanceOfTree:rootNode.leftNode];
    NSInteger disRight = [DyBinaryTreeNode maxDistanceOfTree:rootNode.rightNode];
    
    return MAX(MAX(disLeft, disRight), distance);
}

0x04 翻转二叉树

又叫：二叉树的镜像。交换节点的左节点和右节点。

1、递归翻转

递归思想：先交换当前节点的左右节点，再递归调用去翻转以左右节点为根节点的二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
+ (DyBinaryTreeNode *)invertBinaryTree:(DyBinaryTreeNode *)rootNode {
    if (!rootNode) {
        return nil;
    }
    if (!rootNode.leftNode && !rootNode.rightNode) {
        return rootNode;
    }
    //交换当前节点的左右节点。
    DyBinaryTreeNode *tempNode = rootNode.leftNode;
    rootNode.leftNode = rootNode.rightNode;
    rootNode.rightNode = tempNode;
    
    //递归交换左右子节点
    [DyBinaryTreeNode invertBinaryTree:rootNode.leftNode];
    [DyBinaryTreeNode invertBinaryTree:rootNode.rightNode];
    
    return rootNode;
}
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
/**
 * 非递归方式翻转
 */
+ (DyBinaryTreeNode *)invertBinaryTreeNot:(DyBinaryTreeNode *)rootNode {
    if (!rootNode) {  return nil; }
    if (!rootNode.leftNode && !rootNode.rightNode) {  return rootNode; }
    
    NSMutableArray *queueArray = [NSMutableArray array]; //数组当成队列
    [queueArray addObject:rootNode]; //压入根节点
    while (queueArray.count > 0) {
        DyBinaryTreeNode *node = [queueArray firstObject];
        [queueArray removeObjectAtIndex:0]; //弹出最前面的节点，仿照队列先进先出原则
        
        DyBinaryTreeNode *pLeft = node.leftNode;
        node.leftNode = node.rightNode;
        node.rightNode = pLeft;
        
        if (node.leftNode) {
            [queueArray addObject:node.leftNode];
        }
        if (node.rightNode) {
            [queueArray addObject:node.rightNode];
        }
        
    }
    return rootNode;
}

备注

关于二叉树的基本算法先介绍到此处，后续会补充更多关于二叉树操作的一些算法。