【ACM】- PAT. A1099 Build a Binary Search Tree 【BST】

题目链接

题目分析

1、给出一棵树结构和一组值，把这些值填入树中构成BST（唯一） 2、输出其层序遍历！ 3、节点编号 0 ~ N-1，0号为根

解题思路：

方法一： （推荐） 由于BST的中序遍历序列为递增序列，所以把所给值递增排序后，中序遍历插入二叉树结构中；

方法二： 先后序遍历获得每个结点左右子树的结点数，对值序列进行切分，并赋值

---

方法一：中序遍历赋值

/********************************** *@ID: 3stone *@ACM: PAT.A1099 Build A Binary Search Tree *@Time: 17/3/8 *@IDE: VSCode 2017 + clang++ ***********************************/ #include<cstdio> #include<algorithm> #include<queue> using namespace std; const int maxn = 1000; struct Node{ int lchild; int rchild; int c; }node[maxn]; int num = 0, seq[maxn]; void in_order(int key){//中序遍历赋值 if(node[key].lchild != -1){ in_order(node[key].lchild); } node[key].c = seq[num++]; if(node[key].rchild != -1){ in_order(node[key].rchild); } } //层次遍历 void bfs_traversal() { int flag = 0; queue<int> Q; Q.push(0); while(Q.empty() == false){ int front = Q.front(); Q.pop(); if(0 == flag){ flag = 1; printf("%d", node[front].c); } else printf(" %d", node[front].c); //左右子节点入栈 if(node[front].lchild != -1) Q.push(node[front].lchild); if(node[front].rchild != -1) Q.push(node[front].rchild); } printf("\n"); }//bfs int main(){ int n; while(scanf("%d", &n) != EOF){ for(int i = 0; i < n; i++){ scanf("%d%d", &node[i].lchild, &node[i].rchild); } for(int i = 0; i < n; i++){ scanf("%d", &seq[i]); } sort(seq, seq + n); //递增排序 //中序遍历二叉树 //node[0]是根节点 num = 0; in_order(0); bfs_traversal(); }//while-scanf return 0; }

---

方法二：切分序列

| 解题思路 存储结构：树的静态存储！ 1、所给值 先排序 2、需要知道左右子树包含的结点个数，进而切分 值序列。 3、如何知道左右子树结点数？ 结点结构体增加一个变量记录子结点数量，后序遍历赋值

/********************************** *@ID: 3stone *@ACM: PAT.A1099 Build A Binary Search Tree *@Time: 18/8/16 *@IDE: VSCode 2018 + clang++ ***********************************/ #include<cstdio> #include<algorithm> #include<queue> #include<cmath> #include<cstring> using namespace std; const int maxn = 110; struct node{ //数结点 int data; int nodes_num; int lchild; int rchild; }Node[maxn]; bool flag; //在建树过程中 标记是否能成功 int seq[maxn]; //保存输入的前序序列 int N; //结点数 //建立正常BST void create(int root, int left, int right) { if(root == -1) return; int lchild_num = Node[Node[root].lchild].nodes_num; //左子树的结点数 int root_key = left + lchild_num; //切分 Node[root].data = seq[root_key]; //赋值 //递归 建树 create(Node[root].lchild, left, left + lchild_num - 1); create(Node[root].rchild, left +lchild_num + 1, right); } void BFS_traversal() { queue<int> Q; Q.push(0); int num = 0; while(!Q.empty()) { int front = Q.front(); Q.pop(); num++; if(num == N) printf("%d\n", Node[front].data); else printf("%d ", Node[front].data); if(Node[front].lchild != -1) Q.push(Node[front].lchild); if(Node[front].rchild != -1) Q.push(Node[front].rchild); } } //后序遍历 （回溯赋值每个结点左右子树所含的结点数） int post_traversal(int v) { if(v == -1) return 0; int lchild_num = post_traversal(Node[v].lchild); int rchild_num = post_traversal(Node[v].rchild); Node[v].nodes_num = lchild_num + rchild_num + 1; return Node[v].nodes_num; } int main() { while(scanf("%d", &N) != EOF) { //input BST structure for(int i = 0; i < N; i++){ scanf("%d%d", &Node[i].lchild, &Node[i].rchild); } //input seq[] for(int i = 0; i < N; i++) scanf("%d", &seq[i]); //后序遍历 （回溯赋值每个结点左右子树所含的结点数） post_traversal(0); // the key of root = 0 sort(seq, seq + N); //待插入值先排序 create(0, 0, N - 1); BFS_traversal(); } return 0; }