小陈不会认输
2021-11-26 01:04
采纳率: 100%
浏览 18

二叉排序树及将树平衡的问题

我的代码运行结果无法输出树的高度

#include<stdio.h>
#include<stdlib.h>
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
}Node;
typedef struct  {
    Node* root;
}Tree;
void addnode(Tree* tree, int data) {//添加
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    if (tree->root == NULL) {
        tree->root = node;
    }
    else {
        Node* temp = (Node*)malloc(sizeof(Node));//存储当前根节点内容
        temp = tree->root;
        while (temp != NULL) {
            if (temp->data > data) {
                if (temp->left == NULL) {
                    temp->left = node;
                    return;
                }
                else {
                    temp = temp->left;

                }
            }
            else {
                if (temp->data < data) {
                    if (temp->right == NULL) {
                        temp->right = node;
                        return;
                    }
                    else {
                        temp = temp->right;
                    }
                }
            }
        }
    }
}

Node* findmin(Node* node) {//找到最小值
    if (node == NULL)
        return NULL;
    while (node->left != NULL)
        node = node->left;
    return node;
}
Node *denode(Node* node, int data) {//删除
    if (node ==NULL) {
        return node;
    }
    else {
        if (node->data > data) {
            node->left = denode(node->left, data);
        }
        else if (node->data < data) {
            node->right = denode(node->right, data);
        }
        else {
            if (node->left == NULL && node->right == NULL) {
                node = NULL;
            }
            else if (node->left != NULL && node->right == NULL) {

                node = node->left;

            }
            else if (node->right != NULL && node->left == NULL) {
                node = node->right;
            }
            else {
                Node* pre = findmin(node->right);
                node = denode(node,pre->data);
                node->data = pre->data;
            }
        }
    }
    return node;
}
int height(Node* node) {//求树的高度
    if (node == NULL) {
        return -1;
    }
    else if (node->left == NULL && node->right == NULL) {
        return 0;
    }
    else {
        int left = height(node->left);
        int right = height(node->right);
        return left>right?(left + 1):(right + 1);
    }
}
Node* leftrotation(Node* node) {//左旋
    Node* temp = node->right;
    node->right = temp->left;
    temp->left = node;
    return temp;
}
Node* rightrotation(Node* node) {//右旋
    Node* temp = node->left;
    node->left = temp->right;
    temp->right = node;
    return temp;
}
Node* balance(Node* current) {//平衡
    if (current == NULL) {
        return current;
    }
    if (height(current->left) - height(current->right) > 1) {
        if (height(current->left->left) >= height(current->left->right)){
            return rightrotation(current);
        }
        else {
            return rightrotation(leftrotation(current->left));
        }
    }
    if (height(current->right) - height(current->left) > 1) {
        if (height(current->right->right) >= height(current->right->left)) {
            return leftrotation(current);
        }
        else {
            return leftrotation(rightrotation(current->right));
        }
    }
    return current;
}

void firorder(Node* node) {//先序遍历
    if (node != NULL) {
        printf("%d\n", node->data);
        firorder(node->left);
        firorder(node->right);
    }
}
int main() {

    int arry[7] = { 6,3,8,2,5,1,7 };
    Tree tree;
    tree.root = NULL;
    printf("d%\n" + height(tree.root));
    for (int i = 0; i < 7; i++) {
    addnode(&tree, arry[i]);
    }
    firorder(tree.root);
    printf("--------\n");
    denode(tree.root, 7);
    firorder(tree.root);
    printf("--------\n");
    printf("d%\n" + height(tree.root));
    addnode(&tree, 15);
    addnode(&tree, 17);
    addnode(&tree, 19);
    printf("d%\n" + height(tree.root));
    printf("--------\n");
    balance(tree.root);
    firorder(tree.root);
    printf("--------\n");
    printf("d%\n" + height(tree.root));
}

希望能帮我解决输出显示的问题,最好可以帮我检查一下代码是否实现,能否正常运行,谢谢!

  • 好问题 提建议
  • 收藏

1条回答 默认 最新

  • 已采纳
    printf("d%\n" + height(tree.root));
    

    printf中是 %d 不是 d% , "%d\n" 后是逗号(,) 不是加号(+) ,改成

    printf("%d\n" , height(tree.root));
    

    你题目的解答代码如下:

    #include<stdio.h>
    #include<stdlib.h>
    typedef struct Node {
        int data;
        struct Node* left;
        struct Node* right;
    }Node;
    typedef struct  {
        Node* root;
    }Tree;
    void addnode(Tree* tree, int data) {//添加
        Node* node = (Node*)malloc(sizeof(Node));
        node->data = data;
        node->left = NULL;
        node->right = NULL;
        if (tree->root == NULL) {
            tree->root = node;
        }
        else {
            Node* temp = (Node*)malloc(sizeof(Node));//存储当前根节点内容
            temp = tree->root;
            while (temp != NULL) {
                if (temp->data > data) {
                    if (temp->left == NULL) {
                        temp->left = node;
                        return;
                    }
                    else {
                        temp = temp->left;
                    }
                }
                else {
                    if (temp->data < data) {
                        if (temp->right == NULL) {
                            temp->right = node;
                            return;
                        }
                        else {
                            temp = temp->right;
                        }
                    }
                }
            }
        }
    }
    Node* findmin(Node* node) {//找到最小值
        if (node == NULL)
            return NULL;
        while (node->left != NULL)
            node = node->left;
        return node;
    }
    Node *denode(Node* node, int data) {//删除
        if (node ==NULL) {
            return node;
        }
        else {
            if (node->data > data) {
                node->left = denode(node->left, data);
            }
            else if (node->data < data) {
                node->right = denode(node->right, data);
            }
            else {
                if (node->left == NULL && node->right == NULL) {
                    node = NULL;
                }
                else if (node->left != NULL && node->right == NULL) {
                    node = node->left;
                }
                else if (node->right != NULL && node->left == NULL) {
                    node = node->right;
                }
                else {
                    Node* pre = findmin(node->right);
                    node = denode(node,pre->data);
                    node->data = pre->data;
                }
            }
        }
        return node;
    }
    int height(Node* node) {//求树的高度
        if (node == NULL) {
            return -1;
        }
        else if (node->left == NULL && node->right == NULL) {
            return 0;
        }
        else {
            int left = height(node->left);
            int right = height(node->right);
            return left>right?(left + 1):(right + 1);
        }
    }
    Node* leftrotation(Node* node) {//左旋
        Node* temp = node->right;
        node->right = temp->left;
        temp->left = node;
        return temp;
    }
    Node* rightrotation(Node* node) {//右旋
        Node* temp = node->left;
        node->left = temp->right;
        temp->right = node;
        return temp;
    }
    Node* balance(Node* current) {//平衡
        if (current == NULL) {
            return current;
        }
        if (height(current->left) - height(current->right) > 1) {
            if (height(current->left->left) >= height(current->left->right)){
                return rightrotation(current);
            }
            else {
                return rightrotation(leftrotation(current->left));
            }
        }
        if (height(current->right) - height(current->left) > 1) {
            if (height(current->right->right) >= height(current->right->left)) {
                return leftrotation(current);
            }
            else {
                return leftrotation(rightrotation(current->right));
            }
        }
        return current;
    }
    void firorder(Node* node) {//先序遍历
        if (node != NULL) {
            printf("%d\n", node->data);
            firorder(node->left);
            firorder(node->right);
        }
    }
    int main() {
        int arry[7] = { 6,3,8,2,5,1,7 };
        Tree tree;
        tree.root = NULL;
        //printf("d%\n" + height(tree.root));
        printf("%d\n" , height(tree.root));
        for (int i = 0; i < 7; i++) {
        addnode(&tree, arry[i]);
        }
        firorder(tree.root);
        printf("--------\n");
        denode(tree.root, 7);
        firorder(tree.root);
        printf("--------\n");
        //printf("d%\n" + height(tree.root));
        printf("%d\n" , height(tree.root));
        addnode(&tree, 15);
        addnode(&tree, 17);
        addnode(&tree, 19);
        //printf("d%\n" + height(tree.root));
        printf("%d\n" , height(tree.root));
        printf("--------\n");
        balance(tree.root);
        firorder(tree.root);
        printf("--------\n");
        //printf("d%\n" + height(tree.root));
        printf("%d\n" , height(tree.root));
    }
    

    如有帮助,望采纳!谢谢!

    编辑记录

    已采纳该答案
    评论
    解决 1 无用
    打赏 举报

相关推荐 更多相似问题