有序的树

如果一棵树满足"左边的都比我小、右边的都比我大"，它就叫二叉搜索树，像图书馆按编号摆书：小编号往左放，大编号往右放。神奇的是，对它做一次中序遍历，数字正好从小到大排好队！因为中序总是先取尽左边最小的，再取自己，再取右边更大的。

#include <iostream>
using namespace std;
struct Node { int val; Node* l; Node* r; };
void mid(Node* p){ if(!p) return; mid(p->l); cout<<p->val<<" "; mid(p->r);}
int main(){
    Node n1{1,0,0}, n4{4,0,0}, n7{7,0,0};
    Node n2{2,&n1,&n4};       // 2 左小右大
    Node root{5,&n2,&n7};
    mid(&root); // 输出：1 2 4 5 7，天然有序
}

要注意：只有满足"左小右大"这条规则，中序才有序。随便一棵普通树是不会自动排好序的。