二叉树的那些事儿

每一个结点最多只有两棵子树,通常称这种树为二叉树。
在二叉树中严格区分结点的左、右孩子。
因此二叉树是有序树。

有序树
严格区分左右子树

二叉树的5种基本形态

二叉树演化出来的树

二叉查找树、满二叉树、完全二叉树、自平衡二叉树、AVL、红黑树…
头晕,为啥整出这么多树?

分类图

满二叉树

对于任意一个结点,要么是叶子结点,要么它有两个孩子结点

完全二叉树

最下面两层的结点度可以小于2,并且最下面一层结点依次排列在最左边的位置上

自平衡二叉查找树

为啥有这个呢?
因为在一般的二叉查找树中查找某个结点,跟树的深度有关,当深度大的时候,查询复杂度越高。

解决这样的问题:有两种常用的树,就是AVL树和红黑树了。

AVL树

红黑树

红黑树相对于AVL树来说,牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作,整体来说性能要优于AVL树

哈夫曼树


给定一组权值,构造出的具有最小带权路径长度的二叉树称为哈夫曼树,又称为最优二叉树。

斜树

xpisme wechat
微信号