二叉排序樹

二叉排序樹題目

題目描述：
    輸入一系列整數，建立二叉排序數，並進行前序，中序，後序遍歷。
輸入：
    輸入第一行包括一個整數n(1<=n<=100)。
    接下來的一行包括n個整數。
輸出：
    可能有多組測試數據，對於每組數據，將題目所給數據建立一個二叉排序樹，並對二叉排序樹進行前序、中序和後序遍歷。
    每種遍歷結果輸出一行。每行最後一個數據之後有一個空格。
樣例輸入：
5
1 6 5 9 8
樣例輸出：
1 6 5 9 8
1 5 6 8 9
5 8 9 6 1
提示：
輸入中可能有重復元素，但是輸出的二叉樹遍歷序列中重復元素不用輸出。

AC代碼

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define N 101
 
struct btree
{
    struct btree *lchild, *rchild;
    int data;
};
 
struct stack
{
    struct btree* arr[N];
    int top;
};
 
struct btree* create_sortree(struct btree* t, int d);
void pre_traverse(struct btree *t);
void order_traverse(struct btree *t);
void post_traverse(struct btree *t);
void clean_tree(struct btree *t);
 
int main()
{
    int i, n, d;
    struct btree *t;
    while (scanf("%d", &n) != EOF) {
        //接收客戶端輸入，構建二叉排序樹
        for (i = 0, t = NULL; i < n; i ++) {
            scanf("%d", &d);
            t = create_sortree(t, d);
        }
       
        // 前序遍歷
        pre_traverse(t);
 
        // 中序遍歷
        order_traverse(t);
 
        // 後序遍歷
        post_traverse(t);
 
        // 清理
        clean_tree(t);
    }
 
    return 0;
}
 
 
struct btree* create_sortree(struct btree *t, int d)
{
    if (t == NULL) {
        t = (struct btree*)malloc(sizeof(struct btree) * 1);
        t->data = d;
        t->lchild = NULL;
        t->rchild = NULL;
    }else if(t->data > d) {  // 插入到左子樹
        t->lchild = create_sortree(t->lchild, d);
    }else if(t->data < d) { // 插入到右子樹
        t->rchild = create_sortree(t->rchild, d);
    }else {
        // 相同元素不進行任何操作
    }
 
    return t;
}
 
void pre_traverse(struct btree *t)
{
    struct btree *p = t;
    struct stack *s = (struct stack*)malloc(sizeof(struct stack) * 1);
    s->top = 0;
 
    while (s->top || p) {
        if (p) {
            printf("%d ", p->data);
            s->arr[s->top ++] = p;
            p = p->lchild;
        }else {
            p = s->arr[-- s->top];
            p = p->rchild;
        }
    }
 
    printf("\n");
}
 
void order_traverse(struct btree *t)
{
    struct btree *p = t;
    struct stack *s = (struct stack*)malloc(sizeof(struct stack) * 1);
    s->top = 0;
 
    while (s->top || p) {
        if (p) {
            s->arr[s->top ++] = p;
            p = p->lchild;
        }else {
            p = s->arr[-- s->top];
            printf("%d ", p->data);
            p = p->rchild;
        }
    }
 
    printf("\n");
}
 
void post_traverse(struct btree *t)
{
    struct btree *p, *pre;
    struct stack *s = (struct stack*)malloc(sizeof(struct stack) * 1);
    s->top = 0;
    pre = NULL;
    p = t;
 
    while (p || s->top) {
        if (p) {
            s->arr[s->top ++] = p;
            p = p->lchild;
        }else {
            p = s->arr[-- s->top];
            if (p->rchild == NULL || p->rchild == pre) {
                printf("%d ", p->data);
                pre = p;
                p = NULL;
            }else {
                s->arr[s->top ++] = p;
                p = p->rchild;
            }
        }
    }
 
    printf("\n");
}
 
void clean_tree(struct btree *t)
{
    if (t) {
        clean_tree(t->lchild);
        clean_tree(t->rchild);
        free(t);
    }
}
/**************************************************************
    Problem: 1201
    User: wangzhengyi
    Language: C
    Result: Accepted
    Time:70 ms
    Memory:3284 kb
****************************************************************/

後記
 
算法導論上二叉排序樹應該是最簡單最容易理解的，這裡記錄一下，當數據結構復習吧