1 满二叉树(full tree)
2 完全二叉树 (complete tree)
特点:从上到下从左到右编号,编号能连续。
3 二叉搜索树(二叉查找树,二叉排序树) (binary search tree, BST)
特点:左子树的所有节点都小于根节点,右子树的所有节点都不小于根节点;子树也分别为二叉搜索树。
查找时,类似二分法,最优是O(logN)。最差是O(N),如下一条腿特别长,需要挨个遍历:
4 二叉平衡树(AVL,平衡二叉搜索树)
优化了二叉搜索树,防止出现一条腿特别长的情况。
特点:左右子树高度差不超过1;子树也是二叉平衡树。
(二叉平衡树不一定是完全二叉树,如上图)
插入节点的时候,为了保持平衡,会进行旋转,这部分可以参考:AVL Tree | Set 1 (Insertion) - GeeksforGeeks 或者 平衡二叉树_清风拂来水波不兴的博客-CSDN博客_平衡二叉树
标签:各种,tree,二叉,子树,二叉树,平衡,节点 From: https://www.cnblogs.com/zxq89/p/16810869.html