树
树的抽象数据类型:
ADT 树(tree)
树是由一个根结点和若干课子树构成。树中结点具有相同数据类型及层次关系。
Operation
root:返回根结点。
nodes:树的结点数
depth:树的深度
...
EndADT
树的存储结构:
- 双亲表示法
- 孩子表示法
- 孩子兄弟表示法
双亲表示法
在每个结点中,拥有指向双亲结点的指针(可以扩展子结点或者兄弟结点)。
孩子表示法
每个结点有多个指针域,其中每个指针指向一棵子树的根结点,叫多重链表表示法;把每个结点排列起来,以单链表做存储结构,叫孩子表示法。
孩子兄弟表示法
一个结点设置两个指针,分别指向该结点的第一个子结点和该结点的右兄弟。