数据结构&算法之《前序遍历、中序遍历、后序遍历以及层序遍历》

先说下几种遍历的规则：

1.前序遍历：根节点在前面，也就是按照【根节点】-【左孩子】-【右孩子】的顺序遍历
2.中序遍历：根节点在中间，也就是按照【左孩子】-【根节点】-【右孩子】的顺序遍历
3.后序遍历：根节点在最后，也就是按照【左孩子】-【右孩子】-【根节点】的顺序遍历
4.层序遍历：就是按照一层一层的顺序遍历，也就是先遍历所有的【根节点】，再遍历所有的【孩子节点】

下面是一个简单的遍历图示：

二叉树遍历

1. 前序，中序，后序

这三种遍历都是比较简单的遍历方式，可以通过递归的方式快速完成遍历，这里直接上代码：

1. 前序遍历

-(void)preOrderSortWithResultArr:(NSMutableArray *)resultArr {
    
    if (self.rootNode == nil) {
        return;
    }
    
    [self preOrderSortWithRootNode:self.rootNode withResultArr:resultArr];
}

-(void)preOrderSortWithRootNode:(TreeNode *)node withResultArr:(NSMutableArray *)resultArr {
    
    if (node == nil) {
        return;
    }
    
    [resultArr addObject:@(node.value)];
    [self preOrderSortWithRootNode:node.leftLeaf withResultArr:resultArr];
    [self preOrderSortWithRootNode:node.rightLeaf withResultArr:resultArr];
}

2.中序遍历

-(void)inOrderSortWithResultArr:(NSMutableArray *)resultArr {
    
    if (self.rootNode == nil) {
        return;
    }
    
    [self inOrderSortWithRootNode:self.rootNode withResultArr:resultArr];
}

-(void)inOrderSortWithRootNode:(TreeNode *)node withResultArr:(NSMutableArray *)resultArr {
    
    if (node == nil) {
        return;
    }
    
    [self inOrderSortWithRootNode:node.leftLeaf withResultArr:resultArr];
    [resultArr addObject:@(node.value)];
    [self inOrderSortWithRootNode:node.rightLeaf withResultArr:resultArr];
}

3.后序遍历

-(void)postOrderSortWithResultArr:(NSMutableArray *)resultArr {
    
    if (self.rootNode == nil) {
        return;
    }
    
    [self postOrderSortWithRootNode:self.rootNode withResultArr:resultArr];
}

-(void)postOrderSortWithRootNode:(TreeNode *)node withResultArr:(NSMutableArray *)resultArr {
    
    if (node == nil) {
        return;
    }
    
    [self postOrderSortWithRootNode:node.leftLeaf withResultArr:resultArr];
    [self postOrderSortWithRootNode:node.rightLeaf withResultArr:resultArr];
    [resultArr addObject:@(node.value)];
}

2. 层序遍历

这里重点来说下层序遍历，层序遍历不能直接通过节点之间的关系并借助递归来实现。在下面的做法中，我们借助了队列（这里直接用数组表示），以及两个标志位（一个表示当前层的最后一个元素，一个表示下一层的最后一个元素）来完成层序遍历，下面看详细的图解：

比如，我们要层序遍历下面这颗二叉树：

层序遍历

下面是实现代码：

-(void)levelOrderSortWithResultArr:(NSMutableArray *)resultArr {
    
    NSMutableArray *levelNodes = [NSMutableArray array]; // 用来暂存出队的节点
    NSMutableArray *queue = [NSMutableArray array]; // 用来遍历节点用的队列
    
    
    TreeNode *lastNodeInCurrentLevel = self.rootNode; // 当前层的最后一个节点
    TreeNode *lastNodeInNextLevel; // 下一层的最后一个节点
    
    [queue addObject:self.rootNode]; // 头节点入队
    
    while (queue.count > 0) {
        
        // 1. 队列第一个元素出队，并加入到暂存数组
        TreeNode *first = [queue objectAtIndex:0];
        [queue removeObjectAtIndex:0];
        [levelNodes addObject:first];
        
        // 2. 把当前出队节点的左右孩子入队，并更新lastNodeInNextLevel
        if (first.leftLeaf != nil) {
            [queue addObject:first.leftLeaf];
            lastNodeInNextLevel = first.leftLeaf;
        }
        if (first.rightLeaf != nil) {
            [queue addObject:first.rightLeaf];
            lastNodeInNextLevel = first.rightLeaf;
        }
        
        // 3. 如果出队的元素是它所在层的最后一个元素，则需要把暂存数组中的数据提交到结果中，并重新初始化来装下一层的数据
        // 同时表示它所在层所有节点的孩子已经入队，下一层的最后一个节点也确定下来了
        // 这时候把下一层就变成当前层，之前的lastNodeInNextLevel就变成新的当前层的最后节点了
        if (first == lastNodeInCurrentLevel) {
            
            NSArray *resultOfThisLevel = [levelNodes copy];
            [resultArr addObject:resultOfThisLevel];
            [levelNodes removeAllObjects];
            
            lastNodeInCurrentLevel = lastNodeInNextLevel;
            lastNodeInNextLevel = nil;
        }
    }
}