设为首页 加入收藏

TOP

二叉树的接口定义
2018-01-17 13:05:25 】 浏览:115
Tags:接口 定义

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


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


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


】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇Java静态代码块使用 下一篇二叉树的接口定义

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目