二叉树

1、什么是二叉树

• 一种特殊的树，是非线性结构
• 叶子、深度、度、子树、根依然适用于二叉树
• 比普通树多一个限定：每个结点最多只有两颗子树，左子树和右子树
• 每个结点的度最大为2
  

2、二叉树的基本性质

• 在二叉树的第n层上，最多有2的(n-1)次方个结点，比如根结点在第一层，第一层最多只能用1个结点
• 深度为n的二叉树，最多有（2的n次方-1）个结点
• 在任意一颗二叉树中，度为0的结点总是比度为2的结点多1个
• 具有n个结点的二叉树，其深度至少为(以2为底n的对数)取整 +1

3、满二叉树

• 除了最后一层外，每一层上的所有结点都有两个子结点
• 在满二叉树的第n层上，有2的（n-1）个结点
• 深度为m的满二叉树，有2的m次方-1个结点

4、完全二叉树

• 除最后一层外，每一层上的结点数都达到最大值
• 最后一层上只缺少右边的若干结点
• 满二叉树就是一颗完全二叉树。但是完全二叉树不一定是满二叉树
• 有n个结点的完全二叉树，其深度为(以2为底n的对数)取整 +1

5、平衡二叉树（AVL树）

• 是一棵空树或它的任意结点的左右两个子树的高度差的绝对值不超过1

6、二叉排序树

• 又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高
• 一棵空树，或者是具有下列性质的二叉树：
• 若左子树不空，则左子树上所有结点的值均小于它的根结点的值
• 若右子树不空，则右子树上所有结点的值均大于它的根结点的值
• 左、右子树也分别为二叉排序树
• 没有键值相等的结点

7、二叉树的存储结构

• 二叉链表存储二叉树
• 左右子树分别存的是子树的序号，根据序号去查找子树，没有子树就用0表示
• 还有一个指向根结点的指针，这样我们就知道根结点是哪个

本文地址：https://blog.csdn.net/weixin_43365369/article/details/107636329