平衡二叉排序树的设计与实现C语言源程序代码(一定要C的哟!)

用二叉链表作存储结构
(1)以回车(‘\n’)为输入结束标志,输入数列L，分别生成
一棵二叉排序树T和平衡的二叉排序树BT ；
(2)对二叉排序树T作中序遍历，输出结果；
(3)输入元素x,查找二叉排序树T:若存在含x的结点,
则删除该 结点,并作中序遍历(执行操作2)；否则
输出相关信息；
(4)分别计算T、BT的查找成功的平均查找长度,输出
结果；

回答正确之后一定加100分 说到做到 俺不在乎这个积分

这是我前几天写的，看了下应该可以满足要求，由于测试还不够，不知道有没有bug。

第一点你自己改改，2、3都达到了，至于第四，不用说肯定是平衡了的二叉树相对查找效率要高一些，平衡，随机插入，打乱插入等操作都是为了防止最差情况的线性树的出现。测试的话用rand()生成随机数外加time.h里的几个函数，配合使用下就出来了。

#include <stdio.h>
#include <stdlib.h>

// binary search tree
typedef struct BST
{
    int data;
    struct BST* lhs;
    struct BST* rhs;
}BST;

// 插入一个节点
BST* BSTInsertNode(BST* root, int elem)
{
    BST* node;
    node = (BST*)malloc(sizeof(BST));
    node->data = elem;
    node->lhs = node->rhs = 0;

    if(!root)
        return node;

    while(1)
    {
        if(node->data < root->data)
        {
            if(root->lhs)
                root = root->lhs;
            else
            {
                root->lhs = node;
                return root->lhs;
            }
        }
        else  
        {
            if(root->rhs)
                root = root->rhs;
            else
            {
                root->rhs = node;
                return root->rhs;
            }
        }
    }
}

// 获得父节点
BST* BSTGetParentNode(BST* root, BST* node)
{
    if(root == node)
        return 0;

    if(root->lhs && node->data < root->lhs->data)
        return BSTGetParentNode(root->lhs, node);
    else if(root->rhs && node->data > root->rhs->data)
        return BSTGetParentNode(root->rhs, node);
    else
        return root;
}

// 删除一个节点
BST* BSTDeleteNode(BST* root, BST* node)
{
    BST* parent;
    BST** whichNode;
    BST* temp;

    if(root != node)
    {

        parent = BSTGetParentNode(root, node);
        whichNode = parent->lhs == node ? &parent->lhs : &parent->rhs;
    }
    else
        whichNode = &root;
    if(!node->lhs && !node->rhs)
        *whichNode = 0;
    else if(!((node->lhs ? 1 : 0) ^ (node->rhs ? 1 : 0)))
        *whichNode = node->lhs ? node->lhs : node->rhs;
    else
    {
        temp = node->rhs;
        while(temp->lhs)
            temp = temp->lhs;
        temp->lhs = node->lhs;
        *whichNode = node->rhs;
    }
    free(node);
    return *whichNode;
}

// 删除树
void BSTDeleteTree(BST* node)
{
    if(node)
    {
        BSTDeleteTree(node->lhs);
        BSTDeleteTree(node->rhs);
        free(node);
    }
}

// 建造树，从数组构造
BST* BSTBuildTree(int* beg, int* end)
{
    BST* root;

    if(beg >= end)
        return 0;

    root = (BST*)malloc(sizeof(BST));
    root->data = *beg++;
    root->lhs = root->rhs = 0;

    while(beg != end)
        BSTInsertNode(root, *beg++);

    return root;
}

// 查找节点
BST* BSTSearchNode(BST* root, int elem)
{
    if(root)
    {
        if(elem < root->data)
            return BSTSearchNode(root->lhs, elem);
        else if(elem > root->data)
            return BSTSearchNode(root->rhs, elem);
        else
            return root;
    }
    else
        return 0;
}

// 获得最小值
BST* BSTGetMinimumNode(BST* root)
{
    while(root->lhs)
        root = root->lhs;
    return root;
}

// 获得最大值
BST* BSTGetMaximumNode(BST* root)
{
    while(root->rhs)
        root = root->rhs;
    return root;
}

// 前序遍历
void BSTPreorderTraverse(BST* node)
{
    if(node)
    {
        printf("%d ", node->data);
        BSTPreorderTraverse(node->lhs);
        BSTPreorderTraverse(node->rhs);
    }
}

// 中序遍历
void BSTInorderTraverse(BST* node)
{
    if(node)
    {
        BSTInorderTraverse(node->lhs);
        printf("%d ", node->data);
        BSTInorderTraverse(node->rhs);
    }
}

// 后序遍历
void BSTPostorderTraverse(BST* node)
{
    if(node)
    {
        BSTPostorderTraverse(node->lhs);
        BSTPostorderTraverse(node->rhs);
        printf("%d ", node->data);
    }
}

// 获得前继值
BST* BSTGetPredecessor(BST* root, BST* node)
{
    BST* predecessor;
    BST* rightCld;

    if(node->lhs)
        return BSTGetMaximumNode(node->lhs);

    predecessor = rightCld = node;
    while((predecessor = BSTGetParentNode(root, predecessor)))
        if(predecessor->rhs == rightCld)
            return predecessor;
        else
            rightCld = predecessor;
    return 0;
}

// 获得后继值
BST* BSTGetSuccessor(BST* root, BST* node)
{
    BST* successor;
    BST* leftCld;

    if(node->rhs)
        return BSTGetMinimumNode(node->rhs);

    successor = leftCld = node;
    while((successor = BSTGetParentNode(root, successor)))
        if(successor->lhs == leftCld)
            return successor;
        else
            leftCld = successor;
    return 0;
}

// 获得树高
int BSTGetTreeHeight(BST* root)
{
    int l;
    int r;
    if(root)
    {
        l = BSTGetTreeHeight(root->lhs);
        r = BSTGetTreeHeight(root->rhs);
        return 1 + (l > r ? l : r);
    }
    else
        return -1;
}

// 计算子节点数
int BSTGetSubtreeNodeNum(BST* node)
{
    if(node)
        return BSTGetSubtreeNodeNum(node->lhs)
             + BSTGetSubtreeNodeNum(node->rhs)
             + 1;
    else
        return 0;
}

// 用于打乱数组，交换
inline void Swap(int* a, int* b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

// 用于打乱数组，qsort的比较用过程
inline int CMP(const void* lhs, const void* rhs)
{
    return *(const int*)lhs - *(const int*)rhs;
}

// 数组有序?
int IsOrdered(int* beg, int* end)
{
    int attri;
    int cmpVal;
    if(beg >= end)
        return 0;
    if(end - beg <= 2)
        return 1;

    if(*beg < *(beg + 1))
        attri = 1;
    else
        attri = 0;

    cmpVal = *beg++;
    while(++beg != end)
    {
        if(attri)
        {
            if(cmpVal > *beg)
                return 0;
        }else
        {
            if(cmpVal < *beg)
                return 0;
        }
    }
    return 1;
}

// 高层次打乱数组
void HighlyUnorderArray(int* beg, int* end)
{

    int* mid = beg + (end - beg)/2;
    int* folk;
    if(!IsOrdered(beg, end))
        qsort(beg, end - beg, sizeof(int), CMP);

    if((mid - beg) & 1)
        Swap(beg++, mid);
    folk = beg + 2;
    while(folk < mid)
    {
        Swap(beg++, folk++);
        Swap(beg++, folk++);
    }

    folk = mid + 2;
    while(folk < end)
    {
        Swap(folk, folk - 1);
        folk += 2;
    }
}

// 中序遍历结果输出到数组
void BSTInorderWalkToArray(BST* root, int** p)
{
    if(root)
    {
        BSTInorderWalkToArray(root->lhs, p);
        **p = root->data;
        (*p)++;
        BSTInorderWalkToArray(root->rhs, p);
    }
}

// 平衡树，返回平衡好的新树
BST* BSTBalanceTree(BST* root)
{
    int size = BSTGetSubtreeNodeNum(root);
    int* a = (int*)malloc(sizeof(int) * size);
    int* end = a;
    BST* balancedTree;

    BSTInorderWalkToArray(root, &end);
    HighlyUnorderArray(a, end);
    balancedTree = BSTBuildTree(a, end);
    free(a);
    return balancedTree;
}

int main()
{
    int a[] = {5,6,3,7,9,8,1,0,4,2};
    int c[] = {50,17,76,9,23,54,14,19,72,12,67};
    BST* bstTree = BSTBuildTree(a, a + sizeof(a)/sizeof(a[0]));

    BSTPreorderTraverse(bstTree);
    putchar('\n');
    BSTInorderTraverse(bstTree);
    putchar('\n');
    BSTPostorderTraverse(bstTree);
    printf("\n\n");

    BST* balancedTree = BSTBalanceTree(bstTree);
    printf("%d %d\n", BSTGetTreeHeight(bstTree), BSTGetTreeHeight(balancedTree));
    BSTDeleteTree(bstTree);
    BSTDeleteTree(balancedTree);
}

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息！