扫一扫下方二维码,关注本站官方公众号
获取永久解锁本站全部文章的验证码
还能不定期领现金红包

数据结构与算法-基础算法篇-二叉树-Go语言中文社区

数据结构与算法-基础算法篇-二叉树


1. 树

1. 树的常用概念

根节点、叶子节点、父节点、子节点、兄弟节点,还有节点的高度、深度以及层数,树的高度。

2.概念解释

  1. 节点:树中的每个元素称为节点
  2. 父子关系:相邻两节点的连线,称为父子关系
  3. 根节点:没有父节点的节点
  4. 叶子节点:没有子节点的节点
  5. 父节点:指向子节点的节点
  6. 子节点:被父节点指向的节点
  7. 兄弟节点:具有相同父节点的多个节点称为兄弟节点关系
  8. 节点的高度:节点到叶子节点的最长路径所包含的边数
  9. 节点的深度:根节点到节点的路径所包含的边数
  10. 节点的层数:节点的深度+1(根节点的层数是1)
  11. 树的高度:等于根节点的高度

2. 二叉树

1. 概念

  1. 什么是二叉树
    每个节点最多只有2个子节点的树,这两个节点分别是左子节点和右子节点。
  2. 什么是满二叉树
    如果二叉树中除了叶子结点,每个结点的度都为 2,则此二叉树称为满二叉树。
  3. 什么是完全二叉树
    如果二叉树中除去最后一层节点为满二叉树,且最后一层的结点依次从左到右分布,则此二叉树被称为完全二叉树。

二叉树示意图

满二叉树示意图

完全二叉树示意图

2. 性质

  1. 二叉树具有以下几个性质:
    1. 二叉树中,第 i 层最多有2i-1 个结点。
    2. 如果二叉树的深度为 K,那么此二叉树最多有 2K-1 个结点。
    3. 二叉树中,终端结点数(叶子结点数)为 n0,度为 2 的结点数为 n2,则 n0=n2+1
  2. 满二叉树除了满足普通二叉树的性质,还具有以下性质:
    1. 满二叉树中第 i 层的节点数为 2n-1个。
    2. 深度为 k 的满二叉树必有2k-1个节点 ,叶子数为 2k-1
    3. 满二叉树中不存在度为 1 的节点,每一个分支点中都两棵深度相同的子树,且叶子节点都在最底层。
    4. 具有 n 个节点的满二叉树的深度为 log2(n+1)。
  3. 完全二叉树独特的性质:n 个结点的完全二叉树的深度为 ⌊log2n⌋+1。完全二叉树还有以下几个结论成立:
    1. i>1时,父亲结点为结点[i/2] 。(i=1 时,表示的是根结点,无父亲结点)
    2. 如果 2*i>n(总结点的个数),则结点 i 肯定没有左孩子(为叶子结点);否则其左孩子是结点 2*i
    3. 如果 2*i+1>n,则结点 i 肯定没有右孩子;否则右孩子是结点 2*i+1

2. 完全二叉树的存储

  1. 链式存储
    每个节点由3个字段,其中一个存储数据,另外两个是指向左右子节点的指针。我们只要拎住根节点,就可以通过左右子节点的指针,把整棵树都串起来。这种存储方式比较常用,大部分二叉树代码都是通过这种方式实现的。
  2. 顺序存储
    用数组来存储,对于完全二叉树,如果节点X存储在数组中的下标为i,那么它的左子节点的存储下标为2*i,右子节点的下标为 2*i+1,反过来,下标i/2位置存储的就是该节点的父节点。注意,根节点存储在下标为1的位置。完全二叉树用数组来存储时最省内存的方式。

3. 二叉树的遍历

  1. 前序遍历:对于树中的任意节点来说,先打印这个节点,然后再打印它的左子树,最后打印它的右子树。
  2. 中序遍历:对于树中的任意节点来说,先打印它的左子树,然后再打印它的本身,最后打印它的右子树。
  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

伪代码:

void preOrder(Node* root) {
  if (root == null) return;
  print root
  preOrder(root->left);
  preOrder(root->right);
}

void inOrder(Node* root) {
  if (root == null) return;
  inOrder(root->left);
  print root
  inOrder(root->right);
}

void postOrder(Node* root) {
  if (root == null) return;
  postOrder(root->left);
  postOrder(root->right);
  print root
}

时间复杂度:3种遍历方式中,每个节点最多会被访问2次,所以时间复杂度是O(n)

3. 思考

1. 给定一组数据,比如1,3,5,6,9,10,可以构建出多少种不同的二叉树?

确定两点:

  1. n个数,即n个节点,能构造出多少种不同形态的树?

  2. n个数,有多少种不同的排列?
    当确定以上两点,将 1 的结果 乘以 2的结果,即为最终的结果。
    但是有一个注意的点: 如果n中有相等的数,产生的总排列数就不是n!

    答案就是卡特兰数,是 C[n,2n] / (n+1)种形状,c是组合数,节点的不同又是一个全排列,一共就是n!*C[n,2n] / (n+1)个二叉树。可以通过数学归纳法推导得出

2. 二叉树的遍历方式,前、中、后序。实际上,还有另一种遍历方式,也就是按层遍历,你知道如何实现吗?

private List<TreeNode> floorLevelTree(TreeNode root){
        List<TreeNode> result = new ArrayList<>();
        TreeNode node = root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()){
            node = queue.poll();
            result.add(node);
            if (node.left != null){
                queue.offer(node.left);
            }
            if (node.right != null){
                queue.offer(node.right);
            }
        }
        return result;
    }

3. 二叉查找树

1. 概念

二叉查找树是二叉树中最常用的一种类型,也叫二叉搜索树。顾名思义,二叉查找树是为了实现快速查找而生的。不过,它不仅仅支持快速查找一个数据,还支持快速插入、删除一个数据。

二叉查找树要求,在树中的任意一个节点,其左子树中的每个节点的值,都要小于这个节点的值,而右子树节点的值都大于这个节点的值

img

2. 查询查找

先取根节点,如果它等于我们要查找的数据,那就返回。如果要查找的数据比根节点的值小,那就在左子树中递归查找;如果要查找的数据比根节点的值大,那就在右子树中递归查找。

public class BinarySearchTree {
  private Node tree;

  public Node find(int data) {
    Node p = tree;
    while (p != null) {
      if (data < p.data) p = p.left;
      else if (data > p.data) p = p.right;
      else return p;
    }
    return null;
  }

  public static class Node {
    private int data;
    private Node left;
    private Node right;

    public Node(int data) {
      this.data = data;
    }
  }
}

3. 插入操作

如果要插入的数据比节点的数据大,并且节点的右子树为空,就将新数据直接插到右子节点的位置;如果不为空,就再递归遍历右子树,查找插入位置。同理,如果要插入的数据比节点数值小,并且节点的左子树为空,就将新数据插入到左子节点的位置;如果不为空,就再递归遍历左子树,查找插入位置。

public void insert(int data) {
  if (tree == null) {
    tree = new Node(data);
    return;
  }

  Node p = tree;
  while (p != null) {
    if (data > p.data) {
      if (p.right == null) {
        p.right = new Node(data);
        return;
      }
      p = p.right;
    } else { // data < p.data
      if (p.left == null) {
        p.left = new Node(data);
        return;
      }
      p = p.left;
    }
  }
}

4. 删除操作

针对要删除节点的子节点个数的不同,我们需要分三种情况来处理。

img

  1. 如果要删除的节点没有子节点,我们只需要直接将父节点中,指向要删除节点的指针置为 null。比如图中的删除节点 55。
  2. 如果要删除的节点只有一个子节点(只有左子节点或者右子节点),我们只需要更新父节点中,指向要删除节点的指针,让它指向要删除节点的子节点就可以了。比如图中的删除节点 13。
  3. 如果要删除的节点有两个子节点,这就比较复杂了。我们需要找到这个节点的右子树中的最小节点,把它替换到要删除的节点上。然后再删除掉这个最小节点,因为最小节点肯定没有左子节点(如果有左子结点,那就不是最小节点了),所以,我们可以应用上面两条规则来删除这个最小节点。比如图中的删除节点 18。
public void delete(int data) {
  Node p = tree; // p指向要删除的节点,初始化指向根节点
  Node pp = null; // pp记录的是p的父节点
  while (p != null && p.data != data) {
    pp = p;
    if (data > p.data) p = p.right;
    else p = p.left;
  }
  if (p == null) return; // 没有找到

  // 要删除的节点有两个子节点
  if (p.left != null && p.right != null) { // 查找右子树中最小节点
    Node minP = p.right;
    Node minPP = p; // minPP表示minP的父节点
    while (minP.left != null) {
      minPP = minP;
      minP = minP.left;
    }
    p.data = minP.data; // 将minP的数据替换到p中
    p = minP; // 下面就变成了删除minP了
    pp = minPP;
  }

  // 删除节点是叶子节点或者仅有一个子节点
  Node child; // p的子节点
  if (p.left != null) child = p.left;
  else if (p.right != null) child = p.right;
  else child = null;

  if (pp == null) tree = child; // 删除的是根节点
  else if (pp.left == p) pp.left = child;
  else pp.right = child;
}

5. 其他操作

如:快速地查找最大节点和最小节点、前驱节点和后继节点

中序遍历二叉查找树,可以输出有序的数据序列,时间复杂度是 O(n),非常高效

6. 支持重复数据的二叉查找树

如果存储的两个对象键值相同,这种情况该怎么处理呢?

  1. 第一种方法比较容易。二叉查找树中每一个节点不仅会存储一个数据,因此我们通过链表和支持动态扩容的数组等数据结构,把值相同的数据都存储在同一个节点上。

    img

  2. 第二种方法比较不好理解,不过更加优雅。每个节点仍然只存储一个数据。在查找插入位置的过程中,如果碰到一个节点的值,与要插入数据的值相同,我们就将这个要插入的数据放到这个节点的右子树,也就是说,把这个新插入的数据当作大于这个节点的值来处理。

    img

对于删除操作,我们也需要先查找到每个要删除的节点,然后再按前面讲的删除操作的方法,依次删除

img

7.时间复杂度分析

img

看图可知,查询具体某一个数字的时间复杂度其实都跟树的高度成正比,也就是 O(height),现在问题就转变成另外一个了,也就是,如何求一棵包含 n 个节点的完全二叉树的高度?

对于包含 n 个节点的完全二叉树中,第一层包含 1 个节点,第二层包含 2 个节点,第三层包含 4 个节点,依次类推,下面一层节点个数是上一层的 2 倍,第 K 层包含的节点个数就是 2^(K-1)

n >= 1+2+4+8+...+2^(L-2)+1
n <= 1+2+4+8+...+2^(L-2)+2^(L-1)

借助等比数列的求和公式,可以计算出,L 的范围是[log2(n+1), log2n +1]。完全二叉树的层数小于等于 log2n +1,也就是说,完全二叉树的高度小于等于log2n

8. 思考

1. 散列表的插入、删除、查找操作的时间复杂度可以做到常量级的 O(1),非常高效。而二叉查找树在比较平衡的情况下,插入、删除、查找操作时间复杂度才是 O(logn),相对散列表,好像并没有什么优势,那我们为什么还要用二叉查找树呢
  1. 散列表中的数据是无序存储的,如果要输出有序的数据,需要先进行排序。而对于二叉查找树来说,我们只需要中序遍历,就可以在 O(n) 的时间复杂度内,输出有序的数据序列。
  2. 散列表扩容耗时很多,而且当遇到散列冲突时,性能不稳定,尽管二叉查找树的性能不稳定,但是在工程中,我们最常用的平衡二叉查找树的性能非常稳定,时间复杂度稳定在 O(logn)
  3. 笼统地来说,尽管散列表的查找等操作的时间复杂度是常量级的,但因为哈希冲突的存在,这个常量不一定比 logn 小,所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时,也不一定就比平衡二叉查找树的效率高。
  4. 散列表的构造比二叉查找树要复杂,需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题,而且这个问题的解决方案比较成熟、固定。
  5. 为了避免过多的散列冲突,散列表装载因子不能太大,特别是基于开放寻址法解决冲突的散列表,不然会浪费一定的存储空间
2. 如何通过编程,求出一棵给定二叉树的确切高度呢?

递归公式: depth =Math.max(maxDepth(node.left), maxDepth(node.right) )+ 1;
递归出口: depth = 0 (node == null)

版权声明1:本文来源CSDN,感谢博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。
原文链接:https://blog.csdn.net/z_yemu/article/details/106678716
站方申明:本站部分内容来自社区用户分享,若涉及侵权,请联系站方删除。

0 条评论

请先 登录 后评论

官方社群