你好,游客 登录 注册 搜索
背景:
阅读新闻

二叉树的接口定义

[日期:2018-01-11] 来源:Linux社区  作者:idreamo [字体: ]

二叉树的接口定义

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

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.chineselinuxuniversity.net/Linux/2018-01/150239.htm

linux
相关资讯       二叉树 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款