建设零食网站的可行性,莱芜百度网站优化,郑州市重点项目建设办公室网站,云职上海企业服务有限公司二叉树垂直遍历题目描述输入输出示例输入实例输出DFSBFS更简单的方法二叉树垂直遍历题目描述对于一个二叉树#xff0c;输出它的垂直遍历结果#xff1b;对于同一列的节点#xff0c;按照从左向右#xff0c;从上向下的顺序排列。例如#xff0c;对于以下二叉树#xff1…二叉树垂直遍历题目描述输入输出示例输入实例输出DFSBFS更简单的方法二叉树垂直遍历题目描述对于一个二叉树输出它的垂直遍历结果对于同一列的节点按照从左向右从上向下的顺序排列。例如对于以下二叉树1/ \2 3/4垂直遍历的结果是2 1 4 3输入输出输入- 第一行是n表示节点个数(节点编号从0到n-1)当n-1时表示输入结束- 之后的n行每一行有三个整数分别表示节点的数值左子树的编号右子树的编号(编号-1表示节点为空)输出- 针对每组输入输出垂直遍历的结果示例输入41 1 22 -1 -13 3 -14 -1 -1-1实例输出2 1 4 3DFS#include#include#include#include#include#includeusing namespace std;struct Node {int data;Node *left;Node *right;};class TreePrint {private:map nmap;public:void dfs(Node *root, int pos) {if (root NULL) return;nmap[pos].push_back(root-data);dfs(root-left, pos-1);dfs(root-right, pos1);}void display() {int min0;while (nmap.find(min) ! nmap.end()) --min;for (int imin1; nmap.find(i) ! nmap.end(); i)for (vector::iterator it nmap[i].begin();it ! nmap[i].end(); it)printf(%d , *it);printf(\n);}};int main() {ifstream in(../input.txt);int n;in n;while (n ! -1) {Node *tree new Node[n];for (int i0; iint tmp, left, right;in tmp left right;tree[i].data tmp;if (left ! -1) tree[i].left tree[left];else tree[i].left NULL;if (right ! -1) tree[i].right tree[right];else tree[i].right NULL;}TreePrint tp;tp.dfs(tree[0], 0);tp.display();in n;}in.close();return 0;}然而这个结果并不正确不能妥善的处理孩子节点超过父节点的深度的情况。BFS#include#include#include#include#include#includeusing namespace std;struct Node {int data;Node *left;Node *right;};class TreePrint {private:map nmap;public:void dfs(Node *root, int pos) {if (root NULL) return;nmap[pos].push_back(root-data);dfs(root-left, pos-1);dfs(root-right, pos1);}void bfs(Node *root) {queue q;queue qpos;q.push(root);qpos.push(0);while (!q.empty()) {Node *tmp q.front();int pos qpos.front();q.pop();qpos.pop();nmap[pos].push_back(tmp-data);if (tmp-left ! NULL) {q.push(tmp-left);qpos.push(pos-1);}if (tmp-right ! NULL) {q.push(tmp-right);qpos.push(pos1);}}}void display() {int min0;while (nmap.find(min) ! nmap.end()) --min;for (int imin1; nmap.find(i) ! nmap.end(); i)for (vector::iterator it nmap[i].begin();it ! nmap[i].end(); it)printf(%d , *it);printf(\n);}};int main() {ifstream in(../input.txt);int n;in n;while (n ! -1) {Node *tree new Node[n];for (int i0; iint tmp, left, right;in tmp left right;tree[i].data tmp;if (left ! -1) tree[i].left tree[left];else tree[i].left NULL;if (right ! -1) tree[i].right tree[right];else tree[i].right NULL;}TreePrint tp;tp.bfs(tree[0]);tp.display();in n;}in.close();return 0;}更简单的方法由于输入的时候就是BFS遍历所以输入的时候就可以进行排序#include#include#include#includeusing namespace std;struct Node {int data;int id;int colum;};bool compareTo(Node l, Node r) {if (l.colum r.colum) return l.id r.id;else return l.colum r.colum;}int main() {ifstream in(../input.txt);int n;in n;while (n ! -1) {queue q;q.push(0);Node *tree new Node[n];tree[0].colum 0;for (int i0; iint tmp, left, right;in tmp left right;tree[i].data tmp;tree[i].id i;int pos q.front();q.pop();if (left ! -1) {tree[left].colum pos - 1;q.push(pos-1);}if (right ! -1) {tree[right].colum pos 1;q.push(pos1);}}sort(tree, treen, compareTo);for (int i0; iprintf(%d , tree[i].data);}printf(\n);in n;}in.close();return 0;}
