2023年6月22日发(作者：)

数据结构算法之《前序遍历、中序遍历、后序遍历以及层序遍历》先说下⼏种遍历的规则：1.前序遍历：根节点在前⾯，也就是按照【根节点】-【左孩⼦】-【右孩⼦】的顺序遍历2.中序遍历：根节点在中间，也就是按照【左孩⼦】-【根节点】-【右孩⼦】的顺序遍历3.后序遍历：根节点在最后，也就是按照【左孩⼦】-【右孩⼦】-【根节点】的顺序遍历4.层序遍历：就是按照⼀层⼀层的顺序遍历，也就是先遍历所有的【根节点】，再遍历所有的【孩⼦节点】下⾯是⼀个简单的遍历图⽰：⼆叉树遍历1. 前序，中序，后序这三种遍历都是⽐较简单的遍历⽅式，可以通过递归的⽅式快速完成遍历，这⾥直接上代码：1. 前序遍历-(void)preOrderSortWithResultArr:(NSMutableArray *)resultArr {

if (de == nil) { return; }

[self preOrderSortWithRootNode:de withResultArr:resultArr];}-(void)preOrderSortWithRootNode:(TreeNode *)node withResultArr:(NSMutableArray *)resultArr {

if (node == nil) { return; }

[resultArr addObject:@()]; [self preOrderSortWithRootNode:af withResultArr:resultArr]; [self preOrderSortWithRootNode:eaf withResultArr:resultArr];}2.中序遍历-(void)inOrderSortWithResultArr:(NSMutableArray *)resultArr {

if (de == nil) { return; }

[self inOrderSortWithRootNode:de withResultArr:resultArr];}-(void)inOrderSortWithRootNode:(TreeNode *)node withResultArr:(NSMutableArray *)resultArr {

if (node == nil) { return; }

[self inOrderSortWithRootNode:af withResultArr:resultArr]; [resultArr addObject:@()]; [self inOrderSortWithRootNode:eaf withResultArr:resultArr];}3.后序遍历-(void)postOrderSortWithResultArr:(NSMutableArray *)resultArr {

if (de == nil) { return; }

[self postOrderSortWithRootNode:de withResultArr:resultArr];}-(void)postOrderSortWithRootNode:(TreeNode *)node withResultArr:(NSMutableArray *)resultArr {

if (node == nil) { return; }

[self postOrderSortWithRootNode:af withResultArr:resultArr]; [self postOrderSortWithRootNode:eaf withResultArr:resultArr]; [resultArr addObject:@()];}2. 层序遍历这⾥重点来说下层序遍历，层序遍历不能直接通过节点之间的关系并借助递归来实现。在下⾯的做法中，我们借助了队列（这⾥直接⽤数组表⽰），以及两个标志位（⼀个表⽰当前层的最后⼀个元素，⼀个表⽰下⼀层的最后⼀个元素）来完成层序遍历，下⾯看详细的图解：⽐如，我们要层序遍历下⾯这颗⼆叉树：层序遍历下⾯是实现代码：-(void)levelOrderSortWithResultArr:(NSMutableArray *)resultArr {

NSMutableArray *levelNodes = [NSMutableArray array]; // ⽤来暂存出队的节点 NSMutableArray *queue = [NSMutableArray array]; // ⽤来遍历节点⽤的队列

TreeNode *lastNodeInCurrentLevel = de; // 当前层的最后⼀个节点 TreeNode *lastNodeInNextLevel; // 下⼀层的最后⼀个节点

[queue addObject:de]; // 头节点⼊队

while ( > 0) {

// 1. 队列第⼀个元素出队，并加⼊到暂存数组 TreeNode *first = [queue objectAtIndex:0]; [queue removeObjectAtIndex:0]; [levelNodes addObject:first];

// 2. 把当前出队节点的左右孩⼦⼊队，并更新lastNodeInNextLevel if (af != nil) { [queue addObject:af]; lastNodeInNextLevel = af; } if (eaf != nil) { [queue addObject:eaf]; lastNodeInNextLevel = eaf; }

// 3. 如果出队的元素是它所在层的最后⼀个元素，则需要把暂存数组中的数据提交到结果中，并重新初始化来装下⼀层的数据 // 同时表⽰它所在层所有节点的孩⼦已经⼊队，下⼀层的最后⼀个节点也确定下来了 // 这时候把下⼀层就变成当前层，之前的lastNodeInNextLevel就变成新的当前层的最后节点了 if (first == lastNodeInCurrentLevel) {

NSArray *resultOfThisLevel = [levelNodes copy]; [resultArr addObject:resultOfThisLevel]; [levelNodes removeAllObjects];

lastNodeInCurrentLevel = lastNodeInNextLevel; lastNodeInNextLevel = nil; } }}