一、二叉树

1、二叉树的概念

二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree），其次序不能任意颠倒。

2、性质

（1）若二叉树的层次从0开始，则在二叉树的第i层至多有2^i个结点(i>=0)；

（2）高度为k的二叉树最多有2^(k+1) - 1个结点(k>=-1)。 (空树的高度为-1)；

（3）对任何一棵二叉树，如果其叶子结点(度为0)数为m, 度为2的结点数为n, 则m = n + 1。

二、几种特殊的二叉树

1、满二叉树

所有叶结点同处于最底层（非底层结点均是内部结点），一个深度为k(>=-1)且有2^(k+1) - 1个结点。如图（图来源于veil的博客）：

2、完全二叉树

叶结点只能出现在最底层的两层，且最底层叶结点均处于次底层叶结点的左侧。规模为n的完全二叉树，高度为

3、平衡二叉树

平衡二叉树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci(斐波那契)数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

对于平衡二叉树要特别注意的是，不要求非叶节点都有两个子结点，仅要求两个子树的高度差的绝对值不超过1，或者为空树。

三、存储方式

存储的方式和图一样，有链表和数组两种，用数组存访问速度快，但插入、删除节点操作就比较费时了。实际中更多的是用链来表示二叉树的。

四、遍历方式

三种遍历方式  访问节点的顺序是一致的，不同之处在于，有的遍历流程把访问到的节点暂存起来，达成某种条件后再将节点输出。约定， 根节点V, 其左孩子为L, 右孩子为R, 那么遍历顺序可以记为：

Pre-Order Traversal ： 到达一个节点后，即刻输出该节点的值，并继续遍历其左右子树。 VLR

In-Order Traversal  ：   到达一个节点后，将其暂存，遍历完左子树后，再输出该节点的值，然后遍历右子树LVR

Post-Order Traversal:   到达一个节点后，将其暂存，遍历完左右子树后，再输出该节点的值。 LRV

        先序遍历，中序遍历，后序遍历，这个“顺序”指的是输出父节点的顺序，不是访问的顺序，也不是简单的按照二叉树“从左往右”、“从上往下”等。

遍历结果：

二叉树的遍历 （C++实现）_zhhp1001的博客-CSDN博客

二叉树的几种类型 - 王大咩的图书馆 - 博客园