二叉排序树。用二叉链表作存储结构。（8

发布网友发布时间：2022-03-22 15:44

共1个回答

懂视网时间：2022-03-22 20:05

二叉链表存储结构是二叉树的一种存储方式。链表中结点的两个链域分别指向该结点的第一个孩子结点和第二个孩子结点。

　　二叉链表是树的二叉链表实现方式。二叉树是逻辑结构，二叉链表是二叉树的物理实现，两者之间的关系属于概念和实现，抽象和具体的关系。二叉树的顺序存储结构由一组连续的存储单元依次从上到下，从左到右存储完全二叉树的结点元素。对于一般二叉树，应将其与完全二叉树对应，然后给每个结点从1到i编上号，依次存储在大小为i到1的数组中。

热心网友时间：2022-03-22 17:13

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

首页

文章

二叉排序树。用二叉链表作存储结构。（8