数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?

王争 2018-11-12
前面我们讲的都是线性表结构,栈、队列等等。今天我们讲一种非线性表结构,树。树这种数据结构比线性表的数据结构要复杂得多,内容也比较多,所以我会分四节来讲解。
我反复强调过,带着问题学习,是最有效的学习方式之一,所以在正式的内容开始之前,我还是给你出一道思考题:二叉树有哪几种存储方式?什么样的二叉树适合用数组来存储?
带着这些问题,我们就来学习今天的内容,树!

树(Tree)

我们首先来看,什么是“树”?再完备的定义,都没有图直观。所以我在图中画了几棵“树”。你来看看,这些“树”都有什么特征?
你有没有发现,“树”这种数据结构真的很像我们现实生活中的“树”,这里面每个元素我们叫作“节点”;用来连线相邻节点之间的关系,我们叫作“父子关系”。
比如下面这幅图,A 节点就是 B 节点的父节点,B 节点是 A 节点的子节点。B、C、D 这三个节点的父节点是同一个节点,所以它们之间互称为兄弟节点。我们把没有父节点的节点叫作根节点,也就是图中的节点 E。我们把没有子节点的节点叫作叶子节点或者叶节点,比如图中的 G、H、I、J、K、L 都是叶子节点。
除此之外,关于“树”,还有三个比较相似的概念:高度(Height)、深度(Depth)、(Level)。它们的定义是这样的:
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(136)

  • meng
    关于问题1,如果是完全二叉树,老师说过可以放在数组里面,那么问题是否 可以简化为数组内的元素有多少种组合方式,这样的话,就是 n!,不知是否可以这样理解 ?

    作者回复: 👍

    2018-11-18
    4
    172
  • 失火的夏天
    1.是卡特兰数,是C[n,2n] / (n+1)种形状,c是组合数,节点的不同又是一个全排列,一共就是n!*C[n,2n] / (n+1)个二叉树。可以通过数学归纳法推导得出。
    2.层次遍历需要借助队列这样一个辅助数据结构。(其实也可以不用,这样就要自己手动去处理节点的关系,代码不太好理解,好处就是空间复杂度是o(1)。不过用队列比较好理解,缺点就是空间复杂度是o(n))。根节点先入队列,然后队列不空,取出对头元素,如果左孩子存在就入列队,否则什么也不做,右孩子同理。直到队列为空,则表示树层次遍历结束。树的层次遍历,其实也是一个广度优先的遍历算法。
    2018-11-12
    8
    122
  • Jerry银银
    第一题:
    确定两点:
    1)n个数,即n个节点,能构造出多少种不同形态的树?
    2)n个数,有多少种不同的排列?
    当确定以上两点,将【1)的结果】乘以 【2)的结果】,即为最终的结果。
    但是有一个注意的点: 如果n中有相等的数,产生的总排列数就不是n!了哟

    通过这一题,我学到了【卡塔兰数】:https://en.wikipedia.org/wiki/Catalan_number

    第二题:
    层序遍历,借用队列辅助即可,根节点先入队列,然后循环从队列中pop节点,将pop出来的节点的左子节点先入队列,右节点后入队列,依次循环,直到队列为空,遍历结束。

    leetcode上有个类似的题目,链接为:https://leetcode.com/problems/binary-tree-level-order-traversal/
    Java代码如下:
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            if (root == null) return new ArrayList<>(0);
            
            List<List<Integer>> result = new ArrayList<>();
            
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.offer(root);
            
            Queue<TreeNode> curLevelNodes = new LinkedList<TreeNode>();
            
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                curLevelNodes.offer(node);
                
                if (queue.isEmpty()) {
                    List<Integer> list = new ArrayList<>(curLevelNodes.size());
                    while (!curLevelNodes.isEmpty()) {
                        TreeNode curNode = curLevelNodes.poll();
                        list.add(curNode.val);
                        
                        if (curNode.left != null) {
                            queue.offer(curNode.left);
                        }
                        
                        if (curNode.right != null) {
                            queue.offer(curNode.right);
                        }
                        
                    }
                    result.add(list);
                }
            }
            
            
            return result;
        }
        
    }
    2018-11-18
    3
    51
  • 言志
    1、既然是数组了,说明是完全二叉树,应该有n的阶乘个组合。
    2、二叉树按层遍历,可以看作以根结点为起点,图的广度优先遍历的问题。

    作者回复: 👍

    2018-11-21
    1
    47
  • 姜威
    树,总共包含4节内容。具体如下:
    1.树、二叉树
    2.二叉查找树
    3.平衡二叉树、红黑树
    4.递归树

    一、树
    1.树的常用概念
    根节点、叶子节点、父节点、子节点、兄弟节点,还有节点的高度、深度以及层数,树的高度。
    2.概念解释
    节点:树中的每个元素称为节点
    父子关系:相邻两节点的连线,称为父子关系
    根节点:没有父节点的节点
    叶子节点:没有子节点的节点
    父节点:指向子节点的节点
    子节点:被父节点指向的节点
    兄弟节点:具有相同父节点的多个节点称为兄弟节点关系
    节点的高度:节点到叶子节点的最长路径所包含的边数
    节点的深度:根节点到节点的路径所包含的边数
    节点的层数:节点的深度+1(根节点的层数是1)
    树的高度:等于根节点的高度
    二、二叉树
    1.概念
    ①什么是二叉树?
    每个节点最多只有2个子节点的树,这两个节点分别是左子节点和右子节点。
    ②什么是满二叉树?
    有一种二叉树,除了叶子节点外,每个节点都有左右两个子节点,这种二叉树叫做满二叉树。
    ③什么是完全二叉树?
    有一种二叉树,叶子节点都在最底下两层,最后一层叶子节都靠左排列,并且除了最后一层,其他层的节点个数都要达到最大,这种二叉树叫做完全二叉树。
    2.完全二叉树的存储
    ①链式存储
    每个节点由3个字段,其中一个存储数据,另外两个是指向左右子节点的指针。我们只要拎住根节点,就可以通过左右子节点的指针,把整棵树都串起来。这种存储方式比较常用,大部分二叉树代码都是通过这种方式实现的。
    ②顺序存储
    用数组来存储,对于完全二叉树,如果节点X存储在数组中的下标为i,那么它的左子节点的存储下标为2*i,右子节点的下标为2*i+1,反过来,下标i/2位置存储的就是该节点的父节点。注意,根节点存储在下标为1的位置。完全二叉树用数组来存储时最省内存的方式。
    3.二叉树的遍历
    ①前序遍历:对于树中的任意节点来说,先打印这个节点,然后再打印它的左子树,最后打印它的右子树。
    ②中序遍历:对于树中的任意节点来说,先打印它的左子树,然后再打印它的本身,最后打印它的右子树。
    ③后序遍历:对于树中的任意节点来说,先打印它的左子树,然后再打印它的右子树,最后打印它本身。
    前序遍历的递推公式:
    preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)
    中序遍历的递推公式:
    inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
    后序遍历的递推公式:
    postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r
    时间复杂度:3种遍历方式中,每个节点最多会被访问2次,所以时间复杂度是O(n)。
    三、思考
    1.二叉树有哪几种存储方式?什么样的二叉树适合用数组来存储?
    2.给定一组数据,比如1,3,5,6,9,10.你来算算,可以构建出多少种不同的二叉树?
    3.我们讲了三种二叉树的遍历方式,前、中、后序。实际上,还有另一种遍历方式,也就是按层遍历,你知道如何实现吗?
    4.如何用循环实现二叉树的遍历?
    2018-11-24
    2
    38
  • Renext
    我看评论有人误解 文章所说的 完全二叉树--“最后一层的叶子节点都靠左排列。”然而图例中 I 节点明明是右节点,怎么就被称作完全二叉树?其实刚开始我也理解错了。这里说的 “最后一层的叶子节点都靠左排列”不是最后一层的子节点是左节点,而是指最后一层的子节点,从 左数到右是连续,中间没有断开,缺少节点(如图例H、I、J是连续的)。结合下文所说的基于数组的顺序存储法,可以知道完全二叉树是不会浪费内存的。其实简单理解,完全是为了省内存而提出这样的概念
    2019-04-28
    33
  • LeoBing
    恕我愚钝。完全二叉树最后一层叶节点都靠左。可是图上节点9是靠右的,是不是我理解有什么问题,请教老师
    2018-11-17
    2
    17
  • Laughing_Lz
    /**
    * 层次遍历二叉树
    *
    * @param root
    */
    public static void levelOrder(Node root) {
    if (root == null) {
    return;
    }
    LinkedList<Node> queue = new LinkedList<Node>();
    queue.add(root);
    while (!queue.isEmpty()) {
    Node currentNode = queue.poll();
    System.out.print(currentNode.getValue() + " ");
    if (currentNode.getLeft() != null) {
    queue.add(currentNode.getLeft());
    }
    if (currentNode.getRight() != null) {
    queue.add(currentNode.getRight());
    }
    }
    }
    2018-11-30
    1
    15
  • 前、中、后序遍历,主要是针对父节点的打印顺序。父左右为前序,左父右为中序,左右父为后序
    2019-03-15
    1
    12
  • 明翼
    我看很多人计算第一题都按照完全二叉树计算的,实际上并没有说完全二叉树,所以n阶乘肯定不对吧,只要是二叉树按照文中规则肯定可以按照数组存储,六个数字,前面五个数字最多浪费四个位置加上本身存储五个就是九个位置,然后六可以浪费一个,那就是一共十个位置,六个数字,有多少种放法就有多少种二叉树。
    2018-12-16
    1
    12
  • Liam
    1 递归地理解一下:按住根节点,如果有k个左节点,则有n-k-1个右节点,分步乘法,f(n) = f(k) * f(n - k - 1) ,k可能性从0 到 n - 1 ,分步加法: f(n) = f(0)f(n-1) + ... + f(n-1)f(0) ,怎么计算该递推公式呢?参考Catalon数
    2018-11-12
    12
  • 天二
    老师 你在计算便利二叉树时间复杂度的时候说,“从我前面画的前、中、后序遍历的顺序图,可以看出来,每个节点最多会被访问两次”, 我想知道都是哪两次呢? 可否帮忙解惑,从图中没看出来

    作者回复: 第一次遍历到的时候算一次。递归返回的时候再一次。不过,这些说法都很笼统,你只要知道每个节点都被访问了一次,并且被访问的次数是常数次就可以了。

    2019-01-21
    11
  • Rephontil
    现在评论的小伙伴少了好多,坚持学习的小伙伴是不是越来越少了?大家的热情呢?💪

    作者回复: 有些人学得慢 或者工作耽搁了。一直追着最新的看的不多

    2018-11-21
    10
  • 极明
    感谢老师让我明白了为什么需要完全二叉树
    2019-02-05
    4
  • nothing
    后序遍历节点不是最多被访问三次嘛, 还有那个深度我们学的深度和层次是一样的哇

    作者回复: 1 从图上看是两次
    2 从生活中的理解来说 应该没有第0层之说 但是有深度为0的说法

    2018-11-12
    4
  • 往事随风,顺其自然
    按照蹭便利使用队列,广度优先搜索
    2018-11-12
    4
  • 朱龙凯
    通过数组存储二叉树,可以从0开始,左右子节点下标分别是2*i+1和2*i+2
    2019-06-05
    3
  • kakasi
    思考题:
    1. 一组数能构建多少个二叉树?
    第一时间想到只要排列位置有改变,那么就应该是新的二叉树。组合排列的公式有点忘记了。。。那么用笨方法:
    当只有1个数的时候,能构建1个二叉树;2个数时是2个二叉树;3个数有6个二叉树;再看下4个数,原来是24个;最后得出n!
    2. 层序遍历二叉树:
    数组和链表的方式都一样。先打印本身的数据,然后将左右节点塞到一个队列中;从队列里取第一个节点打印数据,并将其左右节点再塞到队列,以此类推。
    2018-11-26
    3
  • 传说中的成大大
    刚刚思考了完全二叉树的定义 叶子结点必须要在最后两层 如果不在最后两层的话通过数组顺序存储也会浪费空间吧

    作者回复: 是的

    2018-11-12
    3
  • D→_→M
    老师是否可以在您专栏的github上传一下二叉树这几节的相关代码,还有除了递归遍历二叉树,循环遍历是否也可以讲一下,或者在github上上传一下相关代码,自行研究学习。

    作者回复: 非递归遍历比较复杂 不建议非得给自己制造学习难度 除非是为了面试。其他的二叉树的代码我会放到github上

    2018-11-12
    3
收起评论
99+
返回
顶部