结点的层次:规定根结点在第一层,其子女 结点的层次等于它的层次加一。以下类推。 结点的深度:结点的深度即为结点的层次; 离根最远结点的层次即为树的深度。 A l层 B)(C①D 2层 depth height E)(F)(G)(H 3层 K( M 4层
• 结点的层次：规定根结点在第一层，其子女 结点的层次等于它的层次加一。以下类推。 • 结点的深度：结点的深度即为结点的层次； 离根最远结点的层次即为树的深度。 1层 2层 4层 3层 depth = 4 D A B C E F G H I J K L M height = 4 6
结点的高度:规定叶结点的高度为1,其双亲结 点的高度等于它的高度加一 树的高度:等于根结点的高度,即根结点所有 子女高度的最大值加一。 有序树:树中结点的各棵子树T1,T2,,是有次 序的,即为有序树。 无序树:树中结点的各棵子树之间的次序是不 重要的,可以互相交换位置。 森林:森林是m(m0)棵树的集合
• 结点的高度：规定叶结点的高度为1，其双亲结 点的高度等于它的高度加一。 • 树的高度：等于根结点的高度，即根结点所有 子女高度的最大值加一。 • 有序树：树中结点的各棵子树 T1 , T2 , …是有次 序的，即为有序树。 • 无序树：树中结点的各棵子树之间的次序是不 重要的，可以互相交换位置。 • 森林：森林是m（m≥0）棵树的集合。 7
树的抽象数据类型 template <class t> class tree i /对象:树是由mC>0)个结点组成的有限集合。在 类界面中的 position是树中结点的地址。在顺序 /存储方式下是下标型,在链表存储方式下是指针 /型。T是树结点中存放数据的类型,要求所有结 ∥点的数据类型都是一致的。 ublic: p Tree o; cTree o
树的抽象数据类型 template <class T> class Tree { //对象: 树是由n (≥0) 个结点组成的有限集合。在 //类界面中的 position 是树中结点的地址。在顺序 //存储方式下是下标型, 在链表存储方式下是指针 //型。T 是树结点中存放数据的类型, 要求所有结 //点的数据类型都是一致的。 public: Tree (); ~Tree (); 8
Buildroot(const T& value); ∥/建立树的根结点 position FirstChild(position p) ∥)回p第一个子女地址,天子女返回0 position NextSib ing(position p ∥回p下一兄弟地址,若天下一兄弟返回0 position Parent(position p); 回p双亲结点地址,若p为根返回0 T GetData(position p) ∥回结点卩中存放的值 bool InsertChild(position p, t& value); 在结点p下插入值为 value的新子女,若插 /失败。函数返回fale,否则返回true
BuildRoot (const T& value); //建立树的根结点 position FirstChild(position p); //返回 p 第一个子女地址, 无子女返回 0 position NextSibling(position p); //返回 p 下一兄弟地址, 若无下一兄弟返回 0 position Parent(position p); //返回 p 双亲结点地址, 若 p 为根返回 0 T GetData(position p); //返回结点 p 中存放的值 bool InsertChild(position p, T& value); //在结点 p 下插入值为 value 的新子女, 若插 //入失败, 函数返回false, 否则返回true 9
bool Delete Child(position p, int i ∥除结点p的第i个子女及其全部子孙结 ∥点,若删除失败,则返回 false,否则返回true void Delete Sub Tree(position t) /删除以t为根结点的子树 bool Isempty o /判树空否若空则返回true.否则返回 false void Traversal (void (visit)(position p)) ∥遍历以p为根的子树
bool DeleteChild (position p, int i); //删除结点 p 的第 i 个子女及其全部子孙结 //点, 若删除失败, 则返回false, 否则返回true void DeleteSubTree (position t); //删除以 t 为根结点的子树 bool IsEmpty (); //判树空否, 若空则返回true, 否则返回false void Traversal (void (*visit)(position p)); //遍历以 p 为根的子树 }; 10