c - 从 AVL 树按升序(排序)打印

Question

我需要定义一个 main 函数来读取整数并按升序打印出来。

    For example, if the input contains

       12
       4
       19
       6

   the program should output

       4
       6
       12
       19

但是我需要使用树来做到这一点。我得到了两个函数 insertavl 和 deleteavl 的使用权供我使用。他们的定义是这样的... http://ideone.com/8dwlU基本上，当调用 deleteavl 时，它会删除节点，并相应地重新平衡树 ... 如果对它们的结构感兴趣，请访问:http://ideone.com/QjlGe .

到目前为止我已经得到了这个:

int main (void) {
   int number;
   struct node *t = NULL;
   while (1 == scanf("%d",&number)) {     
          t = insertavl(t, number);              
   }
   while (t != NULL){
      printf("%d\n",t->data);
      t = deleteavl(t, t->data);    
   }    
}

但这不会按升序打印它们。任何的意见都将会有帮助？提前致谢!

Answer 1

提示: in-order traversal在 BST 上按升序迭代元素。

由于AVL树是BST的具体实现，所以这里也适用。

编辑: 解释 - 为什么 BST 的中序遍历属性是正确的？

在有序 trvaersal 中，在访问左子树中的所有节点后访问 [print] 每个节点。由于在 BST 中根比左子树中的所有节点都大，这就是我们想要的。

此外，在中序遍历中，您在访问右子树中的所有元素之前访问每个节点，同样，因为它是 BST - 这正是我们想要的。

(*)注意:这不是正式的证明，只是一个直观的解释为什么它是真的。