二叉查找树的一级ADT接口、实现和使用

接口文件：

[code]

/*-----------------------------------------------------------
        二叉查找树的ADT接口
        作者： QingXiaoming, 12-03, 2007([url]http://www.cublog.com/augustusqing/[/url])
        您可以自由的传播，修改这份代码，转载处请注明原作者
-------------------------------------------------------------*/

#ifndef BIN_SORT_TREE_ADT_H
#define BIN_SORT_TREE_ADT_H

#include "Item.h"

typedef struct BinTreeNode *bstlink;
typedef struct BinTree *BST;

BST initBinTree(void);
int emptyBinTree(BST);
bstlink searchBinTree(BST, Item);
bstlink maxBinTree(BST);
bstlink minBinTree(BST);
bstlink sucBinTree(BST, bstlink);
bstlink preBinTree(BST, bstlink);
void insertBinTree(BST, Item);
bstlink deleteBinTree(BST, Item);
void traverseBinTree(BST);
void destroyBinTree(BST);
Item showBinTreeNode(bstlink);
#endif

[/code]

 

实现文件:

[code]

/*-----------------------------------------------------------
        二叉查找树的ADT实现
        作者： QingXiaoming, 12-03, 2007([url]http://www.cublog.com/augustusqing/[/url])
        您可以自由的传播，修改这份代码，转载处请注明原作者
-------------------------------------------------------------*/

#include <stdlib.h>
#include "include/Bin_Sort_Tree_ADT.h"

struct BinTreeNode {
       Item item;
       bstlink parent;
       bstlink lchild;
       bstlink rchild;
       };
struct BinTree {
       bstlink root;
       };
static bstlink NEW(Item item, bstlink parent)
{
    bstlink x = malloc(sizeof(*x));
    x->item = item;
    x->parent = parent;
    x->lchild = x->rchild = NULL;
    return x;
}

BST initBinTree(void)
{
    BST bst = malloc(sizeof(*bst));
    bst->root = NULL;
    return bst;
}

int emptyBinTree(BST bst)
{
    return bst->root == NULL;
}

bstlink searchBinTree(BST bst, Item item)
{
       bstlink x = bst->root;
       while (x != NULL && x->item != item)
       {
           x = (item < x->item) ? x->lchild : x->rchild;
       }
       return x;
}

bstlink maxBinTree(BST bst)
{
      bstlink x = bst->root;
      while (x != NULL && x->rchild != NULL)
      {
            x = x->rchild;
      }
      return x;
}

bstlink minBinTree(BST bst)
{
     bstlink x = bst->root;
      while (x  && x->lchild)
      {
            x = x->lchild;
      }
      return x;
}

bstlink sucBinTree(BST bst, bstlink link)
{
     bstlink x ;
     if (link->rchild != NULL)
     {
         x = link->rchild;
         while (x && x->lchild) x = x->lchild;
         return x;
     }
     x = link->parent;
     while (x && link == x->rchild)
     {
         link = x;
         x = x->parent;
     }
     return x;
}

bstlink preBinTree(BST bst, bstlink link)
{
     bstlink x;
     if (link->lchild != NULL)
     {
         x = link->lchild;
         while (x && x->rchild) x = x->rchild;
         return x;
     }
     x = link->parent;
     while (x && link == x->lchild)
     {
         link = x;
         x = x->parent;
     }
     return x;
}

void insertBinTree(BST bst, Item item)
{
     bstlink x, p;
     if (!bst->root)
     {
         bst->root = NEW(item, bst->root);
         return ;
     }
     x = bst->root;
     while (x)
     {
         p = x;
         x = (item <= x->item) ? x->lchild : x->rchild;
     }
     if (item <= p->item)
     {
         p->lchild = NEW(item, p);
     }
     else
     {
         p->rchild = NEW(item, p);
     }
}

bstlink deleteBinTree(BST bst, Item item)
{
    bstlink x, y, z = searchBinTree(bst, item);
    if (!z)
    {
        return z;
    }
    if ( !z->lchild || !z->rchild)
    {
         y = z;
    }
    else
    {
        y = sucBinTree(bst, z);
    }
    x = y->lchild ? y->lchild : y->rchild;
    if (x)
    {
        x->parent = y->parent;
    }
    if (!y->parent)
    {
        bst->root = x;
    }
    else
    {
        if ( y == y->parent->lchild)
        {
             y->parent->lchild = x;
        }
        else
        {
            y->parent->rchild = x;
        }
    }
    if (y != z)
    {
        z->item = y->item;
    }
    return y;
}

void traverseBinTree(BST bst)
{
     bstlink x = minBinTree(bst);
     while (x)
     {
         printf("%d \n", x->item);
         x = sucBinTree(bst, x);
     }
}

void destroyBinTree(BST bst)
{
     bstlink y, x = minBinTree(bst);
     while (x)
     {
           y = sucBinTree(bst, x);
           free(x);
     }
}

Item showBinTreeNode(bstlink link)
{
     return link->item;
}

[/code]

 

客户程序:

[code]

/*-----------------------------------------------------------
        二叉查找树的ADT客户程序
        作者： QingXiaoming, 12-03, 2007([url]http://www.cublog.com/augustusqing/[/url])
        您可以自由的传播，修改这份代码，转载处请注明原作者
-------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "include/Bin_Sort_Tree_ADT.h"
#include "include/Stack_ADT.h"

int main(int argc, char *argv[])
{
    int i, N = 10;
    Item t;
    bstlink x;
    BST bst = initBinTree();
    S ps = initStack(N);
    srand((unsigned)clock());
    for (i = 0; i < N; i++)
    {
        t = rand() + i;
        printf("%d \n", t);
        pushStack(ps, t);
        insertBinTree(bst, t);
    }
    printf("\n");
    traverseBinTree(bst);
    printf("\n");
    for (i = 0; i < N; i++)
    {
        t = popStack(ps);
        x = deleteBinTree(bst, t);
        printf("%d \n", showBinTreeNode(x));
    }
    system("pause");
    return 0;
}

[/code]