第6章数据结构树和二叉树

所组成的非空树，左子树和右子树又同样都是二叉树 ?特征：?每个结点最多只有两棵子树?子树有左右之分，其次序不能任意颠倒，只有一棵子树时也必须分清左右子树。РР14РР二叉树的抽象数据类型РADT BinTree{? 数据对象D：D是具有相同特性的数据元素的集合。 ? 数据关系R：若D=，则R=，称二叉树为空二叉树；? 若D，则R={H}，H是如下二元关系：? （1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；? （2）若D-{root},则存在D-{root}={D1,Dr},且?D1Dr；? （3）若D1，则D1中存在唯一的元素x1,<root, x1>H,且存在D1上的关系H1H；若Dr,则Dr中存在唯一的元素xr, <root, xr>H, 且存在Dr上的关系HrH；H={<root, x1>,<root, xr>, H1, Hr};? （4）（D1，{H1}）是一棵符合本定义的二叉树，称为根的左子树，（Dr，{Hr}）是一棵符合本定义的二叉树，称为根的右子树。?基本操作如下：РР15РР二叉树的抽象数据类型РBiTreeInit (BT);?BiTreeRoot(BT);?BiTreeParent(BT,x);?BiTreeLeftChild (BT,x);?BiTreeRightChild (BT,x);?BiTreeBuild(BT,LBT,RBT);?BiTreeInsertLeft(BT,y,x);?BiTreeInsertRight(BT,y,x);?BiTreeDeleteLeft(BT,x);?BiTreeDeleteRight(BT,x);?BiTreeClear(BT);?BiTraverse(BT);?}ADT BinTreeРР16