自学嵌入式第二十五天：数据结构-队列、树

一、队列

        队列是只允许一段进行插入，另一端进行删除操作的线性表；

        允许插入的一端叫队尾，允许删除的一端叫对头；

        先进先出；

        用于解决速度不匹配（例如一快一慢），做缓冲用；

二、树

        1.树：有n个结点的有限集合，n=0时是空树；

        在任意非空树中：有且仅有一个根结点；n>1时又分几个互不相交子树；

        结点拥有子树的个数称谓为度；

        度为0的（最下面的）叫叶子结点，度不为0的（中间的）叫分支结点；

        度最大的结点的度数叫树的度；

        树的高度（或深度）从根开始，根为第一层，根的孩子为第二层；

        2.二叉树

        n个结点的有限集合，集合要么为空树，要么由一个根结点和两颗互不相交的二叉树组成；

        每个结点最多两个子树；左子树和右子树是有顺序的，次序不能颠倒；如果结点只有一个子树也要区分左右子树；

        斜树：假设所有结点都只有左子树的叫左斜树；

        满二叉树：所有分支都存在左右子树，叶子节点都在同一层；

        完全二叉树 ：按层序编号的二叉树；

        特性：

        （1）在第i层最多有2的i-1次方（2^(i-1)）个结点；

        （2）深度为k的二叉树最多有2的k次方-1个结点（2^k-1）；

        （3）一个二叉树，如果有n0个叶子结点，度数为2的结点数为n0-1；

        （4）有n个结点的完全二叉树深度为(logn/long2)+1；

        3.树的层序遍历（广度遍历）

        4.树的深度遍历（前序，中序，后序）

                前序：根左右：先访问根，然后访问左，访问右；

                中序：左根右：从根开始（不访问），先访问左，再访问根，最后访问右；

                后序：左右根：从根开始（不访问），先访问左，再访问右，最后访问根；