(BST二叉搜索树 1.1)hdoj 3999The order of a Tree(二叉搜索树的前序遍历)

忘是亡心i 2022-02-28 00:20 159阅读 0赞

# The order of a Tree #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 2738 Accepted Submission(s): 1454**

**Problem Description**

As we know,the shape of a binary search tree is greatly related to the order of keys we insert. To be precisely:  
1. insert a key k to a empty tree, then the tree become a tree with  
only one node;  
2. insert a key k to a nonempty tree, if k is less than the root ,insert  
it to the left sub-tree;else insert k to the right sub-tree.  
We call the order of keys we insert “the order of a tree”,your task is,given a oder of a tree, find the order of a tree with the least lexicographic order that generate the same tree.Two trees are the same if and only if they have the same shape.

**Input**

There are multiple test cases in an input file. The first line of each testcase is an integer n(n <= 100,000),represent the number of nodes.The second line has n intergers,k1 to kn,represent the order of a tree.To make if more simple, k1 to kn is a sequence of 1 to n.

**Output**

One line with n intergers, which are the order of a tree that generate the same tree with the least lexicographic.

**Sample Input**

4 1 3 4 2

**Sample Output**

1 3 2 4

>     #include <iostream>
>     #include <cstdio>
>     
>     
>     /*
>      * 二叉搜索树模板题
>      */
>     using namespace std;
>     
>     
>     /*
>      * 定义节点
>      */
>     typedef struct node {
>         int data;
>         node *lchild;
>         node *rchild;
>     } BSTNode, *BST;
>     
>     
>     bool isFirstTime = true;
>     
>     
>     /*
>      * 二叉树的插入操作.
>      *
>      */
>     void insert(BST &T, int data) {
>     
>         /*
>          * 如果当前二叉树为空
>          */
>         if (T == NULL) {
>             //新建根节点
>             T = new BSTNode();
>     
>             T->data = data;
>             T->lchild = NULL;
>             T->rchild = NULL;
>             return;
>         }
>     
>         /*
>          * 如果插入的数值小于根节点的数值
>          */
>         if (data < T->data) {
>             //插入左子树
>             insert(T->lchild, data);
>         } else {
>             //否则,插入右子树
>             insert(T->rchild, data);
>         }
>     }
>     
>     
>     /*
>      * 前序遍历
>      */
>     void preOrder(BST &T) {
>     
>         //如果当前的树不为空
>         if (T != NULL) {
>     
>             //格式上的要求,和算法本身无关
>             if (isFirstTime == false) {
>                 printf(" ");
>             }
>     
>             isFirstTime = false;
>     
>             //访问根节点
>             printf("%d", T->data);
>             //访问左子树
>             preOrder(T->lchild);
>             //访问右子树
>             preOrder(T->rchild);
>         }
>     }
>     
>     
>     int main() {
>     
>         int n;
>     
>         while (scanf("%d", &n) != EOF) {
>             BST T = NULL;
>     
>             isFirstTime = true;
>             int i;
>             for (i = 0; i < n; ++i) {
>                 int data;
>                 scanf("%d", &data);
>                 insert(T,data);
>             }
>     
>     
>             preOrder(T);
>     
>             //不加会PE
>             printf("\n");
>         }
>     
>         return 0;
>     }