该楼层疑似违规已被系统折叠隐藏此楼查看此楼
#include
#include
#include
#include
#define OVERFLOW -1
struct BTNode{
char data;
struct BTNode *lchild,*rchild;
};
struct BTNode *CreatBiTree(){ //先序建立二叉树
struct BTNode *T;
char ch;
scanf("%c",&ch);
if (ch==' ')
T=NULL;
else{
if(!(T=(struct BTNode*)malloc(sizeof(struct BTNode))))
exit(OVERFLOW);
T->data =ch;
T->lchild = CreatBiTree();
T->rchild = CreatBiTree();
}
return T;
}
PreOrderTraverse(struct BTNode *T){ //先序遍历二叉树
struct BTNode * A[30]; //定义一个数组存二叉树类型的指针
int i=0;
if(T!=NULL){ //先在数组内存上指向T的根节点的指针 将T赋值为T的左子树
A[i]=T;
printf("%c",T->data);i++;
T=T->lchild;
}
while(i>=0){ //数组不为空的时候
if(T!=NULL){ //树不空，则输出此根节点存的数据 将T赋值为T的左子树
A[i]=T;
printf("%c",T->data);i++;
T=T->lchild ;
}
else{
printf("/"); //树为空 则输出表示空的字符“/”
if(i>0){ //判断下标是否越界 将T赋值为T的根节点的右子树
i--;
T=A[i]->rchild;
}
else break;
}
}
}
InOrderTraverse(struct BTNode *T){
struct BTNode * A[30];
int i=0;
if(T!=NULL){
A[i]=T;i++;
T=T->lchild;
}
while(i>=0){
if(T!=NULL){
A[i]=T;i++;
T=T->lchild ;
}
else{
printf("/");
if(i>0){
printf("%c",A[i-1]->data);
i--;
T=A[i]->rchild;
}
else break;
}
}
}
PostOrderTraverse(struct BTNode *T){
struct BTNode * A[30]; //定义一个数组存二叉树类型的指针
int B[30]; //定义了一个数组 用于保存标识根节点的状态的标识符 “0”表示此根节点还没被访问过子树，1表示已经访问过左子树，2表示已经访问过右子树
int i=0;
if(T!=NULL){ //初始化数组 将树的根节点存入数组 标识符初始化为 “0”
A[i]=T;B[i]=0;i++;
}
while(i>=0){
if(T==NULL){ //树为空时 输出表示空的字符 返回上一层的根节点
printf("/");
T=A[i-2];i--;
}
else{
if(i>0){
switch (B[i-1]){
case 0: //为“0”时 访问左子树 并将根节点的标识符设为“1”，将其左子树的根节点存入数组，将左子树的标识符设为“0”
A[i]=T->lchild;B[i]=0;
B[i-1]=1;i++;
T=T->lchild;
break;
case 1: //为“1”时 访问右子树 并将根节点的标识符设为“2”，将其右子树的根节点存入数组，将右子树的标识符设为“0”
A[i]=T->rchild;B[i]=0;
B[i-1]=2;i++;
T=T->rchild;
break;
case 2: //为“2”时 输出根节点的数据 并返回上一层的根节点
printf("%c",A[i-1]->data);
T=A[i-2];i--;
}
}
else break;
}
}
}
void main(){
struct BTNode *T;
printf("请按先序输入二叉树值，空用空格代替\n");
T=CreatBiTree();
printf("先序遍历二叉树得到的结果为：\n");
PreOrderTraverse(T);
printf("\n中序遍历二叉树得到的结果为：\n");
InOrderTraverse(T);
printf("\n后序遍历二叉树得到的结果为：\n");
PostOrderTraverse(T);
getch();
}
c语言非递归方式建立二叉链表 非递归算法遍历二叉树 改成用链表的怎么破？链表不熟智商拙计...
