C中的双指针AVL树

Question

我正在使用指针练习我的 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
   }
}

我的代码基于此站点，但它不使用双指针，所以我在学习时遇到了麻烦

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

编辑：numScan(a,b) 基本上只是扫描一个字符串并确定它是否是一个数字数组，以便所有输入都是数字（因此没有输入字母或字符）。 num scan中的数字（a和b）只是允许输入的数字范围。

Answer 1

正如 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;
}

C中的双指针AVL树

Double pointer AVL Tree in C

c

data-structures

linked-list

binary-tree

avl-tree