Morris' Blog

2011-07-06 11:35:55Morris

a171. 打印樹

留言 0 收藏 0 推薦 0

a171. 打印樹

內容：

首先，請你按照 d526. Binary Search Tree (BST)

將樹建造出來

接下來，就請你將這個樹打印出來

1. 整棵樹，請靠左對齊

2. 層跟層之間的 '\' 以及 '/' 的個數，由最深層開始固定是 0,1,3,7,15 ... A_n (A_n = 2A_n-1+ 1)

詳細請參照範例輸出

怕有人因為瀏覽器的關係，而排版錯誤，附上圖片

輸入說明：

輸入的每一行有一個數字 N ( 1 ≦ N ≦ 20 )

接下來會建入 N 個數字 M ( 1 ≦ M ≦2³¹-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;
}

上一篇：d526. Binary Search Tree (BST) (鏈結版本)

下一篇：d920. 智慧盤

Morris' Blog

a171. 打印樹

你可能感興趣的文章

[舊文] 台中空氣好了沒？關鍵在是否依法減煤

“出差” 詩兩首

自我贖身：差TW$659998508-作嘔33次=TW$659998475

入獄第20天

小事小事