19-二叉树ADT

17.7.1　二叉树ADT

和前面一样，先从概括地定义二叉树开始。该定义假设树不包含相同的项。许多操作与链表相同，区别在于数据层次的安排。下面建立一个非正式的树定义：

类型名： 二叉查找树

类型属性： 二叉树要么是空节点的集合（空树），要么是有一个根节点的节点集合

每个节点都有两个子树，叫作左子树和右子树

每个子树本身也是一个二叉树，也有可能是空树

二叉查找树是一个有序的二叉树，每个节点包含一个项，

左子树的所有项都在根节点项的前面，右子树的所有项都在根节点项的后面

类型操作： 初始化树为空

确定树是否为空

确定树是否已满

确定树中的项数

在树中添加一个项

在树中删除一个项

在树中查找一个项

在树中访问一个项

清空树