C中的双指针AVL树

时间:2022-11-30 19:58:10

Im practicing my AVL tree using pointer. But i cant move on on balancing it if i cant even make an unbalanced tree. I think there is something wrong with how i use my pointers. Here is my code:

我用指针练习我的AVL树。但是,如果我甚至不能制作一棵不平衡的树,我就无法继续平衡它。我认为我如何使用指针有问题。这是我的代码:

typedef struct structNode {
   int data;
   struct structNode *left;
   struct structNode *right;
   int height;
} sNode;

void createTree(sNode **node);
void insertNode(sNode **node, int num);

void main(){
   sNode * root = NULL;
   createTree(&root);
}

void createTree(sNode **root){
   int i, num, nodes;

   printf("\n\t\t\t\tNumber of nodes?\n");
   nodes = numScan(1,6);

   for(i=0;i<nodes;i++){
       num = numScan(1,100);
       insertNode(&*root,num);
   }


   printf("\n\n\t\t\t\tPress any key to continue.");
   getch();
}

void insertNode(sNode **root, int num){
   if(*root == NULL){
       sNode *node = malloc(sizeof(node));

       *root = node;

       node->data = num;
       node->left = NULL;
       node->right = NULL;
       node->height = 1;

       return;
   }

   sNode *node = *root;

   if(num < node->data){
       node->left = insertNode(&node->left, num); //void value not ignored as it ought to be
   }
   else
       node->right = insertNode(&node->right, num); //void value not ignored as it ought to be
   }
}

Im basing my code from this site but it doesnt use double pointer so im having troubles learning

我基于我的代码从这个网站,但它不使用双指针所以我有麻烦学习

site: https://www.geeksforgeeks.org/avl-tree-set-1-insertion/

网站:https://www.geeksforgeeks.org/avl-tree-set-1-insertion/

edit: numScan(a,b) basically just scans for a string and figure outs if its a number array or not so that all inputs are numbers (so there are no letters or characters inputted). the numbers in num scan (a and b) are just the range of number allowed to be inputted.

编辑:numScan(a,b)基本上只扫描一个字符串,如果它是一个数字数组,则计算出来,以便所有输入都是数字(所以没有输入字母或字符)。 num扫描(a和b)中的数字只是允许输入的数字范围。

1 个解决方案

#1


1  

As duskwuff said this is a simple unbalanced binary tree, not an AVL one. However, your code is not that bad:

正如duskwuff所说,这是一个简单的不平衡二叉树,而不是AVL。但是,您的代码并没有那么糟糕:

void createTree(sNode **pRoot){
   int i, num, nodes;

   printf("\n\t\t\t\tNumber of nodes?\n");
   nodes = numScan(1,6);

   for(i=0;i<nodes;i++){
       num = numScan(1,100);
       insertNode(pRoot,num); //Just pass the pRoot as it is
   }


   printf("\n\n\t\t\t\tPress any key to continue.");
   getch();
}

int insertNode(sNode **root, int num)
{   //returns the new height of *root
   if(*root == NULL){
       sNode *node = malloc(sizeof(node));

       *root = node;

       node->data = num;
       node->left = NULL;
       node->right = NULL;
       node->height = 1;

       return 1;
   }

   sNode *node = *root;
   int SubtreeHeight;

   if(num < node->data){
       SubtreeHeight = insertNode(&node->left, num); //child enters itself at &node->left if needed
   }
   else
       SubtreeHeight = insertNode(&node->right, num); 
   }
   if (SubtreeHeight>=node->height) //if new subtree is higher.. 
      node->height = SubtreeHeight + 1; //plus node itself
   return node->height;
} 

#1


1  

As duskwuff said this is a simple unbalanced binary tree, not an AVL one. However, your code is not that bad:

正如duskwuff所说,这是一个简单的不平衡二叉树,而不是AVL。但是,您的代码并没有那么糟糕:

void createTree(sNode **pRoot){
   int i, num, nodes;

   printf("\n\t\t\t\tNumber of nodes?\n");
   nodes = numScan(1,6);

   for(i=0;i<nodes;i++){
       num = numScan(1,100);
       insertNode(pRoot,num); //Just pass the pRoot as it is
   }


   printf("\n\n\t\t\t\tPress any key to continue.");
   getch();
}

int insertNode(sNode **root, int num)
{   //returns the new height of *root
   if(*root == NULL){
       sNode *node = malloc(sizeof(node));

       *root = node;

       node->data = num;
       node->left = NULL;
       node->right = NULL;
       node->height = 1;

       return 1;
   }

   sNode *node = *root;
   int SubtreeHeight;

   if(num < node->data){
       SubtreeHeight = insertNode(&node->left, num); //child enters itself at &node->left if needed
   }
   else
       SubtreeHeight = insertNode(&node->right, num); 
   }
   if (SubtreeHeight>=node->height) //if new subtree is higher.. 
      node->height = SubtreeHeight + 1; //plus node itself
   return node->height;
}