回顾：

    栈——先进先出FILO

    队列——先进后出FIFO

树形结构（逻辑结构）

struct Node{//树结点的定义

    EleType data;//树结点的数据域

    Node *child[];//子结点指针集合

};

    对于子结点指针，有可能用数组实现，也可能用链表实现，树还可以使用数组实现，只需记录每个结点的父结点即可。

    树的基础术语：

    1、父结点、子结点、兄弟结点，祖先、子孙

    2、结点的度，树的度

        结点的度——几个子结点

        树的度——结点的度的最大值

    3、叶子结点（终端结点）与分支结点（非终端结点）

            度为零                                    度不为零

    4、结点的深度，高度和层次

    5、路径和路径长度

森林——树的集合

    例题1：度为4的树，度为4的结点2个，度为3的结点2个，度为2的结点0个，度为1的结点5个，总共有几个结点？

画图法——

解析法——度为4的结点2个（2*4=8），度为3的结点2个（3*2=6）....

                    合计8+6+0+5+1（根结点） = 20个

例题2：度为5的树，度为5的结点2个，度为4的结点3个，度为3的结点5个，度为2的结点10个，度为1的结点20个，求总结点数和叶子结点数。

    解析法：5*2+4*3+3*5+2*10+1*20+1=78个总结点数

                78-2-3-5-10-20=38个叶子结点（度为零）

二叉树——度为2、1、0，且严格区分左右

struct Node{//二叉树的结点定义

    EleType data;//二叉树结点的数据域

    Node *left_child, *right_child;//左子结点与右子结点指针

};

左子树与右子树常写作left(lchild)和right(rchild),同理二叉树也能使用数组来存储。

二叉树的基本术语：

    1、左孩子（左子树），右孩子（右子树）

    2、每层的结点个数

    每层最多有多少个结点

        第一层：1个

        第二层：2个

        第三层：4个

        第n层：2^(n-1)个

        总共最多有2^n-1个

    3、满二叉树，完全二叉树

        高度为10的满二叉树有2^10-1=1023结点。

        完全二叉树可以删掉最后一层最靠右的结点，满二叉树是特殊的完全二叉树

    4、使用一维数组存储二叉树

例如：若树根数组下标为1，某结点下标x，左结点下标2*x,右结点2*x+1

    5、广义表

结点（左子树（），右子树（））

例题1：完全二叉树第四层有四个叶子结点，总共有多少个结点？

    若总共有4层，则1+2+4+4=11个

    若总共有5层且父结点都有右子树，则1+2+4+8+8=23个，否则为23-1=22个