重新排序二进制搜索树“就地”

我想要一些有用的建议或代码来实现根据以下方式运行的程序：

1. 从命令行上的整数序列构建二进制搜索树（按给定的顺序）

2. 重新排序树，以便值以降序显示，即新树具有：

   • 左子树中的所有值都大于根
   • 右子树中的所有值均小于根
   • 此属性适用于树中的所有节点

重新排序必须不涉及从输入整数构建新树（我已经实现了这一点）；取而代之的是，它必须简单地在同一棵树中对它们进行重新排序。

到目前为止，这是我的代码，使用了错误的方法（即制作两个单独的树并使用不同的规则插入它们）。

typedef struct node{
    int value;
    struct node *left;
    struct node *right; 
} NodeT;

NodeT *newNode(int);
NodeT *insertAscend(NodeT *, int);
NodeT *insertDescend(NodeT *, int);
void printTree(NodeT *, int);
void freeTree(NodeT *);

int main(int argc,char *argv[]){
    NodeT *t1 = NULL;
    NodeT *t2 = NULL;
    int i;
    int retval = 0;

    if(argc == 1){
        fprintf(stderr, "Usage: %s integers ...\n", argv[0]);
        retval = 1;
    }else{
        int dataGood = 1;
        for(i =1; i < argc && dataGood; i++){
            int num;
            if(sscanf(argv[i], "%d", &num) != 1){
                fprintf(stderr, "Usage: %s integers ...\n", argv[0]);
                freeTree(t1);
                freeTree(t2);
                dataGood = 0;
                retval = 1;
            }else{
                t1 = insertAscend(t1, num);
                t2 = insertDescend(t2, num);
            }
        }
        if(dataGood){
            printTree(t1, 0);

            printf("Swapped tree:\n");
            printTree(t2, 0);
            freeTree(t1);
            freeTree(t2);

        }
    }

    return retval;
}

NodeT *newNode(int v){
    NodeT *new;
    new = (NodeT *)malloc(sizeof(NodeT));
    assert(new != NULL);
    new->value = v;
    new->left = NULL;
    new->right = NULL;
    return new;
}

NodeT *insertAscend(NodeT *t, int v){
    if(t == NULL){
        t = newNode(v);
    }else if(v == t->value){
        ; // no duplicates
    }else if(v < t->value){
        t->left = insertAscend(t->left, v);
    }else if(v > t->value){
        t->right = insertAscend(t->right, v);
    }
    return t;
}

NodeT *insertDescend(NodeT *t, int v){
    if(t == NULL){
        t = newNode(v);
    }else if(v == t->value){
        ; // no duplicates
    }else if(v > t->value){
        t->left = insertDescend(t->left, v);
    }else if(v < t->value){
        t->right = insertDescend(t->right, v);
    }
    return t;
}

void printTree(NodeT *t, int depth){
    if(t != NULL){
        depth++;
        printTree(t->left, depth);
        int i;
        for(i = 1; i < depth; i++){
            putchar('\t');
        }
        printf("%d\n", t->value);
        printTree(t->right, depth);
    }
}

void freeTree(NodeT *t){
    if(t != NULL){
        freeTree(t->left);
        freeTree(t->right);
        free(t);
    }
}

我再次在寻求帮助，以方便地重新安排BST的位置，而无需创建任何新的数据结构。如果下面的代码没有为那些愿意测试的人运行，我可以提供更多的说明和一些所需的示例。我对此很感兴趣，因为我已经看到该问题在以前的公司和考试面试中使用过，似乎无法根据他们的指导方针有效地实施。