数据与结构

树的抽象数据类型:

 ADT  树(tree)
    树是由一个根结点和若干课子树构成。树中结点具有相同数据类型及层次关系。
Operation
    root:返回根结点。
    nodes:树的结点数
    depth:树的深度
    ...
EndADT

树的存储结构:

  • 双亲表示法
  • 孩子表示法
  • 孩子兄弟表示法

双亲表示法

在每个结点中,拥有指向双亲结点的指针(可以扩展子结点或者兄弟结点)。

孩子表示法

每个结点有多个指针域,其中每个指针指向一棵子树的根结点,叫多重链表表示法;把每个结点排列起来,以单链表做存储结构,叫孩子表示法。

孩子兄弟表示法

一个结点设置两个指针,分别指向该结点的第一个子结点和该结点的右兄弟。