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

回顾一下，二叉树的结点由一个数据成员和两个指向其子结点的指针组成。

结构体BiTreeNode代表二叉树中的一个单独的结点，这个结构体由上述的3个成员组成。

结构体BiTree代表二叉树这种数据结构。这个结构体包含4个成员：size表示树中的结点的个数，compare成员在二叉树中暂时不会用到，而是等到其他数据类型继承二叉树时才会派上用场。destroy作为参数传递给bitree_init函数。最后，root是一个指向结点层次体系中最高点的指针，也就是指向根结点的指针。

示例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;