数据结构与算法之二叉树遍历(七)

目录

• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历
• 遍历方式的选择条件
• 根据遍历结果重构二叉树
• 翻转二叉树
• 计算二叉树的高度
• 判断一棵树是否为完全二叉树
• 找前驱节点
• 找后继节点

一 前序遍历(Preorder Traversal)

访问顺序：`根节点，前序遍历左子树，前序遍历右``子树

image.png

遍历顺序: [7]，[4，2，1，3，5]，[9，8，11，10，12]

带[]表示分割为根节点，左子树节点，右子树节点，下面类似

• 代码实现 - 递归

/// 前序遍历
- (void)preorder:(TreeNode *)node {
    if (node == nil) {
        return;
    }
    
    NSLog(@"%@",node.description);
    [self preorder:node.left];
    [self preorder:node.right];
}

• 测试代码

/// 前序遍历
- (void)preorder {
    NSArray *data = @[@7,@4,@9,@2,@5,@8,@11,@1,@3,@10,@12];
    
    BinarySearchTree *tree = [[BinarySearchTree alloc] init];
    for (int i = 0; i < data.count; i++) {
        [tree add:data[i]];
    }
    
    [tree preordr];
}

运行结果

前序遍历.png

二 中序遍历(Inorder Traversal)

访问顺序：中序遍历左子树，根节点，中序遍历右子树

上图中序遍历结果：[1，2，3，4，5]，[7]，[8，9，10，11，12]

2.1 扩展

如果将访问顺序调整为：中序遍历右子树，根节点，中序遍历左子树

遍历结果：[12，11，10，9，8]，[7]，[5，4，3，2，1]

总结：二叉搜索树的中序遍历结果是升序或者降序的

• 代码实现 - 递归

/// 中序遍历
- (void)inorder:(TreeNode *)node {
    if (node == nil) {
        return;
    }
    [self inorder:node.left];
    NSLog(@"%@",node.description);
    [self inorder:node.right];
}

• 测试代码

/// 中序遍历
- (void)Inorder {
    NSArray *data = @[@7,@4,@9,@2,@5,@8,@11,@1,@3,@10,@12];
    
    BinarySearchTree *tree = [[BinarySearchTree alloc] init];
    for (int i = 0; i < data.count; i++) {
        [tree add:data[i]];
    }
    
    [tree inorder];
}

运行结果

中序遍历.png

三 后序遍历(Postorder Traversal)

访问顺序：后序遍历左子树，后序遍历右子树，根节点

上图后序遍历结果:
[1，3，2，5，4]，[8，10，12，11，9]，[7]

代码实现 - 递归

/// 后序遍历
- (void)postorder:(TreeNode *)node {
    if (node == nil) {
        return;
    }
    [self postorder:node.left];
    [self postorder:node.right];
    NSLog(@"%@",node.description);
}

• 测试代码

/// 后序遍历
- (void)postorder {
    NSArray *data = @[@7,@4,@9,@2,@5,@8,@11,@1,@3,@10,@12];
    
    BinarySearchTree *tree = [[BinarySearchTree alloc] init];
    for (int i = 0; i < data.count; i++) {
        [tree add:data[i]];
    }
    
    [tree postorder];
}

运行结果：

后序遍历.png

四 层序遍历(Level Order Traversal)

访问顺序：从上到下，从左到右，依次访问每一个节点
上图遍历结果：[7]，[4，9]，[2，5，8，11]，[1，3，10，12]

实现思路：使用队列

1. 将根节点入队
2. 循环执行以下操作，直到队列为空
2.1 将队头节点A出队，进行访问
2.2 将A的左子节点入队
2.3 将A的右子节点入队

• 代码实现 - 迭代

/// 层序遍历
- (void)levelOrder {
    if (_root == nil) {
        return;
    }
    
    Queue *queue = [[Queue alloc] init];
    [queue enQueue:_root];
    
    while (!queue.isEmpty) {
        TreeNode *node = [queue deQueue];
        NSLog(@"%@",node.description);
        
        if (node.left != nil) { // 左子节点入队
            [queue enQueue:node.left];
        }
        
        if (node.right != nil) {    // 右子节点入队
            [queue enQueue:node.right];
        }
    }
}

• 测试代码

/// 层序遍历
- (void)levelOrder {
    NSArray *data = @[@7,@4,@9,@2,@5,@8,@11,@1,@3,@10,@12];
    
    BinarySearchTree *tree = [[BinarySearchTree alloc] init];
    for (int i = 0; i < data.count; i++) {
        [tree add:data[i]];
    }
    
    [tree levelOrder];
}

运行结果：

层序遍历.png

五 遍历的作用

• 前序遍历：树状结构展示（注意左右子树的顺序）
• 中序遍历：二叉搜索树的中序遍历按升序或者降序处理节点
• 后序遍历：适用于一些先子后父的操作
• 层序遍历：计算二叉树的高度，判断一棵树是否为完全二叉树

六 根据遍历结果重构二叉树

6.1 以下结果可以保证重构出唯一的一棵二叉树

• 前序遍历 + 中序遍历
• 后序遍历 + 中序遍历

image.png

6.2 前序遍历 + 后序遍历

• 如果它是一棵真二叉树，结果是唯一的
• 不然结果不唯一

image.png

即左子树和右子树的分割点难以确认

七 前序遍历 + 中序遍历重构二叉树

八 利用前序遍历树状打印二叉树

• 代码实现如下

- (NSString *)description {
    NSMutableString *strM = [NSMutableString stringWithString:@"\n"];
    NSMutableString *prefix = [NSMutableString string];
    [self toString:_root strM:strM prefix:prefix];
    return strM.copy;
}

- (void)toString:(TreeNode *)node strM:(NSMutableString *)strM prefix:(NSMutableString *)prefix {
    if (node == nil) {
        return;
    }
    
    // 前序遍历二叉树
    [self toString:node.left strM:strM prefix:[NSMutableString stringWithFormat:@"%@%@",prefix,@"L_"]];
    [strM appendString:[NSString stringWithFormat:@"%@%@ \n",prefix,node.element]];
    [self toString:node.right strM:strM prefix:[NSMutableString stringWithFormat:@"%@%@",prefix,@"R_"]];
}

• 测试代码

/// 利用前序遍历树状打印二叉树
- (void)printBinarySearchTree {
    NSArray *data = @[@7,@4,@9,@2,@5,@8,@11,@1,@3,@10,@12];
    
    BinarySearchTree *tree = [[BinarySearchTree alloc] init];
    for (int i = 0; i < data.count; i++) {
        [tree add:data[i]];
    }
    
    NSLog(@"%@",tree.description);
}

运行结果

image.png

九 翻转二叉树

226. 翻转二叉树

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

• 代码实现如下

十 计算二叉树的高度

• 递归实现

/// 计算二叉树的高度 - 递归实现
- (int)getHeight {
    return [self height:_root];
}

- (int)height:(TreeNode *)node {
    if (node == nil) {
        return 0;
    }
    return 1 + MAX([self height:node.left], [self height:node.right]);
}

• 迭代实现

/// 计算二叉树的高度 - 迭代实现 - 层序遍历
- (int)getHeight2 {
    if (_root == nil) {
        return 0;
    }
    
    int height = 0; // 树的高度
    int levelSize = 1;  // 存储着每一层的元素数量
    
    Queue *qu = [[Queue alloc] init];
    [qu enQueue:_root];
    
    // 遍历队列
    while (!qu.isEmpty) {
        TreeNode *node = qu.deQueue;
        levelSize--;
        
        if (node.left != nil) {
            [qu enQueue:node.left];
        }
        
        if (node.right != nil) {
            [qu enQueue:node.right];
        }
        
        if (levelSize == 0) {   // // 意味着即将要访问下一层
            levelSize = qu.size;
            height++;
        }
    }
    
    return height;
}

• 测试代码

/// 计算二叉树的高度
- (void)getTreeHeight {
    NSArray *data = @[@7,@4,@9,@2,@5,@8,@11,@1,@3,@10,@12];
    
    BinarySearchTree *tree = [[BinarySearchTree alloc] init];
    for (int i = 0; i < data.count; i++) {
        [tree add:data[i]];
    }
    
    NSLog(@"递归:%d",[tree getHeight]);
    NSLog(@"递归:%d",[tree getHeight2]);
}

• 运行结果

二叉树高度.png

十一 判断一棵树是否为完全二叉树

实现原理

1. 如果树为空，返回 false
2. 如果树不为空，开始层序遍历二叉树（使用队列）
  2.1 如果node.left != nil && node.right != nil，将node.left，node.right按顺序入队列
  2.2 如果node.left == nil && node.right != nil，返回false
  2.3 如果node.left != nil && node.right == nil 或者 node.left == nil && node.right == nil，那么
    2.3.1 后面遍历的节点都应该为叶子节点，才是完全二叉树
    2.3.2 否则返回 false
  2.4 遍历结果，返回 true

• 代码实现如下

/// 是否为完全二叉树
- (BOOL)isComplteBinaryTree {
    if (_root == nil) {
        return false;
    }
    
    Queue *qu = [[Queue alloc] init];
    [qu enQueue:_root];
    
    BOOL leaf = false;  // 是否为叶子节点
    while (!qu.isEmpty) {
        TreeNode *node = qu.deQueue;
        
        if (leaf && !node.isLeaf) { // 处于最后一层了,要求是叶子节点才可以
            return false;
        }
        
        if (node.hasTwoChildren) {  // 有左右子树 - 都入队
            [qu enQueue:node.left];
            [qu enQueue:node.right];
        } else if (node.left == nil && node.right != nil) { // 如果只有一个叶子节点,必须在左边才行
            return false;
        } else {    // 后面遍历的节点都必须是叶子节点
            leaf = true;
        }
    }
    
    return true;
}

• 测试代码

/// 是否为完全二叉树
- (void)isComplteBinaryTree {
    NSArray *data = @[@7,@4,@9,@2,@5,@8,@11,@1,@3,@10,@12];
    NSArray *data1 = @[@7,@4,@9,@2,@5,@8,@11];
    NSArray *data2 = @[@7,@4,@9,@2,@5,@8,@11,@1];
    
    BinarySearchTree *tree = [[BinarySearchTree alloc] init];
    for (int i = 0; i < data.count; i++) {
        [tree add:data[i]];
    }
    BinarySearchTree *tree1 = [[BinarySearchTree alloc] init];
    for (int i = 0; i < data1.count; i++) {
        [tree1 add:data1[i]];
    }
    BinarySearchTree *tree2 = [[BinarySearchTree alloc] init];
    for (int i = 0; i < data2.count; i++) {
        [tree2 add:data2[i]];
    }
    NSLog(@"%d",[tree isComplteBinaryTree]);
    NSLog(@"%d",[tree1 isComplteBinaryTree]);
    NSLog(@"%d",[tree2 isComplteBinaryTree]);
}

• 运行结果

image.png

为了快速构建二叉树，可以将数组的元素按照层序遍历的顺序排列好

更多详细代码请看项目链接

十二 前驱节点（predecessor）

前驱节点：中序遍历时的前一个节点

如果是二叉搜索树，前驱节点就是前一个比它小的节点

视图.png

分为以下情况分别讲解

12.1 node.left != nil

举例：6，13，8
则查找它的前驱节点算法为

predecessor = node.left.right.right.right ...
终止条件：right = nil

12.2 node.left == nil && node.parent != nil

举例：7，11，9，1
则查找它的前驱节点算法为

predecessor = node.parent.parent.parent ...
终止条件：node在parent的右子树中

12.3 node.left == nil && node.parent == nil

那就没有前驱节点
举例：没有左子树的根节点

• 代码实现

/// 找前驱节点
- (TreeNode *)predecessor:(TreeNode *)node {
    if (node == nil) {
        return nil;
    }
    
    /** 1.左子树不为空
        前驱节点在左子树当中（left.right.right.right....）
     */
    TreeNode *p = node.left;
    if (p != nil) {
        while (p.right != nil) {
            p = p.right;
        }
        return p;
    }
    
    /** 2.左子树为空,父节点不为空
        从父节点、祖父节点中寻找前驱节点
     */
    while (node.parent != nil && node == node.parent.left) {
        node = node.parent;
    }
    
    // node.parent == null
    // node == node.parent.right
    return node.parent;
}

• 测试代码

// 找前驱节点
- (void)predecessor {
    NSArray *data = @[@8,@4,@13,@2,@6,@10,@1,@3,@5,@7,@9,@12,@11];
    
    BinarySearchTree *tree = [[BinarySearchTree alloc] init];
    for (int i = 0; i < data.count; i++) {
        [tree add:data[i]];
    }
    
    NSLog(@"二叉树为\n %@",tree.description);
    
    NSArray *data1 = @[@6,@13,@8,@7,@11,@9,@1];
    for (int i = 0; i < data1.count; i++) {
        TreeNode *node = [tree node:data1[i]];
        NSLog(@"%@的前驱节点:%@",node.element,[tree predecessor:node].element);
    }
}

运行结果如下

找前驱节点.png

十三 后继节点（succesor）

后继节点：中序遍历时的后一个节点

如果是二叉搜索树，前驱节点就是前一个比它大的节点

二叉树.png

分为以下情况分别讲解

13.1 node.right != nil

举例：1，8，4
则查找它的后继节点算法为

successor = node.right.left.left.left ...
终止条件：left = nil

13.2 node.right == nil && node.parent != nil

举例：7，6，3，11
则查找它的后继节点算法为

successor = node.parent.parent.parent ...
终止条件：node在parent的左子树中

13.3 node.right == nil && node.parent == nil

那就没有后继节点
举例：没有右子树的根节点

• 代码实现如下

/// 找后继节点
- (TreeNode *)successor:(TreeNode *)node {
    if (node == nil) {
        return nil;
    }
    
    /** 1.右子树不为空
        前驱节点在左子树当中（node.right.left.left.left....）
     */
    TreeNode *p = node.right;
    if (p != nil) {
        while (p.left != nil) {
            p = p.left;
        }
        return p;
    }
    
    /** 2.右子树为空,父节点不为空
        从父节点、祖父节点中寻找前驱节点
     */
    while (node.parent != nil && node == node.parent.right) {
        node = node.parent;
    }
    
    return node.parent;
}

• 测试代码如下

// 找后继节点
- (void)successor {
    NSArray *data = @[@4,@1,@8,@2,@7,@10,@3,@5,@9,@11,@6];
    
    BinarySearchTree *tree = [[BinarySearchTree alloc] init];
    for (int i = 0; i < data.count; i++) {
        [tree add:data[i]];
    }
    
    NSLog(@"二叉树为\n %@",tree.description);
    
    NSArray *data1 = @[@1,@8,@4,@7,@6,@3,@11];
    for (int i = 0; i < data1.count; i++) {
        TreeNode *node = [tree node:data1[i]];
        NSLog(@"%@的后继节点:%@",node.element,[tree successor:node].element);
    }
}

运行结果：

找后继节点.png

---

本文会持续更新中，更多精彩内容敬请期待。

---

本文参考 MJ老师的 恋上数据结构与算法

---

本人技术水平有限，如有错误欢迎指正。
书写整理不易，您的打赏点赞是对我最大的支持和鼓励，欢迎点赞打赏。

---

项目连接链接 - 09_Tree