二叉树的接口定义
松鼠的窝 2018-01-08
二叉树的接口定义
这组接口提供了对二叉树的基本操作和一些简单属性，比如二叉树的初始化、销毁、叶子结点（注意是叶子结点）的插入、删除、合并，属性包括树的结点个数、树的根结点、树的分支结束标识、叶子结点的标识、结点中的数据、结点的左子结点、右子结点。
bitree_init
void bitree_init(BiTree *tree, void (*destroy)(void *data));
返回值：无
描述：初始化由参数tree所指定的二叉树。该函数必须在执行其他操作之前调用。
当调用bitree_destroy时，destroy参数所指定的函数提供了一种释放动态分配数据空间的方法。例如，如果树包含采用malloc动态分配的数据，当销毁二叉树时，destroy应该设置为free用来释放数据空间。对于包含多个动态分配成员的结构化数据，destroy应该设置为一个用户自定义的析构函数，用来对每一个动态分配的成员以及结构体自身执行资源回收操作。如果二叉树包含的不需要释放的数据，destroy参数应该设置为NULL。
复杂度：O(1)
bitree_destroy
void bitree_destroy(BiTree *tree);
返回值：无
描述：销毁由参数tree所指定的二叉树。调用该函数后，任何其他的操作都不允许再执行，除非用户再次调用bitree_init。
bitree_destroy操作将二叉树中所有的结点都移除，如果destroy参数不为NULL的话，则调用destroy所指定的函数对每个移除的结点执行资源回收操作。
复杂度：O(n)。这里的n代表二叉树中的结点个数。
bitree_ins_left
int bitree_ins_left(BiTree *tree, BiTreeNode *node,const void *data);
返回值：如果插入操作成功返回0，否则返回-1。
描述：在tree所指定的二叉树中插入一个节点，使其成为node所指定结点的左子节点。
如果node已经有一个左子结点，则bitree_ins_left返回-1。如果node为NULL，则新节点作为根结点插入。插入根结点时，树必须保证为空，否则bitree_ins_left返回-1。当插入成功时，新结点包含一个指向data的指针，因此只要结点还在二叉树中，data所引用的内存就必须有效。由用户负责管理data所引用的内存空间。
复杂度：O(1)
bitree_ins_right
int bitree_ins_right(BiTree *tree, BiTreeNode *node,const void *data);
返回值：如果插入操作成功返回0，否则返回-1。
描述：该操作与bitree_ins_left类似，除了待插入的结点是作为由tree所指定的二叉树中由node所指定结点的右子节点。
复杂度：O(1)
bitree_rem_left
void bitree_rem_left(BiTree *tree, BiTreeNode *node);
返回值：无。
描述：移除由tree指定的二叉树中node的左结点为根的子树。
如果node为NULL，则移除树中的所有结点。若传递给bitree_init的参数destroy不为NULL，则移除结点时将调用destroy所指定的函数。
复杂度：O(n)，这里n代表子树中的结点个数。
bitree_rem_right
void bitree_rem_left(BiTree *tree, BiTreeNode *node);
返回值：无。
描述：移除由tree指定的二叉树中node的右结点为根的子树。
如果node为NULL，则移除树中的所有结点。若传递给bitree_init的参数destroy不为NULL，则移除结点时将调用destroy所指定的函数。
复杂度：O(n)，这里n代表子树中的结点个数。
bitree_merge
int bitree_merge(BiTree *merge, BiTree *left, BiTree *right, const void *data );
返回值：如果合并操作成功，返回0；否则返回-1。
描述：将left和right所指定的两颗二叉树合并为单颗二叉树。
合并完成后，参数data所代表的数据存储在merge的根结点中，而left和right则代表该根结点的左右子树。一旦合并完成，left和right就好像在它们之上执行了bitree_destroy操作一样。
复杂度：O(1)。
bitree_size
int bitree_size(const BiTree *tree );
返回值：返回树中的结点个数。
描述：这是一个宏，用来计算由参数tree所指定的二叉树中的结点个数。
复杂度：O(1)。
bitree_root
BiTreeNode *bitree_root(const BiTree *tree );
返回值：返回由参数tree所指定的二叉树的根结点。
描述：这是一个宏，用来返回由参数tree所指定的二叉树中的根结点。
复杂度：O(1)。
bitree_is_eob
int bitree_is_eob(const BiTreeNode *node );
返回值：如果node标识的是树的分支结束，则返回1，否则返加0。
描述：这是一个宏，用来判断由参数node所标识的结点是否为二叉树中某个分支的结束。
复杂度：O(1)。
bitree_is_leaf
int bitree_is_leaf(const BiTreeNode *node );
返回值：如果node的是叶子结点，则返回1，否则返加0。
描述：这是一个宏，用来判断由参数node所标识的结点是否为二叉树中的叶子结点。
复杂度：O(1)。
bitree_data
void *bitree_data(const BiTreeNode *node );
返回值：返回存储在结点中的数据。
描述：这是一个宏，用来判断由参数node所标识的结点中存储的数据。
复杂度：O(1)。
bitree_left
BiTreeNode *bitree_left(const BiTreeNode *node );
返回值：返回指定结点的左子结点。
描述：这是一个宏，用来返回由参数node所标识的结点的左子结点。
复杂度：O(1)。
bitree_right
BiTreeNode *bitree_right(const BiTreeNode *node );
返回值：返回指定结点的右子结点。
描述：这是一个宏，用来返回由参数node所标识的结点的右子结点。
复杂度：O(1)。
由于篇幅原因，这些接口的实现与分析，我们将在下一篇文章进行阐述。
