Single

二叉树的接口定义

二叉树的接口定义

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

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)。

由于篇幅原因,这些接口的实现与分析,我们将在下一篇文章进行阐述。

:http://www.linuxidc.com/Linux/2018-01/150239.htm