二叉树的相关概念

二叉树的种类

满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

 深度为k，节点数为2^k  -1

完全二叉树

在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 k 层，则该层包含 1~ 2^(k-1)  个节点

 二叉搜索树

 它的左右子树也是如此

平衡二叉搜索树AVL

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

C++中map,set,multimap,multiset的底层实现为平衡二叉搜索树

unordered系列的底层实现是哈希表

二叉树的存储方式

链式存储

顺序存储

父节点是i，那么左孩子是i*2+1，右孩子是i*2+2

二叉树数据结构定义

 二叉树的遍历

递归

前序遍历：

 另外两个遍历只需要调整一下打印或者放入数组这条语句的位置！

递归较简单，迭代怎么实现前中后序遍历呢？

递归的实质是：每一次递归，会把当前各种信息压入栈中

递归返回时，弹出，返回上一层

因此我们可以用栈来实现！

 对于前序遍历，访问顺序和处理顺序是一致的，所以代码较为简洁

但中序遍历不行

 后序遍历仅需要在前序遍历的基础上做些修改

 接下来是利用队列实现的二叉树层序遍历