iOS数据结构学习之OC代码实现二叉树遍历

最近一直在看数据结构相关问题，学到二叉树时，遇到一个棘手的问题就是leetcode没办法断点调试二叉树，而且又没有oc代码的选择，

所以自己开始花了一点时间使用oc代码实现了二叉树的前序、中序、后序遍历。同时也造了2个下面结构的二叉树亲测可用。

二叉树

二叉树是一种更为典型的树树状结构。如它名字所描述的那样，二叉树是每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。

遍历二叉树

前序遍历

前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。按照此思路遍历上面二叉树的结果为 1 2 3

中序遍历

中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。按照此思路遍历上面二叉树的结果为 1 3 2

后序遍历

后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。按照此思路遍历上面二叉树的结果为 3 2 1

自己的实现代码 (非递归)

因为递归代码比较简单，所以只贴迭代的代码

1.创建一个类当作树节点，添加3个属性 val、left、right

@interface TreeNode : NSObject
@property (nonatomic ,assign) NSInteger val;
@property (nonatomic, strong) TreeNode *left;
@property (nonatomic, strong) TreeNode *rigth;
@end

2.创建一个栈对象，定义并实现相应的功能

主要是通过一个可变数组来实现栈的特性。

@interface Stack : NSObject
- (void)push:(id)object;
- (id)top;
- (void)pop;
- (BOOL)isEmpty;
@property (nonatomic, strong) NSMutableArray *muArray;
@end

@implementation Stack
- (void)push:(id)object {
    if (object) {
        [self.muArray addObject:object]; 
   }
}
- (id)top { 
   if (self.muArray && [self.muArray count]) {
        return [self.muArray lastObject];    
    } else {  
          return nil;    
    }
}
- (void)pop {
     if (self.muArray && [self.muArray count]) {
           [self.muArray removeLastObject];
    }
}
- (BOOL)isEmpty {
    if ([self.muArray count]== 0) { 
       return YES;    
    } else {  
          return NO;   
     }
}
-(NSMutableArray *)muArray {
    if (!_muArray) {  
      _muArray = [NSMutableArray array]; 
       }    
    return _muArray;
}
@end

3.搞起来 preOrder inOrder postOrder分别对应前序中序后序遍历

- (void)preOrder {//123  
         TreeNode * leftNode = [[TreeNode alloc]init];  
         leftNode.val = 3;    
         TreeNode * rightNode = [[TreeNode alloc]init];  
         rightNode.val = 2;      
         rightNode.left = leftNode;

         TreeNode * root = [[TreeNode alloc]init];  
         root.val = 1;       
         root.rigth = rightNode; 
         NSMutableArray *result = [NSMutableArray array];

         Stack * stack  = [[Stack alloc]init];  
         while (root || !stack.isEmpty) { 
             if (root) {      
                  [result addObject:@(root.val)]; 
                  [stack push:root];    
                  root = root.left;      
              } else {         
                   TreeNode *node = [stack top]; 
                   [stack pop];  
                   root = node.rigth;   
         }       
     }    
        NSLog(@"%@",result);
}

- (void)inOrder {//132 
          TreeNode * leftNode = [[TreeNode alloc]init];  
          leftNode.val = 3; 
          TreeNode * rightNode = [[TreeNode alloc]init];  
          rightNode.val = 2;   
          rightNode.left = leftNode;  
           TreeNode * root = [[TreeNode alloc]init]; 
           root.val = 1;  
           root.rigth = rightNode; 
           TreeNode * pp  = root;  
           NSMutableArray *result = [NSMutableArray array];
            Stack * stack  = [[Stack alloc]init];  
            while (pp || !stack.isEmpty) {  
               while (pp) {      
               [stack push:pp];  
                   pp = pp.left;    
             }           
               pp = [stack top];  
               [stack pop];  
               [result addObject:@(pp.val)]; 
                pp = pp.rigth;    
     }   
     NSLog(@"%@",result);
}
- (void)postOrder {//231 
           TreeNode * leftNode = [[TreeNode alloc]init]; 
           leftNode.val = 3;   
           TreeNode * rightNode = [[TreeNode alloc]init]; 
           rightNode.val = 2;   
           rightNode.left = leftNode;  
           TreeNode * root = [[TreeNode alloc]init];  
           root.val = 1;   
           root.rigth = rightNode;  
           NSMutableArray *result = [NSMutableArray array];  
           Stack * stack  = [[Stack alloc]init];   
          [stack push:root];   
          TreeNode *head = root;  
          while ( !stack.isEmpty) {  
              TreeNode *t = [stack top]; 
               if ((!t.left && !t.rigth)|| t.left == head || t.rigth == head ) { 
                   [result addObject:@(t.val)];  
                  [stack pop];       
                 head = t;       
          } else {      
               if (t.rigth) {  
               [stack push:t.rigth];   
          }        
             if (t.left) {  
                  [stack push:t.left];     
            }             
        }  
      }   
     NSLog(@"%@",result);
}