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

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

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

举报该问题

推荐答案 2019-05-10

这是我前几天写的，看了下应该可以满足要求，由于测试还不够，不知道有没有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);
}

温馨提示：答案为网友推荐，仅供参考

当前网址：http://11.wendadaohang.com/zd/8vF72q8M.html

其他回答

第1个回答 2007-09-27

这是我前几天写的，看了下应该可以满足要求，由于测试还不够，不知道有没有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);
}本回答被提问者采纳

相似回答

跪求二叉树排序的 源程序(一定要C语言的)!!!答：depth(p,i,&j);//求二叉树深度 for(;j>0;j--)endpre(p,p);//这个循环次数为二叉树深度减一 headpre(p);system("pause");return 0;}

大家正在搜

二叉排序树调整为平衡二叉排序树平衡二叉树和平衡二叉排序树平衡二叉树一定是二叉排序树平衡二叉树和二叉排序树的关系二叉排序树是平衡二叉树时二叉排序树转换二叉平衡树在一棵平衡二叉排序树中二叉排序树的平衡旋转平衡二叉排序树调整