2011-07-06 08:00:34Morris
d526. Binary Search Tree (BST) (鏈結版本)
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
出處 ：
/* 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;
}
下一篇：a171. 打印樹