24h購物| | PChome| 登入
2011-07-06 08:00:34| 人氣3,974| 回應0 | 上一篇 | 下一篇

d526. Binary Search Tree (BST) (鏈結版本)

推薦 0 收藏 0 轉貼0 訂閱站台

d526. Binary Search Tree (BST)

內容 :

某次測驗的第29題

內容如下 :
將下列建值輸入,直接建立一個二元搜尋樹, 368,115,121,88,741,762,801,34,41,511,60,欲找建值為34的節點,從368節點為第一次起算,需要做幾次比較 ? 

(A) 2 (B) 3 (C) 4 (D) 5

只是想請你建出一個二元搜尋樹,並輸出此樹的前序搜尋 (中左右)

輸入說明 :

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

接下來會建入 N 個數字 M ( 1 ≦ M ≦231-1 ) ,且沒有數字會重複

輸出說明 :

輸出該樹的前序搜尋結果。

範例輸入 :

11368 115 121 88 741 762 801 34 41 511 6065 2 10 4 9 15

範例輸出 :

368 115 88 34 41 60 121 741 511 762 8015 2 4 10 9 15

提示 :

Binary Search Tree

出處 :

BST (管理:morris1028)



沒辦法傳C啊,真是痛苦

/**********************************************************************************/
/*  Problem: d526 "Binary Search Tree (BST)" from BST                             */
/*  Language: CPP                                                                 */
/*  Result: AC (64ms, 768KB) on ZeroJudge                                         */
/*  Author: morris1028 at 2011-07-06 07:48:35                                     */
/**********************************************************************************/


#include<stdio.h>
#include<stdlib.h>
struct node {
    int v;
    struct node *lc, *rc;
}*root, *curr, *temp;
void Print(node *now) {
    printf("%d ", now->v);
    if(now->lc != NULL)    Print(now->lc);
    if(now->rc != NULL)    Print(now->rc);
    free(now);
}
main() {
    int n, m, a;
    while(scanf("%d", &n) == 1) {
        scanf("%d", &m);
        temp = (struct node*)malloc(sizeof(struct node));
        temp->v = m, temp->lc = temp->rc = NULL;
        root = temp;
        for(a = 1; 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;
                        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;
                        curr->rc = temp; break;
                    }
                    else
                        curr = curr->rc;
                }
                else
                    break;
            }
        }
        Print(root), puts("");
    }
    return 0;    
}

台長: Morris
人氣(3,974) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:a171. 打印樹
此分類上一篇:d627. 我.我.我...這麼弱 -跨年倒數

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文