树型结构： 1、树的基本概念 一种表示层次关系的(一对多)数据结构。 有且仅有一个特定的节点，该节点没有前驱，被称为根节点。 剩余的n个互不相交的子集，其中每个子集也都是一棵树，被称为根节点的子树。 注意：树型结构具有递归性（树中有树）。 2、树的表示方法：倒悬树、嵌套法、凹凸法。 3、树的专业术语： 节点：组成树的基础元素，同时它也是一棵树。 节点的度：该节点子树的数量。 树的度(密度)：树中节点的数量。 叶子节点：节点的度为0的节点。 双亲和孩子：节点的子树被称为孩子节点，该节点就是它们的双亲。 兄弟：具有同一个双亲节点，被称为兄弟节点。 祖先：从根节点出发到该节点，经过的所有节点都被称为该节点的祖先。 子孙：一个节点的子树中的任意一个节点都被称为它的子孙。 节点的层次：根节点层次为1，它的孩子层次为2，孩子的孩子层次为3，依次类推。 堂兄弟：双亲在同一层互为堂兄弟。 树的深度：树的最大层次为树的深度。 森林：n个不相交的树的集合被称为森林。 4、树的存储 树可以顺序存储、链式存储，也可以混合存储，由于存储的信息不同，有以下表示方式：
双亲表示法：顺序 位置 data 双亲 0 A -1 1 B 0 2 C 0 3 D 1 4 E 2 5 G 4 6 F 4 7 H 2 优点：方便找到双亲，缺点：查找孩子节点不方便。 孩子表示法： 顺序：浪费空间 位置 data sub_arr 0 A 1,2 1 B 3 2 C 4,7 3 D 4 E 5,6 5 G 6 F 7 H 链式：节约空间 位置 data ListHead 0 A 1 B 2 C 3 D 4 E 5 G 6 F 7 H 优点：方便找孩子，缺点：不方便找双亲结点。 兄弟表示法： 双亲只存储第一个子节点，然后链式指向所有兄弟节点。 优点：可以方便的查询到兄弟节点 缺点：查询双亲比较麻烦 数据 第一个子节点 兄弟节点头指针