0

我正在尝试用 AVL 树完成一个学校项目。发生的情况是，一旦我插入根节点和其他两个节点，一切正常，如果我尝试添加的节点超过这三个节点，程序就会失败。我认为问题在于 newnode 的指针在创建后并未指向哨兵 NIL；我尝试将 newnode 的指针设置为 NIL，但没有运气。
我怎样才能解决这个问题？

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <cmath>
#include <stdio.h>
#include "graphvisualize.h"

using namespace std;
typedef struct node Tnode;

Tnode *root;
Tnode *NIL;
Tnode *newnode;

void InitializeTree(int k) {
    //initialize the list with the root node
    NIL=(Tnode *)malloc(sizeof(Tnode));  
    root=(Tnode *)malloc(sizeof(Tnode));
    //change to null later
    root->value = k;
    root->parent = NIL;
    root->right = NIL;
    root->left = NIL;  
    root->height = 1;
    NIL->right = NULL;
    NIL->left = NULL;
    NIL->parent = NULL;
}

void insert(int v) {
    Tnode *newnode=(Tnode *)malloc(sizeof(Tnode));
    newnode->value = v;
    Tnode *y = NIL;
    Tnode *x = root;
    while(x != NIL) {
        y = x;
        if(newnode->value < x->value) {
            x = x->left;  
        } else {
            x = x->right;   
        }
        newnode->parent = y;
        if(y == NIL) {
            root = newnode;
        } else if(newnode->value < y->value) {
            y->left = newnode;          
        } else {
            y->right = newnode;
        }
        cout << "insert  ";
        //Heres my problem
        //trying to set right and left pointer to NIL
        newnode->left = NIL;
        newnode->right = NIL;         
    }

    //height manager
    int h = 1;
    newnode->height = h;
    while((newnode->parent != NIL)  &&  (newnode->height >= newnode->parent->height)) {
        newnode = newnode->parent;
        newnode->height++;
    }
    cout << "height-fix  ";
}

//Display AVL Tree
void ViewTree() {
    ofstream AVLfile;
    AVLfile.open("AVLgraphfile.dot");
    AVLfile << visualize_tree(root);
    AVLfile.close();
}

int main() {
    InitializeTree(7);
    cout << "root  ";
    insert(5);
    insert(8);
    //insert(6); 
    ViewTree();
    return 0;
}
4

0 回答 0