hdu3999 The order of a Tree（BST的建立）

http://acm.hdu.edu.cn/showproblem.php?pid=3999

题意：给你一个序列可以构成一个二叉搜索树，求此二叉搜索树字典序最小的输入序列。

思路：这题只要明确一点就可以做出。由于二叉搜索树插入的时候是先插入根，再插入左，再插入右，这正好和前序遍历的顺序一样。所以二叉搜索树字典序最小的输入序列即为前序遍历序列。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include using namespace std;const int MAXN = 1005;
const int INF = INT_MAX;struct Treenode{int data;Treenode* leftchild;Treenode* rightchild;Treenode(int d) : data(d), leftchild(NULL), rightchild(NULL) {}
};Treenode* Insert(Treenode* root, int value){if(root == NULL){root = new Treenode(value);return root;}if(value < root->data) root->leftchild = Insert(root->leftchild, value);if(value > root->data) root->rightchild = Insert(root->rightchild, value);return root;
}void PreOrder(Treenode* root, bool flag){if(root == NULL) return;if(flag) printf(" ");flag = true;printf("%d", root->data);PreOrder(root->leftchild, flag);PreOrder(root->rightchild, flag);return;
}int main(){//   freopen("in.txt", "r", stdin);int n, x;while(~scanf("%d", &n)){Treenode* root = NULL;for(int i = 0; i < n; i++){scanf("%d", &x);root = Insert(root, x);}PreOrder(root, false);printf("\n");}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！