什么是二叉树（binary tree）？

在树结构的基础上，要求其中每个节点最多有两个子节点（一个节点最多有2个边）。

二叉树由根节点和若干个左子树和右子树构成，这些子树也都是二叉树。二叉树可以为空树，也可以只包含一个根节点。

为什么树形结构常用二叉树呢？

就是为了省空间。n叉树，n越大就需要更多的链接建立节点与子节点的关系。推导如下：

树结构一般使用链表（Linked List）存储，对于n叉树（n-way树），虽然每个节点的度数不可能都是n，但每个节点必须预留n个链接，用于建立父子节点关系。因此每个节点的数据结构如下：

 这种n叉树十分浪费链接存储空间。

假设此n叉树有m个节点，那么此书需要n*m个链接/指针(每个节点都必须拥有n个链接)。除了根节点以外，每个非空链接都指向一个节点（有m-1个节点就有m-1节点链接/指针，这些链接没有浪费即为非空链接），得知空链接总数为n * m  - (m - 1) = m(n-1) + 1,而n叉树的链接浪费率为 m(n-1) + 1除以n * m。因此可以得到结论：

1.  n=2时，2叉树的链接浪费率为（m+1）/ 2m,浪费率约为二分之一

2.  n=3时，3叉树的链接浪费率为（2m+1）/ 3m,浪费率约为三分之二

3.  n=4时，4叉树的链接浪费率为（3m+1）/ 4m,浪费率约为四分之三

……

因此得到n=2时即2叉树的链接浪费率最低，因此常使用二叉树来取代其他树结构。

二叉树与一般树的不同之处

1. 是否可以是空结合：树不可以为空集合，但二叉树可以为空集合

2. 度数的范围：树的度数范围是大于等于0，而二叉树大于等于0且小于等于2

3. 子树关系：树的子树间没有次序关系，而二叉树有（主要涉及插入顺序、遍历顺序、搜索和排序）

二叉树涉及的数学证明

1. 高度为k的二叉树的总节点数是2^k-1(最多)，其中k大于等于1

为了实现总结点最多，每一层都挂满子节点

2⁰ + 2¹+ 2²+ ……+2^k-1=2^k-1

https://i.cnblogs.com/posts/edit-done;postId=17795378;isPublished=false

2. 二叉树第i层上的结点数目最多为2^i-1(i≥1)

因为是二叉树，一个节点最多有2个子节点，除了第1层根节点是1个。其他层节点最多都是2的倍数。即

第1层：2⁰

第2层：2¹

第3层：2²

……

第i层：2^i-1

 3. 在任意-棵二叉树中，若终端结点(叶子节点)的个数为n₀，度为2的结点数为n₂，则n_o=n₂+1。

推导过程：

假设

　　1. 叶子节点数：n₀

　　2. 度数为1的节点数：n₁

　　3. 读数为2的节点数：n₂

　　4. 总节点数：n

        5. 二叉树的总边数：e

从节点数得到：n=n₀ +  n₁ + n₂

已知边数与节点数关系：n=e+1

边数与度数为2、1、0节点的关系：

　　1. 一个度数为2的节点有2个边，  n₂个有2n₂个边。

　　2. 一个度数为1的节点有1个边， n₁个有 n₁个边。

　　3. 度数为0的节点，没有边。

从而得到结论： e= 2n₂ +  n₁

进而得到 n=n₀ +  n₁ + n₂ = e +1 = 2n₂ +  n₁ + 1  ==> n_o=n₂+1

特殊情形

满二叉树

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。

 完全二叉树

完全二叉树是满二叉树的一个特例

完全二叉树(Complete Binary Tree):假设二叉树的高度为h。除第h层外，其它各层(0～h-1)的结点数都达到最大个数（2^k-1），第h层从右向左连续缺若干结点，这就是完全二叉树

上述所说从右向左缺若干节点，也就是说在h层的时候，如果有节点都在左半边，而缺的都是右半边的节点，这就是完全二叉树！

BST树(二叉搜索树)

对于树上的每个节点来说，其左孩子的节点比双亲节点小,其右孩子的节点比双亲结点大，移除根节点，形成的左子树和右子树也都按照这个规则排序。

平衡二叉搜索树(AVL树)

两子树高度相差不超过1的搜索二叉树即为平衡搜索二叉树

对称二叉树（Symmetric Binary Tree）

对称二叉树（Symmetric Binary Tree）是一种特殊的二叉树，其中树的结构呈现对称性。这意味着，树的根节点具有两个子节点，这两个子节点的结构是镜像对称的，它们的左子树是对方右子树的镜像，而右子树是对方左子树的镜像。这就意味着树从根节点开始向下延伸，左子树和右子树的结构是对称的。

在这个示例中，树的根节点是1，左子树是以2为根的子树，右子树也是以2为根的子树。而且，这两个子树的结构是镜像对称的，它们的左子树和右子树也是镜像对称的。这使得整个二叉树成为一个对称二叉树。

对称二叉树在编程和数据结构中经常出现，通常用于解决一些与对称性相关的问题。在验证一个二叉树是否是对称二叉树时，通常可以使用递归算法或迭代算法来检查树的左子树和右子树是否镜像对称。