二叉树ADT描述 ADT BinaryTreef 数据对象D:D是同类型数据元素的集合。 数据关系R:若D=O,则称BinaryTree:为空二叉树； 否则R是满足下列条件的二元关系： (1)在D中存在唯一的称为根的元素root,它在R下无直接前驱； (2)若D-{root}=☑，则R=O;否则存在D-{root}={DI,Dr}, 且DInDr=-O; (3)若Dl≠O,则DI中存在唯一的元素xl,<root,x>∈R,且存在 DI上的关系RlcR;若Dr≠☑，则Dr中存在唯一的元素xr, <rOot,Xr>∈R,且存在Dr上的关系RrCR;R={<root,X>, <root,xr>,Rl,Rr}i (4)D1,)是一棵符合本定义的二叉树，称为根的左子树； (Dr,R)是一棵符合本定义的二叉树，称为根的右子树。 ypb@ustc.edu.cn 9 中国科学技术大学ypb@ustc.edu.cn 9 中国科学技术大学 二叉树ADT描述 ADT BinaryTree{ 数据对象D：D是同类型数据元素的集合。 数据关系R：若D=，则称BinaryTree为空二叉树； 否则R是满足下列条件的二元关系： (1)在D中存在唯一的称为根的元素root，它在R下无直接前驱； (2)若D-{root}=，则R=；否则存在D-{root}={Dl，Dr}， 且Dl∩Dr=； (3)若Dl≠，则Dl中存在唯一的元素xl，<root,xl>∈R，且存在 Dl上的关系RlR；若Dr≠，则Dr中存在唯一的元素xr， <root,xr>∈R，且存在Dr上的关系RrR；R={<root,xl>， <root,xr>，Rl，Rr}； (4)(Dl，Rl)是一棵符合本定义的二叉树，称为根的左子树； (Dr，Rr)是一棵符合本定义的二叉树，称为根的右子树