一、二叉树

        二叉树：每个节点最多有两个子树的树结构，它可以有五种形态：空集、根节点与空左右子树、根节点与左子树、根节点与右子树以及根节点与左右子树。

性质：

        1.二叉树每层最多节点个数为2^(n-1) (其中n>=1);

        2.深度为n的二叉树最多能拥有2^n-1个子节点(n>=1);

        3.在任意一颗二叉树中，有n0个叶子节点，有n2个度为2的节点，则有n0 = n2 + 1;

        4.具有n个节点的满二叉树深度为 + 1;

        5.任意一颗二叉树，节点个数 = 分支个数 + 1，即n = B + 1.

类别：

1.满二叉树：

        定义：除了叶子节点外的节点都有左右子叶，且所有叶子节点都处于同一深度层。

2.完全二叉树：

        定义：一颗深度为k节点个数为n的二叉树，对树中的节点进行从上到下、从左到右排序编号，编号为i（1<=i<=n）的节点与满二叉树中编号为i的节点所在的位置相同，那么这颗二叉树被称为完全二叉树。

 二叉树存储方式：

1.顺序存储：

         采用数组存储的好处：内存连续，可以通过下标随机访问，坏处在于对于单支二叉树这种结构数组空数据太多，浪费内存空间。

2.链式存储：

        二叉树也可以采用链表结构实现，每个节点由三部分组成：数据域、左子节点域、右子节点域。

二叉树的遍历

        二叉树的遍历总共可分为：前序遍历、中序遍历、后序遍历以及层序遍历。

1.前序遍历（根-左-右）

        访问根节点，访问当前节点的左子节点，若当前节点无左子节点，则访问当前节点的右子节点。

 2.中序遍历（左-根-右）

        先访问当前节点左子树；访问根节点；访问当前节点右子树。

3.后序遍历（左-右-根）

        先访问左子树，再访问右子树，最后访问根节点。 

4.层序遍历

        根据深度逐层遍历节点。

 

 二、二叉排序树

.....待更新