二叉树的接口定义
这组接口提供了对二叉树的基本操作和一些简单属性,比如二叉树的初始化、销毁、叶子结点(注意是叶子结点)的插入、删除、合并,属性包括树的结点个数、树的根结点、树的分支结束标识、叶子结点的标识、结点中的数据、结点的左子结点、右子结点。
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所标识的结点的右子结点。