# 二叉树的实现与分析(源码及解析)

2018/01/10 06:36

#### 示例1：二叉树抽象数据类型的头文件

/*bitree.h*/
#ifndef BITREE_H
#define BITREE_H
#include <stdlib.h>

/*定义二叉树结点结构体*/
typedef struct BiTreeNode_
{
void *data;
struct BiTreeNode_ *left;
struct BiTreeNode_ *right;
}BiTreeNode;

/*定义二叉树结构体*/
typedef struct BiTree_
{
int size;
int (*compare)(const void *key1,const void *key2);
void (*destroy)(void *data);
BiTreeNode *root;
}BiTree;

/*公共接口部分*/
void bitree_init(BiTree *tree,void (*destroy)(void *data));
void bitree_destroy(BiTree *tree);
int bitree_ins_left(BiTree *tree,BiTreeNode *node,const void *data);
int bitree_ins_right(BiTree *tree,BiTreeNode *node,const void *data);
void bitree_rem_left(BiTree *tree,BiTreeNode *node);
void bitree_rem_right(BiTree *tree,BiTreeNode *node);
int bitree_merge(BiTree *merge,BiTree *left,BiTree *right,const void *data);

#define bitree_size(tree)((tree)->size)
#define bitree_root(tree)((tree)->root)
#define bitree_is_eob(node)((node) == NULL)
#define bitree_is_leaf(node)((node)->left == NULL && (node)->right == NULL)
#define bitree_data(node)((node)->data)
#define bitree_left(node)((node)->left)
#define bitree_right(node)((node)->right)

#endif // BITREE_H

#### 示例2：二叉树抽象数据类型的实现

#include <stdlib.h>
#include <string.h>
#include "bitree.h"

/*bitree_init  初始化二叉树*/
void bitree_init(BiTree *tree,void (*destroy)(void *data))
{
tree->size = 0;
tree->destroy = destroy;
tree->root = NULL;

return ;
}

/*bitree_destroy  销毁二叉树*/
void bitree_destroy(BiTree *tree)
{
/*移除树中的所有结点*/
bitree_rem_left(tree,NULL);
/*不再允许其他操作，清除树结构*/
memset(tree,0,sizeof(BiTree));
return ;
}

/*bitree_ins_left  插入左子结点*/
int bitree_ins_left(BiTree *tree,BiTreeNode *node,const void *data)
{
BiTreeNode *new_node,**position;

/*决定在何处插入结点*/
if(node == NULL)
{
/*允许只在空树中插入根结点*/
if(bitree_size(tree)>0)
return -1;

position = &tree->root;
}
else
{
/*通常只允许在一个分支的末端进行插入*/
if(bitree_left(node) != NULL)
return -1;

position = &node->left;
}
/*为结点分配空间*/
if((new_node = (BiTreeNode*)malloc(sizeof(BiTreeNode)))==NULL)
return -1;

new_node->data = (void*)data;
new_node->left = NULL;
new_node->right = NULL;
*position = new_node;

tree->size++;

return 0;
}/*bitree_ins_right  插入右结点*/int bitree_ins_right(BiTree *tree,BiTreeNode *node,void *data){    BiTreeNode *new_node, **position;    /*决定将结点插入哪一位置*/    if(node == NULL)    {        /*仅允许在空树中插入根结点*/        if(bitree_size(tree)>0)        return -1;            position = &tree->root;    }    else    {     /*通常只允许在一个分支的末端进入插入*/        if(bitree_right(node)!=NULL)        return -1;        position = &node->right;    }        /*为结点分配空间*/    if((new_node = (BiTreeNode*)malloc(sizeof(BiTreeNode)))==NULL)        return -1;    /*将结点插入树中*/    new_node->data = (void*)data;    new_node->left = NULL;     new_node->right = NULL;    *position = new_node;    tree->size++;    return 0;}/*bitree_rem_left  移除以指定结点的左子结点为根的子树*/void bitree_rem_left(BiTree *tree,BiTreeNode *node){    BiTreeNode **position;        /*从一颗空树中移除节点是不被允许的*/    if(bitree_size == 0)        return;        /*决定从何处移除分支*/    if(node == NULL)        position = &tree->root;    else         position = &node->left;    /*按后序遍历的顺序移除分支*/    if(*position != NULL)    {        bitree_rem_left(tree,*position);        bitree_rem_right(tree,*position);        if(tree->destroy != NULL)        {             /*调用自定义的析构函数释放动态空间*/            tree->destroy((*position)->data);        }        free(*position);        *position = NULL;                tree->size--;    }    return;}
/*bitree_rem_left  移除以指定结点的右子结点为根的子树*/void betree_rem_right(BiTree *tree,BiTreeNode *node){    BiTreeNode **position;    if(bitree_size(tree) == 0)        return ;    if(node == NULL)        position = &tree->root;    else         position = &node->right;    if(position != NULL)    {        bitree_rem_left(tree,*position);        bitree_rem_right(tree,*position);        if(tree->destroy != NULL)        {            tree->destroy((*position)->data);        }          free(*position);        *position = NULL;        tree->size--;    }    return ;}/*bitree_merge  将两颗二叉树合并为单颗二叉树*/int bitree_merge(BiTree *merge, BiTree *left, BiTree *right, const void *data){    /*初始化合并树*/    bitree_init(merge,left->destroy);    /*将传入的data插入到新树的根结点中*/    if(bitree_ins_left(merge,NULL,data) != 0)    {        bitree_destroy(merge);        return -1;    }    /*合并后的树的左右子结点，分别设置为left和right的根结点*/    bitree_root(merge)->left = bitree_root(left);    bitree_root(merge)->right = bitree_root(right);    /*调整合并后的树的结点的数量为本身的数量与左右两颗树的结点数量之和*/    merge->size = merge->size + bitree->size(left) + bitree_size(right);        /*解除原来树中的结点关系，并分别将size设置为0*/    left->root = NULL;    left->size = 0;    right->root = NULL;    right->size = 0;    return 0;}    

0
0 收藏

0 评论
0 收藏
0