二叉树有前序遍历，中序遍历和后序遍历三种。主要需要记住顺序：

• 前序遍历 - 根->左->右
• 中序遍历 - 左->根->右
• 后序遍历 - 左->右->根

数结点定义:

#import <Foundation/Foundation.h>
// 树节点
@interface NSBinaryTreeNode : NSObject
// 值
@property (nonatomic, assign) int value;
// 左节点
@property (nonatomic, strong) NSBinaryTreeNode *left;
// 右节点
@property (nonatomic, strong) NSBinaryTreeNode *right;
@end

递归实现方法:

递归前序遍历:

// 递归 前序 遍历 树
void preoder_traversal_iteratively_recursion (NSBinaryTreeNode *root) {

    if (root != nil) {
        printf("%d ", root.value);
        preoder_traversal_iteratively_recursion(root.left);
        preoder_traversal_iteratively_recursion(root.right);
    }
}

递归中序遍历:

// 递归中序遍历
void inorder_traversal_iteratively_recursion (NSBinaryTreeNode *root) {
    
    if (root != nil) {
        inorder_traversal_iteratively_recursion(root.left);
        printf("%d ", root.value);
        inorder_traversal_iteratively_recursion(root.right);
    }
}

递归后序遍历:

// 递归 后序遍历
void postorder_traversal_iteratively_recursion (NSBinaryTreeNode *root) {
    
    if (root != nil) {
        postorder_traversal_iteratively_recursion(root.left);
        postorder_traversal_iteratively_recursion(root.right);
        printf("%d ", root.value);
    }
}

非递归版本：

思路:

• 首先我们需要一个栈NSCustomStack来模拟递归时的函数调用。对于三种遍历，我们都使用push当前节点->push左子树->pop左子树->push右子树->pop右子树的方式。但是输出时机会有所不同。

• 对于前序遍历来说，每次访问到一个节点就cout；

• 对于中序遍历来说，每次将右子节点进栈时，把当前节点输出；

• 对于后序遍历来说，每次pop的时候输出。

• 另外我们还需要一个previousTreeNode指针来存放上一个pop出去的节点。

如果当前节点的左右节点都不是上一个pop的节点，那么我们将左子节点入栈；

如果当前节点的左节点是上一个pop的节点，但右节点不是，那么就把右子节点入栈；

否则的话，就需要让当前节点出栈。

自定义栈:

#import <Foundation/Foundation.h>

// 只要参数是一个id类型的block
typedef void (^StackBlock)(id objc);

@interface NSCustomStack : NSObject
// 入栈
-(void)push:(id)objet;
// 出栈
-(id)popTopElement;
// 返回栈顶元素
-(id)TopElement;
// 是否为空
-(BOOL)isEmpty;
// 栈的长度
-(NSInteger)stackLength;
// 遍历，从栈底开始遍历
-(void)traversalElementFromBottom:(StackBlock)block;
// 从顶部开始遍历
-(void)traversalElementFromtop:(StackBlock)block;
// 所有元素出栈，一边出栈一边返回元素
-(void)traversalElementPopStack:(StackBlock)block;
// 清空
-(void)removeAllObjects;
// 返回栈顶元素
-(id)topElemet;
@end


#import "NSCustomStack.h"

@interface NSCustomStack()

// 有入栈就有出栈的时候，使用强引用，就要记得释放引用
/** NSMutableArray */
@property (nonatomic,strong)NSMutableArray *stackArray;

/** top of stack */
@property (nonatomic,assign)NSInteger top;

@end
@implementation NSCustomStack

#pragma mark --------------- Public Methods

// 入栈
-(void)push:(id)objet{
    [self.stackArray addObject:objet];
}

// 出栈
-(id)popTopElement{
    id objc = [self.stackArray lastObject];
    [self.stackArray removeLastObject];
    return objc;
}

// 返回栈顶元素
-(id)TopElement{
    return [self.stackArray lastObject];
}

// 是否为空
-(BOOL)isEmpty{
    return !self.stackArray.count;
}

// 栈的长度
-(NSInteger)stackLength{
    return self.stackArray.count;
}

// 从底部开始遍历
-(void)traversalElementFromBottom:(StackBlock)block{
    NSEnumerator *objc = [self.stackArray objectEnumerator];
    for (id element in objc) {
        block(element);
    }
}

// 从顶部开始遍历
-(void)traversalElementFromtop:(StackBlock)block{
    // 先获取存储元素的个数
    NSInteger count = self.stackArray.count;
    for (NSInteger i = count - 1; i >= 0; i --) {
        // 处理最后一个元素
        block([self.stackArray objectAtIndex:i]);
    }
}

// 所有元素出栈，同时遍历
-(void)traversalElementPopStack:(StackBlock)block{
    // 先获取存储元素的个数
    NSInteger count = self.stackArray.count;
    for (NSInteger i = count - 1; i >= 0; i --) {
        // 处理最后一个元素
        block(self.stackArray.lastObject);
        [self.stackArray removeLastObject];
    }
}

// 返回栈顶元素
-(id)topElemet{
    return self.stackArray.lastObject;
}

// 清空
-(void)removeAllObjects{
    [self.stackArray removeAllObjects];
}

#pragma mark - 懒加载

-(NSMutableArray*)stackArray{
    if (_stackArray == nil) {
        _stackArray = [NSMutableArray array];
    }
    return _stackArray;
}

-(NSInteger)top{
    _top = self.stackArray.count;
    return _top;
}

#pragma mark - 不存在该对象的时候，自动清空
- (void)dealloc{
    if (_stackArray) {
        [_stackArray removeAllObjects];
    }
}
@end

非递归前序遍历:

// 非递归 前序 遍历 树
void preoder_traversal_iteratively_norecursion (NSBinaryTreeNode *root) {
    
    if (root == nil) {
        return;
    }
    
    // 自定义 栈
    NSCustomStack *tmpStack = [[NSCustomStack alloc] init];
    [tmpStack push:root];
    printf("%d ", root.value);
    
    // 上一个 节点
    NSBinaryTreeNode *previousTreeNode = root;
    
    // 如果 栈 不为空
    while (!tmpStack.isEmpty) {
        
        NSBinaryTreeNode *topTreeNode = tmpStack.topElemet;
        
        if (topTreeNode.left != nil
            && topTreeNode.left != previousTreeNode
            && topTreeNode.right != previousTreeNode) {
            [tmpStack push:topTreeNode.left];
            printf("%d ", topTreeNode.left.value);
        }
        else if(topTreeNode.right != nil &&
                topTreeNode.right != previousTreeNode &&
                (topTreeNode.left == nil || topTreeNode.left == previousTreeNode)){
            [tmpStack push:topTreeNode.right];
             printf("%d ", topTreeNode.right.value);
        }
        else {
            [tmpStack popTopElement];
            previousTreeNode = topTreeNode;
        }
    }
}

非递归中序遍历

// 非递归 中序遍历
void inorder_traversal_iteratively_norecursion(NSBinaryTreeNode *root) {
    if (root == nil) {
        return;
    }
    
    // 自定义 栈
    NSCustomStack *tmpStack = [[NSCustomStack alloc] init];
    [tmpStack push:root];
    
    NSBinaryTreeNode *previousTreeNode = root;
    
    while (!tmpStack.isEmpty) {
        NSBinaryTreeNode *topTreeNode = tmpStack.topElemet;
        if (topTreeNode.left != nil &&
            topTreeNode.left != previousTreeNode &&
            topTreeNode.right != previousTreeNode) {
            [tmpStack push:topTreeNode.left];
        }
        else if(topTreeNode.right != nil &&
                topTreeNode.right != previousTreeNode &&
                (topTreeNode.left == nil || topTreeNode.left == previousTreeNode)){
            [tmpStack push:topTreeNode.right];
             printf("%d ", topTreeNode.value);
        }
        else {
            [tmpStack popTopElement];
            previousTreeNode = topTreeNode;
            if (topTreeNode.right == nil) {
                printf("%d ", topTreeNode.value);
            }
        }
    }
}

非递归后序遍历:

// 非递归 后序遍历
void postorder_traversal_iteratively_norecursion(NSBinaryTreeNode *root) {
    if (root == nil) {
        return;
    }
    
    // 自定义 栈
    NSCustomStack *tmpStack = [[NSCustomStack alloc] init];
    [tmpStack push:root];
    
    NSBinaryTreeNode *previousTreeNode = root;
    
    while (!tmpStack.isEmpty) {
        NSBinaryTreeNode *topTreeNode = tmpStack.topElemet;
        if (topTreeNode.left != nil &&
            topTreeNode.left != previousTreeNode &&
            topTreeNode.right != previousTreeNode) {
            [tmpStack push:topTreeNode.left];
        }
        else if(topTreeNode.right != nil &&
                topTreeNode.right != previousTreeNode &&
                (topTreeNode.left == nil || topTreeNode.left == previousTreeNode)){
            [tmpStack push:topTreeNode.right];
        }
        else {
            [tmpStack popTopElement];
            previousTreeNode = topTreeNode;
            printf("%d ", topTreeNode.value);
        }
    }
}