数据结构之树

一个形象的例子

比如我们的一个View的层级结构，如果这个层级结构很复杂的话，你可以想象下是不是和树这个数据结构很像。

常用的树

• 二叉树，它是分支因子值为2，也就是有左右两个分支。
• 二叉搜索树，一种专门用于查找操作的二叉树

树的遍历算法

• 前序遍历

在先序遍历中，我们先访问根结点，然后递归使用先序遍历访问左子树，再递归使用先序遍历访问右子树
根节点->左子树->右子树

• 中序遍历

在中序遍历中，我们递归使用中序遍历访问左子树，然后访问根结点，最后再递归使用中序遍历访问右子树
左子树->根节点->右子树

• 后序遍历

在后序遍历中，我们先递归使用后序遍历访问左子树和右子树，最后访问根结点
左子树->右子树->根结点

• 层级遍历

从树的root开始，从上到下从从左到右遍历整个树的结点

注意：前三种遍历是按照深度优先遍历的策略。而层级遍历是按照广度优先遍历的策略

看图想象下遍历的方法

树的平衡

• 所有的叶子结点都在同一层，或者所有叶子结点都在最后两层，且倒数第二层是满的，则这个个树就是平衡的。

• 如果最后一层的叶子结点靠左这叫做左平衡树，应用实现堆和优先级队列，这部分之前已经实现。下图左平衡二叉树：

  
  

注意：为什么特别强调树的平衡呢？因为这树的高度对搜索树的性能影响巨大，后面会介绍。

二叉树代码实现

1. 初始化一个结点为根结点的树
2. 想象下，我们的一个树的叶子结点，除了有父结点还有左右孩子结点，然后还有一个表达的值。
3. 然后我们需要在某个父结点插入左或者右孩子结点
4. 然后利用递归遍历来实现前中后序遍历
5. 利用队列先进先出的特性层级遍历

结点头文件

@interface DSTreeNode : NSObject

@property (nonatomic, strong) NSObject   *object;
@property (nonatomic, strong) DSTreeNode *leftChild;
@property (nonatomic, strong) DSTreeNode *rightChild;
@property (nonatomic, strong) DSTreeNode *parent;
@property (nonatomic, assign) SEL         compareSelector;



//是否是左还是结点
- (BOOL)isLeftChildOfParent;


@end

二叉树头文件

@property (nonatomic, strong) DSTreeNode *root;

- (instancetype)initWithObject:(NSObject *)object;
- (BOOL)insertNode:(DSTreeNode *)node parent:(DSTreeNode *)parent isLeftChild:(BOOL)value;
- (DSTreeNode *)find:(NSObject *)object;

- (void)preOrderTraversal;
- (void)inOrderTraversal;
- (void)postOrderTraversal;
- (void)levelOrderTraversal;

二叉树实现文件

//初始化根结点
- (instancetype)initWithObject:(NSObject *)object
{
    if (self = [super init]) {
        _root            = [[DSTreeNode alloc] init];
        self.root.object = object;
    }
    
    return self;
}

//插入结点
- (BOOL)insertNode:(DSTreeNode *)node parent:(DSTreeNode *)parent isLeftChild:(BOOL)value
{
    //如果插入的是左孩子结点并且左孩子结点不存在可以插入
    if (value == true && parent.leftChild == nil) {
    //插入的结点父结点是parent
        node.parent = parent;
        //父结点的左孩子结点是当前结点
        parent.leftChild = node;
    }
    //否则插入的是右孩子结点
    else if (parent.rightChild == nil) {
        node.parent = parent;
        parent.rightChild = node;
    }
    //如果某个结点的左右孩子结点都存在结束 并提示错误
    else {
        NSAssert(parent.leftChild != nil || parent.rightChild != nil, @"Can't insert into parent node!");
        return false;
    }
    return true;
}

//根据某个值查询这个结点是否在树中并返回
- (DSTreeNode *)find:(NSObject *)object
{
    //利用队列先进先出特性遍历每个结点
    DSQueue*queue = [[DSQueue alloc] init];
    [queue enqueue:self.root];
    DSTreeNode *node;
    //注意这个遍历的顺序是层级遍历顺序
    while (![queue isEmpty]) {
        node = [queue dequeue];
        if ([node.object isEqualTo:object]) {
            return node;
        }
        if (node.leftChild) {
            [queue enqueue:node.leftChild];
        }
        if (node.rightChild) {
            [queue enqueue:node.rightChild];
        }
    }
    return nil;
}

//如果当前根结点存在则前序遍历这个树
- (void)preOrderTraversal
{
    if (self.root) {
        [DSBinaryTree preOrderTraversalRecursive:self.root];
    }
}

//递归的遍历并打印树 顺序是根 左 右
+ (void)preOrderTraversalRecursive:(DSTreeNode *)node
{
    if (node) {
        NSLog(@"%@",node.object);
        [DSBinaryTree preOrderTraversalRecursive:node.leftChild];
        [DSBinaryTree preOrderTraversalRecursive:node.rightChild];
    }
}

- (void)inOrderTraversal
{
    if (self.root) {
        [DSBinaryTree inOrderTraversalRecursive:self.root];
    }
}


+ (void)inOrderTraversalRecursive:(DSTreeNode *)node
{
    if (node) {
        [DSBinaryTree preOrderTraversalRecursive:node.leftChild];
        NSLog(@"%@",node.object);
        [DSBinaryTree preOrderTraversalRecursive:node.rightChild];
    }
}

- (void)postOrderTraversal
{
    if (self.root) {
        [DSBinaryTree postOrderTraversalRecursive:self.root];
    }
}


+ (void)postOrderTraversalRecursive:(DSTreeNode *)node
{
    if (node) {
        [DSBinaryTree postOrderTraversalRecursive:node.leftChild];
        [DSBinaryTree postOrderTraversalRecursive:node.rightChild];
        NSLog(@"%@",node.object);
    }
}

//层级遍历的思路和上面查找的思路一样
- (void)levelOrderTraversal
{
    if (self.root) {
        DSQueue *queue = [[DSQueue alloc] init];
        [queue enqueue:self.root];
        
        while (![queue isEmpty]) {
            DSTreeNode *currentNode = [queue dequeue];
            if (currentNode.leftChild) {
                [queue enqueue:currentNode.leftChild];
            }
            if (currentNode.rightChild) {
                [queue enqueue:currentNode.rightChild];
            }
            NSLog(@"%@", currentNode.object);
        }
    }
}

注意：思路都下载注释里了，后面介绍二叉搜索树

代码：

https://github.com/renmoqiqi/DSBinaryTree

参考链接：

https://github.com/raywenderlich/swift-algorithm-club/tree/master/Binary%20Tree
https://github.com/EvgenyKarkan/EKAlgorithms/tree/master/EKAlgorithms/Data%20Structures/BinaryTree
https://www.jianshu.com/p/473090b9490d