二叉树的那些使用

栏目: 数据库 · 发布时间: 7年前

内容简介：二叉树的那些使用

在计算机科学中，二叉树（英语：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，并且左右两个子树都是一棵平衡二叉树。

树的结构

#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 （称为后序遍历）。

先序遍历

+ (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];
}

中序遍历

+ (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];
}

后序遍历

+ (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);
    }
}

广度优先遍历(Breadth First Search)

从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。

按照从上到下、从左到右的次序进行遍历。先遍历完一层，再遍历下一层。

+ (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]; //压入右节点
        }
    }
}

深度优先遍历(Depth First Search)

DFS是搜索算法的一种。它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。

当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。

如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

+ (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];
}

树的翻转

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

+ (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;
}

树的查找

+ (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];
    }
}

Kafka技术内幕

郑奇煌 / 人民邮电出版社 / 2017-11 / 119.00元

Kafka自LinkedIn开源以来就以高性能、高吞吐量、分布式的特性著称，本书以0.10版本的源码为基础，深入分析了Kafka的设计与实现，包括生产者和消费者的消息处理流程，新旧消费者不同的设计方式，存储层的实现，协调者和控制器如何确保Kafka集群的分布式和容错特性，两种同步集群工具MirrorMaker和uReplicator，流处理的两种API以及Kafka的一些高级特性等。一起来看看《Kafka技术内幕》这本书的介绍吧!

码农工具