《恋上数据结构与算法一》笔记（七）二叉树遍历

一前序遍历(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

最后编辑于：2020.03.14 17:49:24

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,937评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,503评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,712评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,668评论 1赞 276
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,677评论 5赞 366
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,601评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,975评论 3赞 396
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,637评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,881评论 1赞 298
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,621评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,710评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,387评论 4赞 319
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,971评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,947评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,189评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 44,805评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,449评论 2赞 342

《恋上数据结构与算法一》笔记（七）二叉树遍历

《恋上数据结构与算法一》笔记（七）二叉树遍历

目录

一前序遍历(Preorder Traversal)

二中序遍历(Inorder Traversal)

2.1 扩展

三后序遍历(Postorder Traversal)

四层序遍历(Level Order Traversal)

五遍历的作用

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

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

6.2 前序遍历 + 后序遍历

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

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

九翻转二叉树

226. 翻转二叉树

十计算二叉树的高度

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

十二前驱节点（predecessor）

12.1 node.left != nil

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

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

十三后继节点（succesor）

13.1 node.right != nil

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

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

推荐阅读更多精彩内容

《恋上数据结构与算法一》笔记（七）二叉树遍历

目录

一 前序遍历(Preorder Traversal)

二 中序遍历(Inorder Traversal)

2.1 扩展

三 后序遍历(Postorder Traversal)

四 层序遍历(Level Order Traversal)

五 遍历的作用

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

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

6.2 前序遍历 + 后序遍历

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

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

九 翻转二叉树

226. 翻转二叉树

十 计算二叉树的高度

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

十二 前驱节点（predecessor）

12.1 node.left != nil

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

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

十三 后继节点（succesor）

13.1 node.right != nil

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

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

推荐阅读更多精彩内容

一前序遍历(Preorder Traversal)

二中序遍历(Inorder Traversal)

三后序遍历(Postorder Traversal)

四层序遍历(Level Order Traversal)

五遍历的作用

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

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

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

九翻转二叉树

十计算二叉树的高度

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

十二前驱节点（predecessor）

十三后继节点（succesor）