6.3　树的抽象数据类型

相对于线性结构，树的操作就完全不同了，这里我们给出一些基本和常用操作。

  1. ADT 树(tree)
  2. Data
  3.     树是由一个根结点和若干棵子树构成。树中结点具有相同数据类型及层次关系。
  4. Operation
  5.     InitTree(*T):               构造空树T。
  6.     DestroyTree(*T):            销毁树T。
  7.     CreateTree(*T, definition): 按definition中给出树的定义来构造树。
  8.     ClearTree(*T):              若树T存在，则将树T清为空树。
  9.     TreeEmpty(T):               若T为空树，返回true，否则返回false。
  10.     TreeDepth(T):               返回T的深度。
  11.     Root(T):                    返回T的根结点。
  12.     Value(T, cur_e):            cur_e是树T中一个结点，返回此结点的值。
  13.     Assign(T, cur_e, value):    给树T的结点cur_e赋值为value。
  14.     Parent(T, cur_e):           若cur_e是树T的非根结点，则返回它的双亲，否则返回空。
  15.     LeftChild(T, cur_e):        若cur_e是树T的非叶结点，则返回它的最左孩子，否则返回空。
  16.     RightSibling(T, cur_e):     若cur_e有右兄弟，则返回它的右兄弟，否则返回空。
  17.     InsertChild(*T, *p, i, c):  其中p指向树T的某个结点，i为所指结点p的度加上1，
  18.                                 非空树c与T不相交，操作结果为插入c为树T中p指结点的第i棵子树。
  19.     DeleteChild(*T, *p, i):     其中p指向树T的某个结点，i为所指结点p的度，
  20.                                 操作结果为删除T中p所指结点的第i棵子树。
  21. endADT