题目描述
输入一系列整数,利用所给数据建立一个二叉搜索树,并输出其前序、中序和后序遍历序列。
输入格式
第一行一个整数 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;
}