横向打印二叉树

题目：

二叉树可以用于排序。其原理很简单：对于一个排序二叉树添加新节点时，先与根节点比较，若小则交给左子树继续处理，否则交给右子树。

当遇到空子树时，则把该节点放入那个位置。

比如，10 8 5 7 12 4 的输入顺序，应该建成二叉树如下图所示，其中.表示空白。

...|-12
10-|
...|-8-|
.......|...|-7
.......|-5-|
...........|-4

本题目要求：根据已知的数字，建立排序二叉树，并在标准输出中横向打印该二叉树。

输入格式

输入数据为一行空格分开的N个整数。 N<100，每个数字不超过10000。

输入数据中没有重复的数字。

输出格式

输出该排序二叉树的横向表示。为了便于评卷程序比对空格的数目，请把空格用句点代替：

样例输入1

10 5 20

样例输出1

...|-20
10-|
...|-5

样例输入2

5 10 20 8 4 7

样例输出2

.......|-20
..|-10-|
..|....|-8-|
..|........|-7
5-|
..|-4

分析：排序二叉树，主要是输出，先将各个结点所在的输出层下标计算好了，然后每次都从节点的左边子节点的输出层下标layer到节点的右边子节点的输出层下标，依次替换数组”.“，为”|“。主要就是这个有时候会想不到，还有数组的结束符\0要加上。

代码：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef struct node {int u;int layer;//所在层数int ls=0;//左子树个数int rs=0;//右子树个数struct node *left;struct node *right;
}pNode, *Node;
int depth[10000];
int val[100];
int n;
char mp[110][710];
bool createTree(Node &T, int u) {if (T->u < u) {T->rs++;if (T->right == NULL) {Node next = new pNode();next->u = u;T->right = next;return true;}else {if (createTree(T->right, u))return true;}}else if (T->u > u) {T->ls++;if (T->left == NULL) {Node next = new pNode();next->u = u;T->left = next;return true;}else {if (createTree(T->left, u))return true;}}
}
int dp(Node &T, int v, int layer) {if (T->u < v) {dp(T->right, v, layer + 1);}else if (T->u > v) {dp(T->left, v, layer + 1);}else  if (T->u == v) {return layer;}
}
int intostr(int num,char *x) {int k = 0;while (num != 0) {x[k++]=char(num % 10+'0');num /= 10;}return k;
}
void deep(int id,Node &u) {//计算各个节点层数u->layer= u->rs + id+1;if (u->right != NULL)deep(id, u->right);if (u->left != NULL)deep(u->layer, u->left);
}
void solve(Node &u,int indexs) {char t[6];int lt = intostr(u->u, t);for (int i =0; i layer][i + indexs] = t[lt-i-1];}if (u->right != NULL || u->left != NULL) {mp[u->layer][indexs += lt] = '-';int mins = u->layer, maxs = u->layer;if (u->right != NULL) {mins = u->right->layer;mp[mins][indexs + 2] = '-';solve(u->right, indexs + 3);}if (u->left != NULL) {maxs = u->left->layer;mp[maxs][indexs + 2] = '-';solve(u->left, indexs + 3);}for (int i = mins; i <= maxs; i++) {mp[i][indexs + 1] = '|';}mp[u->layer][indexs + 2] = '\0';}else {mp[u->layer][indexs+lt] = '\0';return;//没有子节点就返回}
}
int main() {int a;while (cin >> a) {n = 0;memset(mp, '.', sizeof(mp));val[n++] = a;Node t = new pNode();t->u = a;while (cin >> a) {createTree(t, a);;val[n++] = a;}/*	sort(val, val + n);for (int i = 0; i < n; i++) {depth[i] = dp(t, val[i], 0);cout << val[i] << ":" << depth[i] << endl;}*/deep(0, t);solve(t, 0);for (int i = 1; i <=n; i++) {cout << mp[i] << endl;}}//system("pause");return 0;
}

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