解题思路:
注意事项:
参考代码:
#include<bits/stdc++.h>
#include< bits/stdc++.h >
#define MAX 101
typedef struct BiTNode{
char data;
struct BiTNode *LeftChild,*RightChild;
}*Bitree,BiTree;
typedef struct Stack_{
Bitree elem[MAX];/*存放二叉树结点指针*/
int top;
}*Stack,STACK;
/*---------------------------------------------*/
/*声明栈操作*/
void init_(Stack s);/*初始化栈*/
void push_(Stack s,Bitree T);
void pop_(Stack s,Bitree *T);/*返回结点指针，所以Bitree *，指向指针的指针*/
int getTop(Stack s,Bitree *T);/*返回结点指针，所以Bitree *，指向指针的指针*/
/*getTop返回值为int是因为下面出现这样代码while(getTop(&S,&p)&&p)需要有返回值*/
int stackempty(Stack s);/*判断栈空*/
/*---------------------------------------------*/
/*声明二叉树操作*/
void CreatBitree(Bitree *T); /*二叉树的创建*//*返回结点指针，所以Bitree *，指向指针的指针*/
void PreOrderTraverse(Bitree T);/*先序遍历二叉树*/
void InOrderTraverse1(Bitree T);/*第一种中序遍历二叉树*/
void InOrderTraverse2(Bitree T);/*第二种遍历二叉树*/
/*---------------------------------------------*/
int main()
{
Bitree T;/*建立二叉树头结点指针*/
CreatBitree(&T);/*T为指针，&T为它的地址，到了函数里面(*T)才代表这里的T*/
PreOrderTraverse(T);
printf("\n");/*先序遍历完后换行*/
InOrderTraverse1(T);
InOrderTraverse2(T);
return 0;
}
/*======================栈操作声明=================*/
void init_(Stack s)/*初始化栈*/
{
s->top=0;
}
/*----------------------------------------*/
void push_(Stack s,Bitree T)
{
s->elem[s->top++]=T;
}
/*----------------------------------------*/
void pop_(Stack s,Bitree *T)
{
(*T)=s->elem[--s->top];
}
/*----------------------------------------*/
int stackempty(Stack s)/*判断栈空*/
{
if(s->top==0)
return 1;
else
return 0;
}
/*----------------------------------------*/
int getTop(Stack s,Bitree *T)/*返回结点指针*/
{
(*T)=s->elem[s->top-1];
return 1;
}
/*=================================================*/
/*====================二叉树操作===================*/
void CreatBitree(Bitree *T) /*二叉树的创建*/
{
char ch;
scanf("%c",&ch);
if(ch==' ')/*如果输入为空格，那么该指针T指向节点为空不存在，所以T=BULL*/
(*T)=NULL;
else
{
/*否则为该节点分配空间*/
(*T)=(Bitree)malloc(sizeof(BiTree));
(*T)->data=ch;/*结点赋值*/
/*递归创建T的左孩子*/
CreatBitree(&(*T)->LeftChild);
/*递归创建T的右孩子*/
CreatBitree(&(*T)->RightChild);
}
return ;
}
/*-----------------------------------------*/
void PreOrderTraverse(Bitree T)/*先序遍历二叉树*/
{
if(T)
{
printf("%c ",T->data);
PreOrderTraverse(T->LeftChild);
PreOrderTraverse(T->RightChild);
}
}
/*-----------------------------------------*/
void InOrderTraverse1(Bitree T)/*第一种中序遍历二叉树*/
{
STACK S;
init_(&S);
while(T||!stackempty(&S))
{
if(T)
{
push_(&S,T);
T=T->LeftChild;
}
else
{
pop_(&S,&T);
printf("%c ",T->data);
T=T->RightChild;
}
}
/*输出完换行*/
printf("\n");
return ;
}
/*-----------------------------------------*/
void InOrderTraverse2(Bitree T)/*第二种遍历二叉树*/
{
STACK S;
Bitree p;
init_(&S);
push_(&S,T);
while(!stackempty(&S))
{
while(getTop(&S,&p)&&p)
push_(&S,p->LeftChild);
pop_(&S,&p);
if(!stackempty(&S))
{
pop_(&S,&p);
printf("%c ",p->data);
push_(&S,p->RightChild);
}
}
}
0.0分
0 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复