树的存储结构

双亲表示法

• 特点
  一般采用数组储存
  根结点的双亲规定为-1
  根结点储存在数组下标0的位置

• 优点
  求某结点的双亲和查找根结点很方便

• 缺点

  1. 查找某结点的孩子结点要遍历整个数组（看哪个结点的父结点等于要找的结点）
  2. 兄弟结点的位置关系不明确，如不知道是左孩子结点还是右孩子结点
  3. 随机删除和添加结点复杂

• 数据结构

  java

  public class Node{
   Object data; //数据
   int parent; //父结点下标
  }

• 图示
  

  

要想确定兄弟结点的位置关系可以多添加一个右兄弟结点下标字段

• 数据结构

  java

  public class Node{
   Object data; //数据
   int parent; //父结点下标
   int right; //右兄弟结点下标
  }

• 图示
  

  

孩子表示法

多重链表表示法

• 不同构（各结点孩子指针数不相同）

  • 特点
    孩子指针数等于结点的度。
  • 优点
    节省空间，因为结点有多少个孩子就设多少个孩子指针。
  • 缺点
    代码不好实现，而且树的各种操作也困难，所有一般不采用。
  • 数据结构
    java

    public class Node{
     Object data; //数据
     int degree; //结点的度(有几个孩子)
     Node child1; //第 1 个孩子
     Node child2; //第 2 个孩子
     Node ...
     Node childn; //第 n 个孩子,直到等于结点的度
    }

  • 图示
    

• 同构（各结点孩子指针数相同）

  • 特点
    孩子指针数等于树的度。
  • 优点
    代码可以实现，而且树的各种操作也相对简单。
  • 缺点
    1. 查找双亲结点困难（从根节点开始遍历，看哪个结点的子结点等于要找的结点）
    2. 浪费空间，大多数结点的度一般小于树的度，所有一般用在树的度较小的树中，如二叉树。
  • 数据结构
    java

    public class Node{
     Object data; //数据
     Node child1; //第 1 个孩子
     Node child2; //第 2 个孩子
     Node ...
     Node childn; //第 n 个孩子,直到等于树的度
    }

  • 图示
    

孩子链表表示法

• 特点
  结点用数组储存
  某结点的孩子结点索引用链表存储
• 优点
  孩子索引链表中可以表示兄弟的位置关系
• 缺点
  1. 查找双亲困难（要遍历每个结点以及每个结点的孩子链表找到哪个链表包含要找的结点）
  2. 随机删除和添加结点复杂
• 数据结构
  java

  //链式
  public class 孩子结点索引{
   int index; //索引
   孩子结点索引 next; //指向下一个孩子
  }
  
  //用数组存储
  public class 结点{
   Object data; //数据
   孩子结点索引 first; //指向第一个孩子（孩子链表的头结点）
  }

• 图示

双亲+孩子链表表示法

• 特点
  将双亲表示法和孩子链表表示法结合

• 优点
  弥补了双亲表示法兄弟结点的位置关系不明确问题 和 孩子链表表示法查找双亲结点困难问题

• 缺点

  1. 占用空间也跟着变大
  2. 随机删除和添加结点复杂

• 数据结构

  java

  //链式
  public class 孩子结点索引{
   int index; //索引
   孩子结点索引 next; //指向下一个孩子
  }
  
  //用数组存储
  public class 结点{
   Object data; //数据
   int parent; //父结点下标
   孩子结点索引 first; //指向第一个孩子（孩子链表的头结点）
  }

• 图示

  

  

孩子兄弟表示法（二叉链表表示法）

• 特点
  采用链表实现

• 优点
  找兄弟结点和孩子结点容易

• 缺点

  1. 找父结点困难（从根结点遍历，看哪个结点的孩子结点等于要找的结点）
  2. 找左兄弟节点困难（从根结点遍历，看哪个结点的右结点等于要找的结点）

• 数据结构

  java

  public class 结点{
   Object data; //数据
   结点 firstChild; //指向第一个孩子结点
   结点 rightBrother; //指向右兄弟结点
  }

• 图示