二叉树的那些使用

栏目: 数据库 · 发布时间: 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];
    }
}

裂变式创业

宗毅、小泽 / 机械工业出版社 / 2016-1-1 / 39.84

互联网大潮汹涌来袭，传统企业增长乏力，互联网公司跨界冲击，转型之路迫在眉睫。“转型找死，不转型等死”这一坊间传说让多数企业徘徊不前，不少实体经济面临困境，敢问路在何方？宗毅独创裂变式创业，用人民币投票选总经理，规定自己不投钱不能参与竞选；不相信干股，不使用职业经理人,用金融的方式管理现金流。用商业模式颠覆传统公益，打通南北充电之路；摇身一变成为自媒体，用产品建立社群。自己写故事，自己当导演......一起来看看《裂变式创业》这本书的介绍吧!

码农工具