二叉树（二叉树的类型有哪些（详细指南））

我们已经讨论过第1套??二叉树简介和集合2中的二叉树的属性。在这篇文章中, 讨论了二叉树的常见类型。
以下是二叉树的常见类型。
满二叉树：如果每个节点都有0或2个子节点, 则二叉树就是满二叉树。以下是满二叉树的示例。我们也可以说满二叉树是一个二叉树, 其中除叶节点外的所有节点都有两个孩子。

18 /\ 1530 /\/\ 40501004018 /\ 1520 /\ 4050 /\ 305018 /\ 4030 /\ 10040

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

18 /\ 1530 /\/\ 40501004018 /\ 1530 /\/\ 405010040 /\/ 879

完全二叉树的实例是二叉堆。
完美二叉树
二叉树是一种完美二叉树, 其中所有内部节点都有两个子节点, 所有叶节点都处于同一级别。
以下是完美二叉树的示例。

18 /\ 1530 /\/\ 40501004018 /\ 1530

在完美二叉树中，叶节点的数量等于内部节点的数量加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)时间。
退化的(或病理的)树一棵树, 其中每个内部节点都有一个子节点。这样的树在性能上与链表相同。