二叉樹遍歷的四種方式

• 前序遍歷

根----左子樹----右子樹

• 中序遍歷

左子樹----根----右子樹

• 后序遍歷

左子樹----右子樹---根

• 層序遍歷

逐層遍歷

遞歸

• 使用遞歸方法比遍歷

前序遍歷

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

///  根---左子樹----右子樹 遞歸的方式
- (void)frontTraversalWithNode:(Node *)node{
    // 結(jié)束遞歸
    if (node == nil) return;
    
    // 先訪問根節(jié)點
    NSObject *ele = node.ele;
    NSLog(@"%@",ele);
    // 再訪問左子樹
    // 遞歸調(diào)用
    [self frontTraversalWithNode:node.left];
    
    // 最后訪問右子樹
    // 遞歸調(diào)用
    [self frontTraversalWithNode:node.right];
}

中序遍歷

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


///  左子樹---根---右子樹  遞歸
- (void)centerTraversalWithNode:(Node *)node{
    // 結(jié)束遞歸
    if (node == nil) return;
    
    // 先訪問左子樹  遞歸調(diào)用
    [self centerTraversalWithNode:node.left];
    
    NSLog(@"%@",node.ele);
    
    // 最后訪問右子樹
    // 遞歸調(diào)用
    [self centerTraversalWithNode:node.right];
}

后序遍歷

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

/// 左子樹----右子樹---根
- (void)afterTraversalWithNode:(Node *)node{
    // 結(jié)束遞歸
    if (node == nil) return;
    // 先訪問左子樹  遞歸調(diào)用
    [self afterTraversalWithNode:node.left];
    // 再訪問右子樹
    // 遞歸調(diào)用
    [self afterTraversalWithNode:node.right];
    NSLog(@"%@",node.ele);
}

中續(xù)遍歷遞歸過程分析，如下圖：

遞歸中續(xù)遍歷.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;
    }
    
}

使用棧的方式

前序遍歷

方式一：

/// 利用?？梢韵f歸
- (void)frontTraversalStack{
    [self frontTraversalStackWithNode:self.rootNode];
}


///  根---左子樹----右子樹 棧的方式   后進(jìn)先出
- (void)frontTraversalStackWithNode:(Node *)node{
    if (node == nil) return;

    // 1.創(chuàng)建棧
    NSMutableArray *stack = [NSMutableArray array];
    //2.將根節(jié)點入棧
    [stack addObject:node];
    while (stack.count > 0) {
        
        // 3.彈出棧頂節(jié)點
        Node *tempNode = stack.lastObject;
        [stack removeLastObject];
        NSLog(@"%@",tempNode.ele);

        
        // 先遍歷左子樹，右子樹先入棧
        //4.將節(jié)點的右子樹入棧
        if (tempNode.right) {
            [stack addObject:tempNode.right];
        }
         
        //5.將節(jié)點的左子樹入棧
        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) {
        
        //發(fā)現(xiàn)節(jié)點不等于nil就入棧
        while (node != nil) {
            //將根添加到棧
            [stack addObject:node];
            // 如果有左子樹， 循環(huán)將左子樹加到棧
            node = node.left;
        }
        // 循環(huán)結(jié)束根節(jié)點的所有左子樹都加入到棧中
        
    
        // 出棧(最先出棧的是根節(jié)點的左子樹)
        node = stack.lastObject;
        [stack removeLastObject];
        
        //訪問節(jié)點
        NSLog(@"%@",node.ele);
        
        // 處理右子樹
        node = node.right;

    }
}

后序遍歷

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

- (void)afterStackWithNode:(Node *)node{
    if (node == nil) {
        return;
    }
    
    // 創(chuàng)建兩個棧
    NSMutableArray<Node *> *stack1 = [NSMutableArray array];
    NSMutableArray<Node *> *stack2 = [NSMutableArray array];
    
    // 根節(jié)點入棧1
    [stack1 addObject:node];
        
    // 循環(huán)
    while (stack1.count > 0) {
        // 取出棧頂元素
        Node *topNode = stack1.lastObject;
        [stack1 removeLastObject];
        
        // 將棧頂元素 加入棧2
        [stack2 addObject:topNode];
        
        // 左節(jié)點入棧1
        if (topNode.left) {
            [stack1 addObject:topNode.left];
        }
        
        // 右節(jié)點入棧1
        if (topNode.right) {
            [stack1 addObject:topNode.right];
        }
    }
    
    while (stack2.count > 0) {
        Node *node = stack2.lastObject;
        [stack2 removeLastObject];
        NSLog(@"%@",node.ele);
        
        
    }
    
}

層序遍歷

/*
 1. 將根節(jié)點加入數(shù)組
 2. 循環(huán)執(zhí)行以下操作，直到數(shù)組為空
    將第一個節(jié)點 A 取出進(jìn)行訪問，訪問完成后刪除
    將 A 的左子節(jié)點加入數(shù)組
    將 A 的右子節(jié)點加入數(shù)組
 */
- (void)levelTraversal{
    // 創(chuàng)建保存節(jié)點的數(shù)組
    NSMutableArray *array = [NSMutableArray array];

    // 1.將根節(jié)點加入數(shù)組
    [array addObject:self.rootNode];
    // 樹的高度
    int height = 0;
    // 層數(shù)
    NSInteger levelSize = 1;
    // 循環(huán)操作，直到數(shù)組為空
    while (array.count > 0) {
       // 取出第一個節(jié)點
        Node *tmpNode = array.firstObject;

        //訪問元素
        NSNumber *ele = (NSNumber *)tmpNode.ele;
        NSLog(@"ele:%@",ele);
        
        // 刪除第一個節(jié)點
        [array removeObjectAtIndex:0];
        levelSize --;
        
        // 加入左子節(jié)點
        if (tmpNode.left) {
            [array addObject:tmpNode.left];
        }
        // 加入右子節(jié)點
        if (tmpNode.right) {

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

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