编写程序 实现对建立的二叉树进行后序遍历，并输出遍历结果。二叉树用二叉链表存储结构存储

(1)、二叉树的链表形式的建立；

(2)、用递归方式写出二叉树的先序、中序、后序三种遍历方法。

(3)、用非递归方式写出二叉禅卖派树的中序遍历程序。

#include<stdio.h>贺贺

#define MAXSIZE 100

typedef struct BiTNode

{

char data

struct BiTNode *lchild, *rchild

}BiTNode,*BiTree

BiTree CreateBiTree()

{

BiTree T

char ch=getchar()

if(ch=='#')

T=NULL

else

{

T=(BiTNode *)malloc(sizeof(BiTNode))

T->data=ch

T->lchild=CreateBiTree()

T->rchild=CreateBiTree()

}

return T

} //递归生成二叉树，用#代表空子树

void preorder(BiTree t)

{

if(t)

{

printf("%c ",t->data)

preorder(t->lchild)

preorder(t->rchild)

}

} //递归先序遍历

void Inorder(BiTree T)

{

if(T)

{

Inorder(T->lchild)

printf("%c ",T->data)

Inorder(T->rchild)

}

}

//递归中序配茄遍历

void postorder(BiTree t)

{

if(t)

{

preorder(t->lchild)

preorder(t->rchild)

printf("%c ",t->data)

}

}//递归后序遍历

void NInorder(BiTree T)

{

BiTree stack[MAXSIZE]

BiTree p=T

int top=-1

while(p||top!=-1)

{

if(p)

{

top++

stack[top]=p

p=p->lchild

}

else

{

p=stack[top]

top--

printf("%c ",p->data)

p=p->rchild

}

}

} //非递归中序遍历

main()

{

BiTree T

printf("please input the tree: ")

T=CreateBiTree()

printf("\n")

getch()

printf("the tree after preorder is: ")

preorder(T)

printf("\n")

getch()

printf("the tree after ineorder is: ")

Inorder(T)

printf("\n")

getch()

printf("the tree after postorder is: ")

postorder(T)

printf("\n")

getch()

printf("the tree after noinorder is: ")

NInorder(T)

printf("\n")

getch()

}

由于我好久没有使用 C 语言编写树形结构的遍历程序了，但绝知是可以给你提供一个思路：递归的方法。先序即：根茄数、左、右；中序即：左、根、右；后序即：左、右、根。现在这个算法在 C 语言版的数据结构教材上都有现成的代码，只需要稍加改动，把书上并纳消的数据类型修改为你自己需要的数据类型即可。

/*二叉树*/

typedef struct BNode{

DataType data

struct BNode *left,*right

}* LinkTree

/*建立*/

int LinkTreeCreate(LinkTree *T)

{

DataType d

scanf("%t",&d)

if (d == 0)

*T = NULL

else

{

if ((*T = malloc(sizeof(struct BNode))) == NULL)

return -1

(*T)->森枣data = d

if (LinkTreeCreate(&(*T)->left) == -1)

return -1

if (LinkTreeCreate(&(*T)->right) == -1)

return -1

}

return 0

}

/*循环遍历算法*/

void LinkTreeTraverse(LinkTree T)

{

SeqStack S

struct PNode p

S.bottom = malloc(STACKSIZE*sizeof(struct PNode))

S.stacksize = STACKSIZE

S.top = 0

p.ptr = T

p.flag = FALSE

while (S.top >= 0)

if (p.ptr != NULL)

{

SeqStackPush(&S,p)

p.ptr = p.ptr->left

p.flag = FALSE

}

else

{

if (SeqStackPop(&S,&p) == -1)

break

if (p.flag == FALSE)

{

p.flag = TRUE

SeqStackPush(&S,p)

p.ptr = p.ptr->right

p.flag = TRUE

}

else

{

printf("%t",p.ptr->缺大data)

p.ptr = NULL

}

}

}

/*递归遍历算法*/

void LinkTreeTraverse(LinkTree T)//先序

{

if (T != NULL)

{

printf("%t",T->data)

LinkTreeTraverse(T->left)

LinkTreeTraverse(T->right)

}

}

void LinkTreeTraverse(LinkTree T)//中序

{

if (T != NULL)

{

LinkTreeTraverse(T->left)

printf("%t",T->data)

LinkTreeTraverse(T->right)

}

}

void LinkTreeTraverse(LinkTree T)//后序

{

if (T != NULL)

{

LinkTreeTraverse(T->left)

LinkTreeTraverse(T->right)

printf("%t",T->伏春竖data)

}

}

/*令DataType为int，则%t为%d，以此类推*/

---