二叉树：二叉树的类型有哪些？详细指南

我们已经讨论过第1套​​二叉树简介和集合2中的二叉树的属性。在这篇文章中, 讨论了二叉树的常见类型。

以下是二叉树的常见类型。

满二叉树：如果每个节点都有0或2个子节点, 则二叉树就是满二叉树。以下是满二叉树的示例。我们也可以说满二叉树是一个二叉树, 其中除叶节点外的所有节点都有两个孩子。

18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40

             18
           /    \   
         15     20    
        /  \       
      40    50   
    /   \
   30   50

               18
            /     \  
          40       30  
                   /  \
                 100   40

完全二叉树：如果所有的关卡都被填满了，那么二叉树就是完全二叉树

下面是完全二叉树的例子

18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40


               18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40
     /  \   /
    8   7  9

完全二叉树的实例是二叉堆。

完美二叉树

二叉树是一种完美二叉树, 其中所有内部节点都有两个子节点, 所有叶节点都处于同一级别。

以下是完美二叉树的示例。

18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40


               18
           /       \  
         15         30

在完美二叉树中，叶节点的数量等于内部节点的数量加1

其中L = I + 1, L =叶节点数，I =内部节点数。

一棵高度为h的完美二叉树(二叉树的高度是从根节点到树中任何叶节点的最长路径)有2^(h+1) - 1个节点。

完美二叉树的一个例子就是家族中的祖先。32、将一个节点作为根，父节点作为子字节，父节点的父节点作为他们的子节点

平衡二叉树

如果二叉树的高度为O(Log n), 则二叉树是平衡的, 其中n是节点数。例如, AVL树通过确保左右子树的高度差几乎为1来维持O(Log n)的高度。红黑树通过确保树的数量保持O(Log n)的高度。每个根到叶路径上的黑色节点都是相同的, 并且没有相邻的红色节点。平衡的二进制搜索树在性能方面很不错, 因为它们为搜索, 插入和删除提供了O(log n)时间。

退化的(或病理的)树一棵树, 其中每个内部节点都有一个子节点。这样的树在性能上与链表相同。

10
      /
    20
     \
     30
      \
      40

参考资源：https://zh.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。