d526: Binary Search Tree (BST)

2019-08-29

內容

某次測驗的第 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 ) ，且沒有數字會重複

11
368 115 121 88 741 762 801 34 41 511 60
6
5 2 10 4 9 15

輸出

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

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

解題思路

實作二分搜索樹。

完整程式碼

AC (28ms, 128KB)

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int value;
    struct Node* lhs, * rhs;
}Node;

inline Node* newNode(int value)
{
    Node* res = malloc(sizeof(Node));
    res->value = value;
    res->lhs = res->rhs = NULL;
    return res;
}

inline void setNode(Node* now, int value)
{
    for (;;)
    {
        if (value < now->value)
        {
            if (now->lhs)
                now = now->lhs;
            else
            {
                now->lhs = newNode(value);
                break;
            }
        }
        else
        {
            if (now->rhs)
                now = now->rhs;
            else
            {
                now->rhs = newNode(value);
                break;
            }
        }
    }
}

void serchNode(Node* now)
{
    if (now)
    {
        printf("%d ", now->value);
        serchNode(now->lhs);
        serchNode(now->rhs);
        free(now);
    }
}

int main()
{
    int n, tmp;
    while (scanf(" %d", &n) == 1)
    {
        Node root = { 0 };
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &tmp);
            setNode(&root, tmp);
        }
        serchNode(root.rhs);
        putchar('\n');
    }
    return 0;
}