二叉树的那些使用

Posted on In

在计算机科学中，二叉树（英语：Binary tree）是每个节点最多只有两个分支(不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”和“右子树”。二叉树的分支具有左右次序，不能颠倒。

二叉树的第i层至多拥有 2^(i-1) 个节点数；深度为k的二叉树至多总共有 2^(k+1) - 1 个节点数，而总计拥有节点数匹配的，称为“满二叉树”；深度为k有n个节点的二叉树，当且仅当其中的每一节点，都可以和同样深度k的满二叉树，序号为1到n的节点一对一对应时，称为“完全二叉树”。对任何一棵非空的二叉树T，如果其叶片(终端节点)数为n0，分支度为2的节点数为n2，则n0 = n2 + 1。

与普通树不同，普通树的节点个数至少为1，而二叉树的节点个数可以为0；普通树节点的最大分支度没有限制，而二叉树节点的最大分支度为2；普通树的节点无左、右次序之分，而二叉树的节点有左、右次序之分。

二叉树通常作为数据结构应用，典型用法是对节点定义一个标记函数，将一些值与每个节点相关系。这样标记的二叉树就可以实现二叉查找树和二元堆积，并应用于高效率的搜索和排序。

相对于普通二叉树，还有一些特殊二叉树，它们诞生于特殊的场景需求。例如，二叉搜索树就是因搜索需求而诞生的一种特殊的树。

具体可以参见
《聊聊「二叉搜索树」的那些事儿》

本文初衷是因为Homebrew 的作者@Max Howell的一条twitter

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

类型

(1)完全二叉树

若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的节点数都达到最大个数，第h层有叶子节点，并且叶子节点都是从左到右依次排布，这就是完全二叉树。

(2)满二叉树

除了叶节点外每一个节点都有左右子叶且叶子节点都处在最底层的二叉树。

(3)平衡二叉树

平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

相关术语

树的节点：包含一个数据元素及若干指向子树的分支。

孩子节点：节点的子树的根称为该节点的孩子。

双亲节点：B 节点是A 节点的孩子，则A节点是B 节点的双亲。

兄弟节点：同一双亲的孩子节点；

堂兄节点：同一层上节点。

祖先节点: 从根到该节点的所经分支上的所有节点。

子孙节点：以某节点为根的子树中任一节点都称为该节点的子孙。

节点层：根节点的层定义为1；根的孩子为第二层节点，依此类推。

树的深度：树中最大的节点层。

节点的度：节点子树的个数。

树的度： 树中最大的节点度。

叶子节点：也叫终端节点，是度为 0 的节点。

分支节点：度不为0的节点。

有序树：子树有序的树，如：家族树。

无序树：不考虑子树的顺序。

树的结构

1
2
3
4
5
6
7
8
9
10
11
12
13
#import <Foundation/Foundation.h>

/** 二叉树节点 */
@interface DDBinaryTreeNode : NSObject

/** 值 */
@property (nonatomic, assign) NSInteger value;
/** 左节点 */
@property (nonatomic, strong) DDBinaryTreeNode *leftNode;
/** 右节点 */
@property (nonatomic, strong) DDBinaryTreeNode *rightNode;

@end

树的遍历

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有节点，使每一个节点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个节点转换成为一个线性序列来表示。

设L、D、R分别表示遍历左子树、访问根节点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR（称为先序遍历），LDR（称为中序遍历），LRD （称为后序遍历）。

先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
+ (void)preOrderTraverseTree:(DDBinaryTreeNode *)rootNode handler:(void(^)(DDBinaryTreeNode *treeNode))handler {
    if (!rootNode) {
        return;
    }
    
    if (handler) {
        handler(rootNode);
    }
    [self preOrderTraverseTree:rootNode.leftNode handler:handler];
    [self preOrderTraverseTree:rootNode.rightNode handler:handler];
}

中序遍历

1
2
3
4
5
6
7
8
9
10
11
+ (void)inOrderTraverseTree:(DDBinaryTreeNode *)rootNode handler:(void (^)(DDBinaryTreeNode *treeNode))handler
{
    if (!rootNode) {
        return;
    }
    [self inOrderTraverseTree:rootNode.leftNode handler:handler];
    if (handler) {
        handler(rootNode);
    }
    [self inOrderTraverseTree:rootNode.rightNode handler:handler];
}

后序遍历

1
2
3
4
5
6
7
8
9
10
+ (void)postOrderTraverseTree:(DDBinaryTreeNode *)rootNode handler:(void(^)(DDBinaryTreeNode *treeNode))handler {
    if (!rootNode) {
        return;
    }
    [self postOrderTraverseTree:rootNode.leftNode handler:handler];
    [self postOrderTraverseTree:rootNode.rightNode handler:handler];
    if (handler) {
        handler(rootNode);
    }
}

从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。
按照从上到下、从左到右的次序进行遍历。先遍历完一层，再遍历下一层。

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

DFS是搜索算法的一种。它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。
当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。
如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
+ (void)depthTraverseTree:(DDBinaryTreeNode *)rootNode handler:(void(^)(DDBinaryTreeNode *treeNode))handler
{
    if (!rootNode) {
        return;
    }
    
    if (handler) {
        handler(rootNode);
    }
    
    [self depthTraverseTree:rootNode.leftNode handler:handler];
    [self depthTraverseTree:rootNode.rightNode handler:handler];
}

树的翻转

翻转二叉树，又叫求二叉树的镜像，就是把二叉树的左右子树对调。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
+ (DDBinaryTreeNode *)invertBinaryTree:(DDBinaryTreeNode *)rootNode {
    if (!rootNode) {
        return nil;
    }
    if (!rootNode.leftNode && !rootNode.rightNode) {
        return rootNode;
    }
    [self invertBinaryTree:rootNode.leftNode];
    [self invertBinaryTree:rootNode.rightNode];
    DDBinaryTreeNode *tempNode = rootNode.leftNode;
    rootNode.leftNode = rootNode.rightNode;
    rootNode.rightNode = tempNode;
    return rootNode;
}

树的查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
+ (DDBinaryTreeNode *)searchTreeNodeWithValue:(NSInteger)value inTree:(DDBinaryTreeNode *)rootNode
{
    if (!rootNode) {
        return nil;
    }
    
    if (rootNode.value == value) {
        return rootNode;
    }
    
    if (value < rootNode.value) {
        return [DDBinarySearchTreeHandler searchTreeNodeWithValue:value inTree:rootNode.leftNode];
    } else {
        return [DDBinarySearchTreeHandler searchTreeNodeWithValue:value inTree:rootNode.rightNode];
    }
}

相关链接：
《百度的校园招聘面试经历》

《你会翻转二叉树吗》

写在最后

欢迎大家加入移动开发交流Q群交流讨论，Q群号：811237468

Q811237468