二叉树|集合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的完美二叉树（其中二叉树的高度是从根节点到树中任何叶节点的最长路径中的边数，根节点的高度为0）有2个 ^h+1 –1个节点。

完美二叉树的一个例子是家族中的祖先。让一个人在根上，把父母当作孩子，把父母的父母当作他们的孩子。

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

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

      10      /    20          30            40     

资料来源： https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees

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