2011-07-06 11:35:55Morris
a171. 打印樹
a171. 打印樹 
內容 ：
首先，請你按照 d526. Binary Search Tree (BST)
將樹建造出來
接下來，就請你將這個樹打印出來
1. 整棵樹，請靠左對齊
2. 層跟層之間的 '\' 以及 '/' 的個數，由最深層開始固定是 0,1,3,7,15 ... An (An = 2An-1+ 1)
詳細請參照範例輸出
怕有人因為瀏覽器的關係，而排版錯誤，附上圖片
輸入說明 ：
輸入的每一行有一個數字 N ( 1 ≦ N ≦ 20 )
接下來會建入 N 個數字 M ( 1 ≦ M ≦231-1 )
× 數字重複，就不必建入
輸出說明 ：
打印出這棵樹
範例輸入 ：
11368 115 121 88 741 762 801 34 41 511 6065 2 10 4 9 15
範例輸出 ：
X / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ X X / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ X X X X / \ / \ / \X X \ X X X / \X X X X X
提示 ：
× 若測資有誤,請多多包涵
出處 ：
BST | 字串 (管理：morris1028)
由於是本人出的題目，在保證測資是對之前
暫時不提供程式碼
example 看 here
15
8 4 2 6 1 3 5 7 12 10 14 9 11 13 15
/ \
/ \
/ \
/ \
/ \ / \
/ \ / \
/ \ / \ / \ / \
長度剛好是 1 2 4 8 ...
正版如下
X
/ \
/ \
/ \
X X
/ \ / \
X X X X
X X X X X X X X
XXXXXXXXXXXXXXX <= 往上對，剛好 1 to 1
只要在迴圈的0 1 3 7 輸出 X就好哩
31
16 8 4 2 6 1 3 5 7 12 10 14 9 11 13 15 24 20 18 22 17 19 21 23 28 26 30 25 27 29 31
X
/ \
/ \
/ \
/ \
/ \
/ \
/ \
X X
/ \ / \
/ \ / \
/ \ / \
X X X X
/ \ / \ / \ / \
X X X X X X X X
X X X X X X X X X X X X X X X X
X
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \ / \ / \
/ \ / \ / \ / \
/ \ / \ / \ / \ / \ / \ / \ / \
#include<stdio.h>
#include<stdlib.h>
#define N 21
#define AnsL 1048576
struct node {
int v, level;
struct node *lc, *rc;
}*root, *curr, *temp, *Queue[N];
int Shift[N] = {1}, BaseShift[N], BaseSpace[N];
char Ans[AnsL];
void PrintTree(int MaxLevel) {
int max_l = 0, shift, Qt = 0, last, At;
int a, b, c, d, e;
Queue[0] = root, BaseShift[0] = Shift[MaxLevel];
for(a = 0; a <= Qt; a++) {
curr = Queue[a], BaseSpace[a] = 1;
if(curr->lc != NULL)
Queue[++Qt] = curr->lc, BaseShift[Qt] = BaseShift[a] - Shift[MaxLevel - curr->lc->level];
if(curr->rc != NULL)
Queue[++Qt] = curr->rc, BaseShift[Qt] = BaseShift[a] + Shift[MaxLevel - curr->rc->level];
}
curr = root;
shift = BaseShift[0] + 1;
while(curr->lc != NULL)
max_l++, curr = curr->lc, shift -= Shift[MaxLevel - curr->level];
last = shift, At = 0;
for(; last <= BaseShift[0]; last++) Ans[At++] = ' ';
Ans[At++] = 'X', Ans[At] = '\0', puts(Ans);
for(a = 0; a <= Qt; a++) {
if(a != 0 && Queue[a]->level == Queue[a-1]->level) continue;
for(b = Shift[MaxLevel - Queue[a]->level - 1]; b > 0; b--) {
last = shift, At = 0;
for(c = a; c <= Qt; c++) {
curr = Queue[c];
if(curr->lc != NULL || curr->rc != NULL)
for(; last < BaseShift[c]; last++) Ans[At++] = ' ';
if(curr->lc != NULL) {
Ans[At++] = b == 1 ? 'X': '/', last++;
}
else {
if(last <= BaseShift[c])
Ans[At++] = ' ', last++;
}
if(curr->rc != NULL)
for(e = 1; e <= BaseSpace[c]; e++) {
if(BaseShift[c] + e< last) continue;
Ans[At++] = ' ', last++;
}
if(curr->rc != NULL) Ans[At++] = b == 1 ? 'X' : '\\';
else Ans[At++] = ' ';
BaseShift[c]--, BaseSpace[c] += 2, last++;
if(c < Qt && Queue[c]->level != Queue[c+1]->level) break;
}
while(At > 0 && Ans[At-1] == ' ') At--;
Ans[At] = '\0', puts(Ans);
}
}
for(a = 0; a <= Qt; a++)
free(Queue[a]);
}
main() {
int n, m, a, MaxLevel;
for(a = 1; a <= 20; Shift[a] = Shift[a-1]*2, a++);
while(scanf("%d", &n) == 1) {
scanf("%d", &m);
temp = (struct node*)malloc(sizeof(struct node));
temp->v = m, temp->lc = temp->rc = NULL, temp->level = 0;
root = temp;
for(a = 1, MaxLevel = 0; a < n; a++) {
scanf("%d", &m);
curr = root;
while(1) {
if(curr->v > m) {
if(curr->lc == NULL) {
temp = (struct node*)malloc(sizeof(struct node));
temp->v = m, temp->lc = temp->rc = NULL, temp->level = curr->level+1;
if(temp->level > MaxLevel) MaxLevel = temp->level;
curr->lc = temp; break;
}
else
curr = curr->lc;
}
else if(curr->v < m) {
if(curr->rc == NULL) {
temp = (struct node*)malloc(sizeof(struct node));
temp->v = m, temp->lc = temp->rc = NULL, temp->level = curr->level+1;
if(temp->level > MaxLevel) MaxLevel = temp->level;
curr->rc = temp; break;
}
else
curr = curr->rc;
}
else
break;
}
}
PrintTree(MaxLevel);
}
return 0;
}
由於是本人出的題目，在保證測資是對之前
暫時不提供程式碼
example 看 here
15
8 4 2 6 1 3 5 7 12 10 14 9 11 13 15
/ \
/ \
/ \
/ \
/ \ / \
/ \ / \
/ \ / \ / \ / \
長度剛好是 1 2 4 8 ...
正版如下
X
/ \
/ \
/ \
X X
/ \ / \
X X X X
X X X X X X X X
XXXXXXXXXXXXXXX <= 往上對，剛好 1 to 1
只要在迴圈的0 1 3 7 輸出 X就好哩
31
16 8 4 2 6 1 3 5 7 12 10 14 9 11 13 15 24 20 18 22 17 19 21 23 28 26 30 25 27 29 31
X
/ \
/ \
/ \
/ \
/ \
/ \
/ \
X X
/ \ / \
/ \ / \
/ \ / \
X X X X
/ \ / \ / \ / \
X X X X X X X X
X X X X X X X X X X X X X X X X
X
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \ / \ / \
/ \ / \ / \ / \
/ \ / \ / \ / \ / \ / \ / \ / \
#include<stdio.h>
#include<stdlib.h>
#define N 21
#define AnsL 1048576
struct node {
int v, level;
struct node *lc, *rc;
}*root, *curr, *temp, *Queue[N];
int Shift[N] = {1}, BaseShift[N], BaseSpace[N];
char Ans[AnsL];
void PrintTree(int MaxLevel) {
int max_l = 0, shift, Qt = 0, last, At;
int a, b, c, d, e;
Queue[0] = root, BaseShift[0] = Shift[MaxLevel];
for(a = 0; a <= Qt; a++) {
curr = Queue[a], BaseSpace[a] = 1;
if(curr->lc != NULL)
Queue[++Qt] = curr->lc, BaseShift[Qt] = BaseShift[a] - Shift[MaxLevel - curr->lc->level];
if(curr->rc != NULL)
Queue[++Qt] = curr->rc, BaseShift[Qt] = BaseShift[a] + Shift[MaxLevel - curr->rc->level];
}
curr = root;
shift = BaseShift[0] + 1;
while(curr->lc != NULL)
max_l++, curr = curr->lc, shift -= Shift[MaxLevel - curr->level];
last = shift, At = 0;
for(; last <= BaseShift[0]; last++) Ans[At++] = ' ';
Ans[At++] = 'X', Ans[At] = '\0', puts(Ans);
for(a = 0; a <= Qt; a++) {
if(a != 0 && Queue[a]->level == Queue[a-1]->level) continue;
for(b = Shift[MaxLevel - Queue[a]->level - 1]; b > 0; b--) {
last = shift, At = 0;
for(c = a; c <= Qt; c++) {
curr = Queue[c];
if(curr->lc != NULL || curr->rc != NULL)
for(; last < BaseShift[c]; last++) Ans[At++] = ' ';
if(curr->lc != NULL) {
Ans[At++] = b == 1 ? 'X': '/', last++;
}
else {
if(last <= BaseShift[c])
Ans[At++] = ' ', last++;
}
if(curr->rc != NULL)
for(e = 1; e <= BaseSpace[c]; e++) {
if(BaseShift[c] + e< last) continue;
Ans[At++] = ' ', last++;
}
if(curr->rc != NULL) Ans[At++] = b == 1 ? 'X' : '\\';
else Ans[At++] = ' ';
BaseShift[c]--, BaseSpace[c] += 2, last++;
if(c < Qt && Queue[c]->level != Queue[c+1]->level) break;
}
while(At > 0 && Ans[At-1] == ' ') At--;
Ans[At] = '\0', puts(Ans);
}
}
for(a = 0; a <= Qt; a++)
free(Queue[a]);
}
main() {
int n, m, a, MaxLevel;
for(a = 1; a <= 20; Shift[a] = Shift[a-1]*2, a++);
while(scanf("%d", &n) == 1) {
scanf("%d", &m);
temp = (struct node*)malloc(sizeof(struct node));
temp->v = m, temp->lc = temp->rc = NULL, temp->level = 0;
root = temp;
for(a = 1, MaxLevel = 0; a < n; a++) {
scanf("%d", &m);
curr = root;
while(1) {
if(curr->v > m) {
if(curr->lc == NULL) {
temp = (struct node*)malloc(sizeof(struct node));
temp->v = m, temp->lc = temp->rc = NULL, temp->level = curr->level+1;
if(temp->level > MaxLevel) MaxLevel = temp->level;
curr->lc = temp; break;
}
else
curr = curr->lc;
}
else if(curr->v < m) {
if(curr->rc == NULL) {
temp = (struct node*)malloc(sizeof(struct node));
temp->v = m, temp->lc = temp->rc = NULL, temp->level = curr->level+1;
if(temp->level > MaxLevel) MaxLevel = temp->level;
curr->rc = temp; break;
}
else
curr = curr->rc;
}
else
break;
}
}
PrintTree(MaxLevel);
}
return 0;
}