3

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

    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/ ｛｝｝｝．

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

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);    
   }    
}

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

4

1 回答 1

4

提示： BST上的按序遍历是按升序迭代元素。

由于 AVL 树是 BST 的特定实现，因此它也适用于此。

编辑：解释-为什么在 BST 上按顺序遍历的这个属性是正确的？

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

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

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

于 2012-03-04T18:45:34.063 回答