二叉排序树和平衡二叉树的实现与比较

二叉排序树和平衡二叉树的实现与比较

引用

CSDN

1.

https://m.blog.csdn.net/2301_80057101/article/details/143782696

二叉排序树（BST树）的任何结点均满足：“若左子树存在，根结点大于其左子树上的所有结点；若右子树存，根结点小于其右子树上的所有结点。给定一个数据序列（所有数据互不相等），可以构造二叉排序树。例如：按照下面的数据序列及其先后顺序{ 10,30,20,7,5,6,2,9,28 }可构造出如下的二叉排序树。

平衡二叉树（AVL树）是一种二叉排序树，同时要求每个结点左右子树的高度最多相差为１。对上述数据序列，同样按照数据序列及其先后顺序构造平衡二叉树，可构造出如下的平衡二叉树。

对序列中的数据元素进行查找，对于单个数据而言，平衡二叉树查找成功的比较次数不一定比二叉排序树小，但是，在每个数据元素查找的等概率下，平衡二叉树查找成功的平均查找长度要小于二叉排序树的平均查找长度。使用C或C++编写算法完成：

（1）按给定数据序列及其顺序构建二叉排序树；

（2）按给定数据序列及其顺序构建平衡二叉树；

（3）计算并输出二叉排序树中所有数据元素在查找等概率下的平均查找长度；

（4）计算并输出平衡二叉树中所有数据元素在查找等概率下的平均查找长度。

输入格式:

输入分为2行，第1行为数据元素个数，第2行为数据元素，其中个数据元素为整数。

输出格式:

输出分为2行，第1行为二叉排序树的平均查找长度，第2行为平衡二叉树的平均查找长度。平均查找长度位置输出所有数据元素查找成功的比较次数之和即可。这样输出就是一个整数了。

输入样例:

对于上面的数据序列，输入格式为：

9
10,30,20,7,5,6,2,9,28  

输出样例:

对于上面的数据序列，输出格式为:

BST-ASL:26
AVL-ASL:25  

其中“BST-ASL:”和“AVL-ASL:”为二叉排序树和平衡二叉树的平均查找长度提示，其后为各自树中所有数据查找成功的比较次数之和。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct BSTNode
{
    int value;
    struct BSTNode *left;
    struct BSTNode *right;
} BSTNode;
typedef struct AVLNode
{
    int value;
    struct AVLNode *left;
    struct AVLNode *right;
    int height;
} AVLNode;
int height(AVLNode* node)
{
    return node == NULL ? 0 : node->height;
}
AVLNode* rightRotate(AVLNode* y)
{
    AVLNode* x = y->left;
    AVLNode* T2 = x->right;
    x->right = y;
    y->left = T2;
    y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));
    x->height = 1 + (height(x->left) > height(x->right) ? height(x->left) : height(x->right));
    return x;
}
AVLNode* leftRotate(AVLNode* x)
{
    AVLNode* y = x->right;
    AVLNode* T2 = y->left;
    y->left = x;
    x->right = T2;
    x->height = 1 + (height(x->left) > height(x->right) ? height(x->left) : height(x->right));
    y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));
    return y;
}
int getBalance(AVLNode* node)
{
    return node == NULL ? 0 : height(node->left) - height(node->right);
}
BSTNode* insertBST(BSTNode* root, int value)
{
    if (root == NULL)
    {
        root = (BSTNode*)malloc(sizeof(BSTNode));
        root->value = value;
        root->left = root->right = NULL;
        return root;
    }
    else
    {
        if (value < root->value)
        {
            root->left = insertBST(root->left, value);
        }
        else
        {
            root->right = insertBST(root->right, value);
        }
        return root;
    }
}
AVLNode* insertAVL(AVLNode* node, int value)
{
    if (node == NULL)
    {
        node = (AVLNode*)malloc(sizeof(AVLNode));
        node->value = value;
        node->left = node->right = NULL;
        node->height = 1;
        return node;
    }
    else
    {
        if (value < node->value)
        {
            node->left = insertAVL(node->left, value);
        }
        else
        {
            node->right = insertAVL(node->right, value);
        }
        node->height = 1 + (height(node->left) > height(node->right) ? height(node->left) : height(node->right));
        int balance = getBalance(node);
        // 左左进行右旋转
        if (balance > 1 && value < node->left->value)
        {
            return rightRotate(node);
        }
        // 右右进行左旋转
        if (balance < -1 && value > node->right->value)
        {
            return leftRotate(node);
        }
        // 左右
        if (balance > 1 && value > node->left->value)
        {
            node->left = leftRotate(node->left); //将左子树向左旋转得到LL
            return rightRotate(node); //将得到的LL进行右旋转
        }
        // 右左
        if (balance < -1 && value < node->right->value)
        {
            node->right = rightRotate(node->right); //将右子树向右旋转得到RR
            return leftRotate(node); //将得到的RR进行左旋转
        }
        return node;
    }
}
int BST(BSTNode* root, int value, int* p)
{
    (*p)++;
    if (root == NULL)
    {
        return 0;
    }
    else
    {
        if (value < root->value)
        {
            return BST(root->left, value, p);
        }
        else if (value > root->value)
        {
            return BST(root->right, value, p);
        }
        return 1;
    }
}
int AVL(AVLNode* root, int value, int* q)
{
    (*q)++;
    if (root == NULL)
    {
        return 0;
    }
    else
    {
        if (value < root->value)
        {
            return AVL(root->left, value, q);
        }
        else if (value > root->value)
        {
            return AVL(root->right, value, q);
        }
        return 1;
    }
}
int main()
{
    int n;
    int p = 0, q = 0;
    scanf("%d", &n);
    int *a = (int*)malloc(n * sizeof(int));
    char inputs[100];// 使用字符串输入
    scanf("%s", inputs);
    int m = 0;
    char* token = strtok(inputs, ",");
    while (token != NULL && m < n)
    {
        sscanf(token, "%d", &a[m++]);
        token = strtok(NULL, ",");
    }
    BSTNode* bstRoot = NULL;
    AVLNode* avlRoot = NULL;
    for (int i = 0; i < n; i++)
    {
        bstRoot = insertBST(bstRoot, a[i]);
    }
    for (int i = 0; i < n; i++)
    {
        avlRoot = insertAVL(avlRoot, a[i]);
    }
    for (int i = 0; i < n; i++)
    {
        BST(bstRoot, a[i], &p);
    }
    for (int i = 0; i < n; i++)
    {
        AVL(avlRoot, a[i], &q);
    }
    printf("BST-ASL:%d\n", p);
    printf("AVL-ASL:%d", q);
    return 0;
}  

本文原文来自CSDN