前言
写在前面的话：数据结构与算法。
对于初识数据结构的小伙伴们，鉴于后面的数据结构的构建会使用到同tag前面的内容，包括具体数据结构的应用，所使用到的数据结构，也是自己构建的，未使用系统的库文件，因此，建议这类小伙伴们按顺序进行学习；
对于想查询有关资料的小伙伴们，可以选择性地浏览。希望大家都能有所收获～
二叉树基本概念
上一章，我们介绍了队列结构。从本章开始，我们会陆续接触到一些非线性数据结构，由前面的学习我们知道，对一个数据系统而言，如果查找操作比较频繁的话，一般采用顺序结构存储；如果删除，插入操作比较频繁的话，一般采用链式结构存储；
那我们想一想，有没有这样一种数据结构，其兼有顺序结构和链式结构的优点？
有！树形结构！。
树形结构中最基础，最重要的，非二叉树莫属。本节主要介绍二叉树中的一些基本概念：
定义：
二叉树是每个结点最多有两个子树的树结构。概念：
节点的度：一个节点含有的子树的个数称为该节点的度；
叶节点：度为0的节点称为叶节点；
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
兄弟节点：具有相同父节点的节点互称为兄弟节点；
树的度：一棵树中，最大的节点的度称为树的度；
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度：树中节点的最大层次；
兄弟节点：双亲在同一层的节点互为兄弟节点；
节点的祖先：从根到该节点所经分支上的所有节点；
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
森林：由m棵互不相交的树的集合称为森林；基本性质：
性质1：二叉树第i层上的结点数目最多为2^i-1(i>=1);
性质2：深度为k的二叉树至多有2k-1个结点(k>=1);
性质3：包含n个结点的二叉树的高度至少为[log2n]+1; (向下取整)
性质4：在任意一棵二叉树中，若叶结点的个数为n1，度为2的结点数为n2，则n1=n2+1;特殊二叉树：
–满二叉树
定义：高度为h，并且由2^h-1个结点组成的二叉树，称为满二叉树
–完全二叉树
定义：一棵二叉树中，只有最下面两层结点的度可以小于2，
并且最下层的叶结点集中在靠左的若干位置上，这样的二叉树称为完全二叉树。
特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。
显然，满二叉树必定是完全二叉树，而完全二叉树未必是满二叉树。二叉树的三种遍历：
– 前序遍历：根节点->左子树->右子树。
在遍历左右子树时，仍然先访问根节点，再遍历左子树，最后遍历右子树。
– 中序遍历：左子树->根节点->右子树。
在遍历左右子树时，仍然先遍历左子树，再遍历根节点，最后遍历右子树。
– 后序遍历：左子树->右子树->根节点。
在遍历左右子树时，仍然先遍历左子树，再遍历右子树，最后访问根节点。
下一章将介绍二叉树的构建过程。
