c - 如何将树平衡为数组

Question

我已经制作了一个可用的二叉树。

现在我想当我按下选项＃4时，它会显示二叉树根据数组排序(这意味着中间应该是根，左子树的左边部分，然后字段的右边部分右子树)。

我已经创建了执行应该完成的操作所需的函数，但它仍然无法正常工作。

我创建了NodSize()，它控制树中有多少个节点。

我已经创建了balanceTree()，它占用了根中的所有内容。

我已经创建了ArrayInorder()，

还有Balance()，它根据数组平衡树。

我哪里做错了，该如何解决？

..

你可以在这里看到我是如何制作的:

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define MAX 100

struct tree
{
    int data;
    struct tree *left;
    struct tree *right;
};


struct tree *CreateNode(int data)
{
    struct tree *node = (struct tree*) malloc(sizeof(struct tree));
    if (node != NULL)
    {
        node->data = data;
        node->left = NULL;
        node->right = NULL;
    }
    return node;
}

struct tree *insert(struct tree *root, int data)
{
    if (root == NULL)
    {
        root = CreateNode(data);
    }
    if (root->data > data)
    {
        if (root->left == NULL)
        {
            root->left = CreateNode(data);
        }
        else
        {
            insert(root->left, data);
        }
    }
    else if (root->data < data)
    {
        if (root->right == NULL)
        {
            root->right = CreateNode(data);
        }
        else
        {
            insert(root->right, data);
        }
    }
    return root;
}


struct tree *delet(struct tree *ptr, int x)
{
    struct tree *p1, *p2;
    if (!ptr)
    {
        printf("\n NOTHING ");
        return(ptr);
    }
    else
    {
        if (ptr->data < x) 
        {
            ptr->right = delet(ptr->right, x); 

        }
        else if (ptr->data > x) 
        {
            ptr->left = delet(ptr->left, x); 
            return ptr;
        }
        else
        {
            if (ptr->data == x) 
            {
                if (ptr->left == ptr->right) 
                {
                    free(ptr);
                    return(NULL);
                }
                else if (ptr->left == NULL) 
                {
                    p1 = ptr->right;
                    free(ptr);
                    return p1;
                }
                else if (ptr->right == NULL) 
                {
                    p1 = ptr->left;
                    free(ptr);
                    return p1;
                }
                else
                {
                    p1 = ptr->right;
                    p2 = ptr->right;
                    while (p1->left != NULL)
                        p1 = p1->left;
                    p1->left = ptr->left;
                    free(ptr);
                    return p2;
                }
            }
        }
    }
    return(ptr);
}


void Findroot(struct tree *root)
{
    if (root != NULL)
    {
        printf("\nRoot is %d\n", root->data);
    }
    else
    {
        printf("\nNOTHING\n");
    }
}

void inorder(struct tree *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        printf(" %d", root->data);
        inorder(root->right);
    }
    return;
}

int NodSize(struct tree *root)
{
    if (root == NULL)
        return 0;
    else
        return (NodSize(root->left) + 1 + NodSize(root->right));
}

void DestoryTree(struct tree * root)
{
    if (root == NULL)
        return;

    DestoryTree(root->left);
    DestoryTree(root->right);


    printf("\n Destory node: %d", root->data);
    free(root);
}


struct tree *Balance(int arr[], int start, int end)
{
    if (start > end)
        return NULL;

    int mid = (start + end) / 2;
    struct tree *root = CreateNode(arr[mid]);

    root->left = Balance(arr, start, mid - 1);

    root->right = Balance(arr, mid + 1, end);
    return root;
}


int ArrayInorder(struct tree *root, int *arr, int helper)
{
    if (root != NULL)
    {
        helper = ArrayInorder(root->left, arr, helper);
        arr[helper] = root->data;
        helper++;
        helper = ArrayInorder(root->right, arr, helper);
    }
    return helper;
}


void balanceTree(struct tree *root)
{
    int *arr, size;
    size = NodSize(root);
    arr = (int*)malloc(sizeof(int)*size);
    ArrayInorder(root, arr, 0);

    //DestoryTree(root);
    root = Balance(arr, 0, size - 1);
}


void CreateBalancedTreeFromArray(struct tree *root, int *arr, int size)
{
    DestoryTree(root);
    root = Balance(arr, 0, size - 1);
}



int main(void)
{
    struct tree *root;
    int valja, item, dele;
    root = NULL;

    do
    {
        do
        {
            printf("\n1. Add a node to BINARY TREE ");
            printf("\n2. Delete a node from BINARY TREE ");
            printf("\n3. Show ROOT");
            printf("\n4. Show Balanced Tree IN (Array)");
            printf("\n5. Stang");
            printf("\nYour choice? : ");
            scanf(" %d", &valja);
            if (valja<1 || valja>5)
                printf("\n Fel - Try again");
        } while (valja<1 || valja>5);
        switch (valja)
        {
        case 1:
            system("cls");
            printf("\n Write a new element: ");
            scanf("%d", &item);
            root = insert(root, item);
            printf("\n root is %d \n", root->data);
            printf("INORDER: ");
            inorder(root);
            printf("\n");
            break;
        case 2:
            system("cls");
            printf("\n Write an element to delete: ");
            scanf(" %d", &dele);
            root = delet(root, dele);
            printf("\n");
            break;
        case 3:
            system("cls");
            Findroot(root);
            printf("\n");
            break;
        case 4:
            balanceTree(root);
            Findroot(root);
            inorder(root);
            break;
        default:
            printf("\n bye ");
        }
    } while (valja != 5);
    return(0);
}

Answer 1

问题出在这里:

void balanceTree(struct tree *root)

尽管此函数有效，但创建的新根不会返回给调用者，因为 root 已按值传递。您需要将函数更改为:

struct tree *balanceTree(struct tree *root)

并在末尾添加:

return root;

调用该函数:

root = balanceTree(root);