操作结果:将树T清为空树。 InsertChild(&T,&p, i, c) 初始条件:树T存在,p指向T中某个结点,1≤长p所指结点的度+1,非空树c与 T不相交 操作结果:插入c为T中p所指结点的第i棵子树。 Delete Child (&T,&p, i); 初始条件:树T存在,p指向T中某个结点,1≤i≤p指结点的度。 操作结果:删除T中p所指结点的第i棵子树 3 ADT Tree 树和线性结构对照: 第二节二叉树类型 ·定义:二叉树是另一种树形结构。它与树形结构的区别是: (1)每个结点最多有两棵子树; (2)子树有左右之分 叉树也可以用递归的形式定义。即:二叉树是n(n≥0)个结点的有限集合。 当n=0时,称为空二叉树;当n>时,有且仅有一个结点为二叉树的根,其余结点被分成两个 互不相交的子集,一个作为左子集,另一个作为右子集,每个子集又是一个二叉树。 621二叉树的类型定义 ADT Binary Tree i 数据对象:D是具有相同特性的数据元素的集合 数据关系: 若D为空集,称 Binary Tree为空二叉树; 否则关系R={H} (1)在D中存在唯一的称为根的数据元素root,它在关系H下无前驱; (2)D中其余元素必可分为两个互不相交的子集L和R,每一个子集都是一棵符合本 定义的二叉树,并分别为root的左子树和右子树。如果左子树L不空,则必存在一个根结点, 它是root的"左后继"<root,>∈H),如果右子树R不空,则必存在一个根结点为root的 右后继"(<root,>∈H) °基本操作P 结构初始化} Init BiTree(&I 操作结果:构造空二叉树T。 Create BiTree(&T, definition); 初始条件: definition给出二叉树T的定义 操作结果:按 definition构造二叉树T。 销毁结构} Destroy BiTree(&T); 初始条件:二叉树T存在。操作结果：将树 T 清为空树。 InsertChild(&T, &p, i, c); 初始条件：树 T 存在，p 指向 T 中某个结点，1≤i≤p 所指结点的度＋1，非空树 c 与 T 不相交。 操作结果：插入 c 为 T 中 p 所指结点的第 i 棵子树。 DeleteChild(&T, &p, i); 初始条件：树 T 存在，p 指向 T 中某个结点，1≤i≤p 指结点的度。 操作结果：删除 T 中 p 所指结点的第 i 棵子树。 } ADT Tree 树和线性结构对照： 第二节 二叉树类型 •定义：二叉树是另一种树形结构。它与树形结构的区别是： • （1）每个结点最多有两棵子树； • （2）子树有左右之分。 • 二叉树也可以用递归的形式定义。即：二叉树是 n（n≥0）个结点的有限集合。 当 n=0 时，称为空二叉树；当 n>0 时，有且仅有一个结点为二叉树的根，其余结点被分成两个 互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。 6.2.1 二叉树的类型定义 ADT BinaryTree { 数据对象：D 是具有相同特性的数据元素的集合。 数据关系： 若 D 为空集，称 BinaryTree 为空二叉树； 否则 关系 R={H}： (1) 在 D 中存在唯一的称为根的数据元素 root，它在关系 H 下无前驱； (2) D 中其余元素必可分为两个互不相交的子集 L 和 R，每一个子集都是一棵符合本 定义的二叉树，并分别为 root 的左子树和右子树。如果左子树 L 不空，则必存在一个根结点 ， 它是 root 的"左后继"(<root, >∈H)，如果右子树 R 不空，则必存在一个根结点 为 root 的 "右后继"(<root, >∈H)。 •基本操作 P： {结构初始化} InitBiTree(&T); 操作结果：构造空二叉树 T。 CreateBiTree(&T, definition); 初始条件：definition 给出二叉树 T 的定义。 操作结果：按 definition 构造二叉树 T。 {销毁结构} DestroyBiTree(&T); 初始条件：二叉树 T 存在