二叉树的抽象数据类型定义

ADT BinaryTree{

    数据对象D：D是具有相同特性的数据元素的集合

    数据关系R：若 D = ∅，则 R = ∅

                         若 D ≠ ∅，则 R = {H}；H是如下二元关系：

                                                              ① root 唯一 //关于根的说明

                                                              ② Dj∩Dk = ∅ //关于子树不相交的说明

                                                              ③ 根和它左孩子和右孩子的说明

                                                              ④ 关于左子树和右子树的说明

    基本操作P：

                      CreateBiTree(&T,definition) //创建二叉树，创建的二叉树通过 T 返回

                                            初始条件：definition 给出二叉树 T 的定义

                                            操作结果：按 definition 构造二叉树 T

                      PreOrderTraverse(T) //前序遍历

                                            初始条件：二叉树 T 存在

                                            操作结果：先序遍历 T ，对每个结点访问一次

                      InOrderTraverse(T) //中序遍历

                                            初始条件：二叉树 T 存在

                                            操作结果：中序遍历 T ，对每个结点访问一次

                      PostOrderTraverse(T) //后序遍历

                                            初始条件：二叉树 T 存在

                                            操作结果：后序遍历 T ，对每个结点访问一次

}ADT BinaryTree