二叉排序树

二叉排序树

二叉排序树题目

题目描述：
    输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。
输入：
    输入第一行包括一个整数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
****************************************************************/

后记
 
算法导论上二叉排序树应该是最简单最容易理解的，这里记录一下，当数据结构复习吧