题目描述

输入一系列整数，利用所给数据建立一个二叉搜索树，并输出其前序、中序和后序遍历序列。

输入格式

第一行一个整数 n，表示输入整数数量。

第二行包含 n 个整数。

输出格式

共三行，第一行输出前序遍历序列，第二行输出中序遍历序列，第三行输出后序遍历序列。

输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。

数据范围

1≤n≤100,
输入元素取值范围 [1,1000]。

输入样例：

5
1 6 5 9 8

输出样例：

1 6 5 9 8
1 5 6 8 9
5 8 9 6 1

注意：

如果里面代码有不懂的，可以去查看我的分享和相应问题的题解，写的比较详细

C 代码(使用了C++引用)

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

typedef struct BiNode {
    int data;
    struct BiNode* lchild, * rchild;
}BiNode, * BSTree;

typedef struct LinkNode {
    BiNode* data;//存放的数据为树结点
    struct LinkNode* next;
}LinkNode, * LinkStack;

//初始化链栈
void initStack(LinkStack& S) {
    S = (LinkStack)malloc(sizeof(LinkNode));
    S->next = NULL;
}

//判断栈是否为空
bool EmptyStack(LinkStack S) {
    if (S->next) {
        return false;
    }
    return true;
}

//元素进栈
void Push(LinkStack& S, BSTree p) {
    LinkNode* node = (LinkNode*)malloc(sizeof(LinkNode));
    //头插法
    node->data = p;
    node->next = S->next;
    S->next = node;
}

//元素出栈
void Pop(LinkStack& S, BSTree& p) {
    if (EmptyStack(S))
        return;
    LinkNode* tempNode = (LinkNode*)malloc(sizeof(LinkNode));
    tempNode = S->next;
    p = tempNode->data;
    S->next = tempNode->next;
    free(tempNode);
}

//查看栈顶元素(非出栈)
void GetTop(LinkStack S, BSTree& p) {
    if (EmptyStack(S))
        return;
    p = S->next->data;
}

//二叉排序树的结点插入
void BSTInsert(BSTree& T, int data) {
    if (!T) {//如果原树为空，新插入的结点直接当做根结点
        T = (BSTree)calloc(1, sizeof(BiNode));
        T->data = data;
        return;
    }
    else if (data == T->data) {//相同元素插入失败
        return;
    }
    else if (data < T->data) {
        BSTInsert(T->lchild, data);
    }
    else {
        BSTInsert(T->rchild, data);
    }
}

//创建二叉排序树
void CreatBST(BSTree& T, int* arr, int len) {
    T = NULL;
    int i = 0;
    while (len--) {
        BSTInsert(T, arr[i]);
        i++;
    }
}

//先序遍历非递归法
void PreOrder2(BSTree T) {
    LinkStack S;
    initStack(S);
    BSTree p = T;
    while (p || !EmptyStack(S))
    {
        if (p)
        {
            printf("%d ", p->data);
            Push(S, p);
            p = p->lchild;
        }
        else
        {
            Pop(S, p);
            p = p->rchild;
        }
    }
}

//先序遍历递归法
void PreOrder(BSTree T) {
    if (T) {
        printf("%d ", T->data);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

//中序遍历非递归法
void InOrder2(BSTree T) {
    LinkStack S;
    initStack(S);
    BSTree p = T;
    while (p || !EmptyStack(S)) {
        if (p) {
            Push(S, p);
            p = p->lchild;
        }
        else {
            Pop(S, p);
            printf("%d ", p->data);
            p = p->rchild;
        }
    }
}

//中序遍历递归法
void InOrder(BSTree T) {
    if (T) {
        InOrder(T->lchild);
        printf("%d ", T->data);
        InOrder(T->rchild);
    }
}

//后序遍历非递归法
void PostOrder2(BSTree T) {
    LinkStack S;
    initStack(S);
    BiNode* pre = NULL;//标记刚刚访问过的结点
    BSTree p = T;
    while (p || !EmptyStack(S))
    {
        if (p)
        {
            Push(S, p);
            p = p->lchild;
        }
        else
        {
            //查看当前栈顶元素
            GetTop(S, p);
            if (p->rchild && p->rchild != pre)//右子树存在，且没被访问过
                p = p->rchild;
            else
            {
                Pop(S, p);
                printf("%d ", p->data);
                pre = p;
                p = NULL;
            }
        }
    }
}

//后序遍历递归法
void PostOrder(BSTree T) {
    if (T) {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        printf("%d ", T->data);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    int* arr = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    BSTree root;
    CreatBST(root, arr, n);
    //PreOrder(root);//递归法
    PreOrder2(root);
    printf("\n");
    //InOrder(root);//递归法
    InOrder2(root);//非递归法
    printf("\n");
    //PostOrder(root);//递归法
    PostOrder2(root);//非递归法
    free(arr);
    return 0;
}