23 | 二叉树基础（上）：什么样的二叉树适合用数组来存储？

精选留言(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