树型结构：

树型结构：

      1、树的基本概念

        一种表示层次关系（一对多）的数据结构

        有且只有一个特定的节点，该节点没有前趋，被称为根节点

        剩余的n个互不相交的子集，每个子集也是一棵树，都被称为根节点的子树

        注意：树型结构具有递归性（树中有树）

    2、树的表示方法

        倒悬树、嵌套法、凹凸法

    3、树的专业术语

        节点：组成树的基础元素，同时它也是一棵树

        节点的度：该节点的子树的数量

        树的度（密度）：树中节点的数量

        树的深度（高度）：树的最大层数

        节点的层次：根节点的层次是1，它的孩子层次为2，孩子的孩子层次为3

        叶子节点：节点的度为0的节点

        双亲和孩子：节点的子树称为该节点的孩子节点，该节点是孩子节点的双亲节点

        兄弟节点：具有同一个双亲，互为兄弟

        堂兄弟节点：双亲节点在同一层上，但双亲不同，则它们互为堂兄弟节点

        叔叔节点：与该节点的双亲节点互为兄弟节点的节点，称为该节点的叔叔节点

        祖先：从根节点出发到某个节点，过程中经过的所有节点都称为该节点的祖先

        子孙：从某个节点出发，经过所有的节点都称为它的子孙

        森林：由n个不相交的树组成的集合称为森林

    4、树的存储方式

        树可以顺序、链式存储，也可以混合存储，

        由于存储的信息不同，有以下的存储表示方法：

            双亲表示法：顺序

                位置    data    双亲位置

                 0       A         -1

                 1       B         0

                 2       C         0

                 3       D         0

                 4       E         1

                优点：方便找到双亲+

                缺点：不方便找孩子

            孩子表示法：

                顺序：

                位置    data    孩子数组

                 0       A      1、2、3

                 1       B      4、5

                 2       C      6

                 3       D      7

                 4       E

                缺点：浪费空间

                混合：

                位置    data    listhead（孩子的下标）

                 0       A      1->2->3->NULL

                 1       B      4->5->NULL

                 2       C      6->NULL

                 3       D      7->NULL

                 4       E      NULL

                优点：节约空间、找孩子方便

                缺点：不方便找双亲

            兄弟表示法：

                双亲只存储自己的数据+第一个子节点+链式指向所有的兄弟节点

                优点：方便找兄弟、孩子

                缺点：不方便找双亲

        注意：三种表示法可以存储任何的普通树，但是普通树不过多研究，重点研究二叉树

二叉树：

    是一种常用的数据结构，处理起来比普通树简单，而且普通树也可以转换成二叉树

    定义：所有节点的度最多为2

    二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的

    元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，

    称该二叉树为空二叉树

    特殊类型：

        满二叉树：

            每层的节点数都是2^(i-1)，这种树叫做满二叉树

        完全二叉树：

            深度为k，有n个节点的二叉树当且仅当其每一个节点都与

            深度为k的满二叉树中编号从1到n的节点一一对应时，称为完全二叉树

    性质：

        性质1：二叉树的第i层上至多有2^(i-1)（i≥1）个节点。

        性质2：深度为h的二叉树中至多含有2^h-1个节点。

        性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1。

        性质4：具有n个节点的完全二叉树深为log2 x +1（其中x表示不大于n的最大整数）。

        性质5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：

        当i=1时，该节点为根，它无双亲节点。

        当i>1时，该节点的双亲节点的编号为i/2。

        若2i≤n，则有编号为2i的左节点，否则没有左节点。

        若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点。