二叉树|集合 3(二叉树的类型)

原文:https://www . geesforgeks . org/二叉树-set-3-类型的二叉树/

我们已经讨论了第 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 的完美二叉树(其中二叉树的高度是从根节点到树中任何叶节点的最长路径，根节点的高度为 1)有 2h–1 个节点。

完美二叉树的一个例子是家族中的祖先。把一个人放在根上，把父母当成孩子，把父母的父母当成自己的孩子。

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

退化(或病态)树每个内部节点都有一个子节点的树。这种树在性能方面与链表相同。

      10
      /
    20
     \
     30
      \
      40

来源: https://en . Wikipedia . org/wiki/Binary _ tree # Types _ of _ Binary _ trees

如果您发现任何不正确的地方，或者您想分享更多关于上面讨论的主题的信息，请写评论

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：https://www.moonapi.com/news/30889.html