二叉树类型

二叉树类型

满二叉树 (full binary tree)：

A Binary Tree is a full binary tree if every node has 0 or 2 children

完全二叉树 (complete binary tree):

A Binary Tree is a Complete Binary Tree if all the levels are completely filled except possibly the last level and the last level has all keys as left as possible

完美二叉树 (perfect binary tree):

A Binary tree is a Perfect Binary Tree in which all the internal nodes have two children and all leaf nodes are at the same level.

平衡二叉树 (Balanced binary tree):

A binary tree is balanced if the height of the tree is O(Log n) where n is the number of nodes. For Example, the AVL tree maintains O(Log n) height by making sure that the difference between the heights of the left and right subtrees is at most 1. Red-Black trees maintain O(Log n) height by making sure that the number of Black nodes on every root to leaf paths is the same and there are no adjacent red nodes. Balanced Binary Search trees are performance-wise good as they provide ** O(log n) ** time for search, insert and delete.

衰减树形(A degenerate or pathological tree)

A Tree where every internal node has one child. Such trees are performance-wise same as linked list.

二叉树类型

原文：https://www.cnblogs.com/ultramanX/p/14839963.html