[資料結構] BST 的 construct & traversal＠Morris' Blog

2012-11-29 21:11:28| 人氣2,191| 回應0 | 上一篇 | 下一篇

[資料結構] BST 的 construct & traversal

Problem :

BST為二元樹的一種，符合下面兩個條件 :

1. 所有在左子樹之 Node 之值一定不大於 Root 之值

2. 所有在右子樹之 Node 之值一定不小於 Root 之值

輸入數值為一串整數，數字之間以空白隔開

請將輸入的 DATA 依序 Insert 以建立一個 BST

並依序輸出其 Inorder，Preorder，Postorder以及node總數

(請參考下面所附的測資及sample檔)

Sample input:

50 30 98 24 45 52 5 28 60

Sample output:

5 24 28 30 45 50 52 60 98

50 30 24 5 28 45 98 52 60

5 28 24 45 30 60 52 98 50

繳交期限:

12/11/2012 23:59

超過期限者每多一天扣作業分數10%

超過12/15/2012 23:59後繳交一律不給分。

繳交格式:

請以C/C++完成

一律將程式碼.c/.cpp檔案壓縮為.rar/.zip/.7z上傳至FTP

繳交檔案格式為

學號_HW3_Ver1.rar

ex:101522054_HW3_Ver1.rar

(在期限內如果想再重新上傳檔案則命名為ver2 ver3以此類推

助教改作業時會以最後一版為準)

這次程式沒有很難，但是我不確定我有沒有寫錯。

demo 結果如上

#include <stdio.h>
#include <stdlib.h>
#include <sstream>
#include <queue>
using namespace std;
struct BTnode{
    BTnode *l, *r;
    int num;
};
void insBT(BTnode **root, int num) {
    if((*root) == NULL) {
        (*root) = new BTnode;
        (*root)->num = num;
        (*root)->l = (*root)-> r = NULL;
        return;
    }
    BTnode *idx, *p;
    idx = (*root);
    while(idx) {
        if(idx->num > num) {
            if(idx->l == NULL) {
                p = new BTnode;
                idx->l = p;
                p->num = num;
                p->l = p->r = NULL;
                return;
            }
            idx = idx->l;
        } else {
            if(idx->r == NULL) {
                p = new BTnode;
                idx->r = p;
                p->num = num;
                p->l = p->r = NULL;
                return;
            }
            idx = idx->r;
        }
    }
}
void preorder(BTnode *p) {
    if(p == NULL)   return;
    printf("%-5d", p->num);
    preorder(p->l);
    preorder(p->r);
}
void inorder(BTnode *p) {
    if(p == NULL)   return;
    inorder(p->l);
    printf("%-5d", p->num);
    inorder(p->r);
}
void postorder(BTnode *p) {
    if(p == NULL)   return;
    postorder(p->l);
    postorder(p->r);
    printf("%-5d", p->num);
}
void levelorder(BTnode *p) {
    queue<BTnode*> Q;
    Q.push(p);
    while(!Q.empty()) {
        p = Q.front();
        Q.pop();
        printf("%-5d", p->num);
        if(p->l)
            Q.push(p->l);
        if(p->r)
            Q.push(p->r);
    }
}
int cntNode(BTnode *p) {
    if(p == NULL)   return 0;
    return cntNode(p->l)+cntNode(p->r)+1;
}
void freeBT(BTnode *p) {
    if(p == NULL)   return;
    freeBT(p->l);
    freeBT(p->r);
    delete p;
}
int main() {
    char line[1024];
    BTnode *root = NULL;
    int num;
    printf("輸入數列用空白隔開：");
    gets(line);
    stringstream sin(line);
    while(sin >> num) {
        insBT(&root, num);
    }
    printf("inorder:    ");
    inorder(root);
    puts("");
    printf("preorder:   ");
    preorder(root);
    puts("");
    printf("postorder: ");
    postorder(root);
    puts("");
    printf("levelorder: ");
    levelorder(root);
    puts("");
    printf("Node總數: %d\n", cntNode(root));
    freeBT(root);
    system("pause");
    return 0;
}