从AVL树中升序打印（排序）

Question

我需要定义一个主函数，它可以读取整数并按升序将它们打印出来。

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

但是这并不按升序打印它们。有什么建议吗？提前感谢！

- Thatdude1

Answer 1

提示: 中序遍历 一棵 二叉搜索树(BST) 可以按升序迭代元素。

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

编辑: 解释 - 为什么在BST上进行中序遍历的这个属性是正确的？

在中序遍历中，你在访问完所有左子树的节点后才访问[打印]每个节点。由于在BST中，根节点比左子树中的所有节点都大，这正是我们想要的。

此外，在中序遍历中，你在访问所有右子树元素之前访问每个节点，再次，由于它是BST - 这正是我们想要的。

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

- amit

---

真的吗？我只需要在构建树之后使用中序遍历函数将其按升序排列就可以了吗？ - Thatdude1

@Beginnernato：看一下我附上的维基百科链接，里面有一个中序遍历函数的伪代码，我认为它很容易。只需实现并运行它，它应该可以工作[除非程序的其他部分存在错误]。 - amit

@Beginnernato：我在BST中添加了对该属性的解释。所以，是的，你只需要按照中序遍历打印元素即可。 - amit

我意识到使用中序遍历时，我不需要使用deleteavl，但我需要使用它来释放节点。 - Thatdude1

@Beginnernato：是的，为了避免内存泄漏，在从main()函数返回之前，您需要删除所有节点。 - amit

你的回复真快，我猜我们的教授应该教过我们横向遍历... 谢谢你的帮助，阿米特 :) - Thatdude1