二叉树遍历

二叉树遍历的四种方式

• 前序遍历

根----左子树----右子树

• 中序遍历

左子树----根----右子树

• 后序遍历

左子树----右子树---根

• 层序遍历

逐层遍历

递归

• 使用递归方法比遍历

前序遍历

- (void)frontTraversal{
    [self frontTraversalWithNode:self.rootNode];
}

///  根---左子树----右子树 递归的方式
- (void)frontTraversalWithNode:(Node *)node{
    // 结束递归
    if (node == nil) return;
    
    // 先访问根节点
    NSObject *ele = node.ele;
    NSLog(@"%@",ele);
    // 再访问左子树
    // 递归调用
    [self frontTraversalWithNode:node.left];
    
    // 最后访问右子树
    // 递归调用
    [self frontTraversalWithNode:node.right];
}

中序遍历

/// 中序遍历
- (void)centerTraversal{
    [self centerTraversalWithNode:self.rootNode];
}


///  左子树---根---右子树  递归
- (void)centerTraversalWithNode:(Node *)node{
    // 结束递归
    if (node == nil) return;
    
    // 先访问左子树  递归调用
    [self centerTraversalWithNode:node.left];
    
    NSLog(@"%@",node.ele);
    
    // 最后访问右子树
    // 递归调用
    [self centerTraversalWithNode:node.right];
}

后序遍历

/// 后序遍历
- (void)afterTraversal{
    [self afterTraversalWithNode:self.rootNode];
}

/// 左子树----右子树---根
- (void)afterTraversalWithNode:(Node *)node{
    // 结束递归
    if (node == nil) return;
    // 先访问左子树  递归调用
    [self afterTraversalWithNode:node.left];
    // 再访问右子树
    // 递归调用
    [self afterTraversalWithNode:node.right];
    NSLog(@"%@",node.ele);
}

中续遍历递归过程分析，如下图：

递归中续遍历.jpg

层序遍历

/// 层序遍历
- (void)levelRecursion{
    if (self.rootNode == nil) {
        return;
    }
    
    // 获取rootNode的层高，
    int depth = [self depth:self.rootNode];
    for (int i = 0; i <= depth; i ++) {
        [self levelOrder:self.rootNode level:i];
    }
}
   

- (void)levelOrder:(Node *)node level:(int)level{
    if (node == nil || level < 1) {
        return;
    }
    
    if (level == 1) {
        NSLog(@"%@",node.ele);
    }
    
    [self levelOrder:node.left level:level-1];
    
    [self levelOrder:node.right level:level-1];
}
    
// 递归，获取有多少层
- (int)depth:(Node *)node{
    if (node == nil) {
        return 0;
    }
    
    int left = [self depth:node.left];
    int right = [self depth:node.right];

    if (left > right) {
        return left + 1;
    }else{
        return right + 1;
    }
    
}

使用栈的方式

前序遍历

方式一：

/// 利用栈可以消除递归
- (void)frontTraversalStack{
    [self frontTraversalStackWithNode:self.rootNode];
}


///  根---左子树----右子树 栈的方式   后进先出
- (void)frontTraversalStackWithNode:(Node *)node{
    if (node == nil) return;

    // 1.创建栈
    NSMutableArray *stack = [NSMutableArray array];
    //2.将根节点入栈
    [stack addObject:node];
    while (stack.count > 0) {
        
        // 3.弹出栈顶节点
        Node *tempNode = stack.lastObject;
        [stack removeLastObject];
        NSLog(@"%@",tempNode.ele);

        
        // 先遍历左子树，右子树先入栈
        //4.将节点的右子树入栈
        if (tempNode.right) {
            [stack addObject:tempNode.right];
        }
         
        //5.将节点的左子树入栈
        if (tempNode.left) {
            [stack addObject:tempNode.left];
        }
        
    }
}

方式二：

// 前序遍历  栈2
- (void)frontTraversalStack2{
    [self frontTraversalStackWithNode:self.rootNode];
}


- (void)frontTraversalStack2WithNode:(Node *)node{
    
    NSMutableArray *stack = [NSMutableArray array];
    while (node != nil || stack.count > 0) {
        while (node != nil) {
            
            NSLog(@"%@",node.ele);
            [stack addObject:node];
            node = node.left;
        }
        
        if (stack.count > 0) {
            node = stack.lastObject;
            [stack removeLastObject];
            node = node.right;
        }
    }
    
}

中序遍历

///中序遍历  栈
- (void)centerTraversalStackWithNode:(Node *)node{
    
    NSMutableArray *stack = [NSMutableArray array];
    
    // 如果node==nil 并且 stack 为空就停止遍历
    while (node != nil || stack.count > 0) {
        
        //发现节点不等于nil就入栈
        while (node != nil) {
            //将根添加到栈
            [stack addObject:node];
            // 如果有左子树， 循环将左子树加到栈
            node = node.left;
        }
        // 循环结束根节点的所有左子树都加入到栈中
        
    
        // 出栈(最先出栈的是根节点的左子树)
        node = stack.lastObject;
        [stack removeLastObject];
        
        //访问节点
        NSLog(@"%@",node.ele);
        
        // 处理右子树
        node = node.right;

    }
}

后序遍历

- (void)afterStack{
    [self afterStackWithNode:self.rootNode];
}

- (void)afterStackWithNode:(Node *)node{
    if (node == nil) {
        return;
    }
    
    // 创建两个栈
    NSMutableArray<Node *> *stack1 = [NSMutableArray array];
    NSMutableArray<Node *> *stack2 = [NSMutableArray array];
    
    // 根节点入栈1
    [stack1 addObject:node];
        
    // 循环
    while (stack1.count > 0) {
        // 取出栈顶元素
        Node *topNode = stack1.lastObject;
        [stack1 removeLastObject];
        
        // 将栈顶元素 加入栈2
        [stack2 addObject:topNode];
        
        // 左节点入栈1
        if (topNode.left) {
            [stack1 addObject:topNode.left];
        }
        
        // 右节点入栈1
        if (topNode.right) {
            [stack1 addObject:topNode.right];
        }
    }
    
    while (stack2.count > 0) {
        Node *node = stack2.lastObject;
        [stack2 removeLastObject];
        NSLog(@"%@",node.ele);
        
        
    }
    
}

层序遍历

/*
 1. 将根节点加入数组
 2. 循环执行以下操作，直到数组为空
    将第一个节点 A 取出进行访问，访问完成后删除
    将 A 的左子节点加入数组
    将 A 的右子节点加入数组
 */
- (void)levelTraversal{
    // 创建保存节点的数组
    NSMutableArray *array = [NSMutableArray array];

    // 1.将根节点加入数组
    [array addObject:self.rootNode];
    // 树的高度
    int height = 0;
    // 层数
    NSInteger levelSize = 1;
    // 循环操作，直到数组为空
    while (array.count > 0) {
       // 取出第一个节点
        Node *tmpNode = array.firstObject;

        //访问元素
        NSNumber *ele = (NSNumber *)tmpNode.ele;
        NSLog(@"ele:%@",ele);
        
        // 删除第一个节点
        [array removeObjectAtIndex:0];
        levelSize --;
        
        // 加入左子节点
        if (tmpNode.left) {
            [array addObject:tmpNode.left];
        }
        // 加入右子节点
        if (tmpNode.right) {

            [array addObject:tmpNode.right];
        }
        if (levelSize == 0) {
            height ++;
            NSLog(@"---------------");
            levelSize = array.count;
        }

    }
    NSLog(@"height=%d",height);
}