结点的层次：规定根结点在第一层，其子女 结点的层次等于它的层次加一。以下类推。 结点的深度：结点的深度即为结点的层次； 离根最远结点的层次即为树的深度。 1层 B ------2层 depth height --3层 =4 =4 E K --------…4层 6
• 结点的层次：规定根结点在第一层，其子女 结点的层次等于它的层次加一。以下类推。 • 结点的深度：结点的深度即为结点的层次； 离根最远结点的层次即为树的深度。 1层 2层 4层 3层 depth = 4 D A B C E F G H I J K L M height = 4 6
结点的高度：规定叶结点的高度为1，其双亲结 点的高度等于它的高度加一。 树的高度：等于根结点的高度，即根结点所有 子女高度的最大值加一。 有序树：树中结点的各棵子树T，T2,…是有次 序的，即为有序树。 无序树：树中结点的各棵子树之间的次序是不 重要的，可以互相交换位置。 .森林：森林是m(m20)棵树的集合。 7
• 结点的高度：规定叶结点的高度为1，其双亲结 点的高度等于它的高度加一。 • 树的高度：等于根结点的高度，即根结点所有 子女高度的最大值加一。 • 有序树：树中结点的各棵子树 T1 , T2 , …是有次 序的，即为有序树。 • 无序树：树中结点的各棵子树之间的次序是不 重要的，可以互相交换位置。 • 森林：森林是m（m≥0）棵树的集合。 7
树的抽象数据类型 template <class T> class Tree /对象：树是由n(20)个结点组成的有限集合。在 /类界面中的position是树中结点的地址。在顺序 /存储方式下是下标型，在链表存储方式下是指针 /型。T是树结点中存放数据的类型，要求所有结 /点的数据类型都是一致的。 public; Tree O; ~Tree O; 8
树的抽象数据类型 template <class T> class Tree { //对象: 树是由n (≥0) 个结点组成的有限集合。在 //类界面中的 position 是树中结点的地址。在顺序 //存储方式下是下标型, 在链表存储方式下是指针 //型。T 是树结点中存放数据的类型, 要求所有结 //点的数据类型都是一致的。 public: Tree (); ~Tree (); 8
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
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 DeleteChild (position p,int 1); /删除结点D的第i个子女及其全部子孙结 /点，若删除失败，则返回false,否则返回true void DeleteSubTree (position t); /删除以t为根结点的子树 bool IsEmpty O; /判树空否，若空则返回true,否则返回false void Traversal (void (*visit)(position p)); /遍历以p为根的子树 ; 0
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