急急急：关于二叉树的算法 遍历 左右子树交换 用类C语言 要详细代码

Question

（1）编写建立二叉树的算法。
（2）验证二叉树的先序、中序、后序、层次遍历算法
（3）编写二叉树的左右子树交换算法
楼下的大虾 能不能麻烦你把层次遍历写下啊 写了给你加100分啊

Answer 1

（1）编写建立二叉树的算法。
（2）验证二叉树的先序、中序、后序遍历算法
（3）编写二叉树的左右子树交换算法
上面这些都比较简单，程序如下：

#include <stdio.h>
#include <malloc.h>

typedef struct tree
{
char data;
struct tree *l;/*左儿子*/
struct tree *r;/*右儿子*/
}tr;

/*先序建立二叉树*/
tr *create(tr *t)
{
tr *k=NULL;
char ch;

scanf("%s",&ch);
if(ch=='#')
{
t=NULL;
}
else
{
t=(tr *)malloc(sizeof(tr));
t->data=ch;
t->l=create(k);
t->r=create(k);
}
return t;
}

/*先序遍历*/
void preOrder(tr *t)
{
if(t)
{
printf("%c\t",t->data);
preOrder(t->l);
preOrder(t->r);
}
}

/*中序遍历*/
void inOrder(tr *t)
{
if(t)
{
inOrder(t->l);
printf("%c\t",t->data);
inOrder(t->r);
}
}

/*后序遍历*/
void postOrder(tr *t)
{
if(t)
{
postOrder(t->l);
postOrder(t->r);
printf("%c\t",t->data);
}
}

/*左右子树交换*/
void switchChild(tr *t)
{
if(t)
{
tr *temp;

temp=t->l;
t->l=t->r;
t->r=temp;
switchChild(t->l);
switchChild(t->r);
}
}

main()
{
tr *head=NULL;

head=create(head);
printf("\n The preOrder is:");
preOrder(head);
printf("\n The inOrder is:");
inOrder(head);
printf("\n The postOrder is:");
postOrder(head);
printf("\n");
switchChild(head);
}

层次遍历也不难，但需要用到堆栈。
如果自己写堆栈的操作，也不难，但比较麻烦了。

补充：
已经写的代码，是完全符合的啊。
层次遍历，要用到堆栈，嫌麻烦就没有写了！

Answer 2

#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
char data;
struct Node * Lchild;
struct Node * Rchild;
}BitNode,*Bitree;

void CreateBitree(Bitree *bt)
{
char ch;
ch = getchar();
if(ch == '.')
*bt=NULL;
else
{
*bt = (Bitree)malloc(sizeof(BitNode));
(*bt)->data = ch;
CreateBitree(&((*bt)->Lchild));
CreateBitree(&((*bt)->Rchild));
}
}
void Visit(char ch)
{
printf("%c ",ch);
}

void PreOrder(Bitree root)
{
if(root != NULL)
{
Visit(root->data);
PreOrder(root->Lchild);
PreOrder(root->Rchild);
}
}
void InOrder(Bitree root)
{
if(root != NULL)
{
InOrder(root->Lchild);
Visit(root->data);
InOrder(root->Rchild);
}
}

void PostOrder(Bitree root)
{
if(root != NULL)
{
PostOrder(root->Lchild);
PostOrder(root->Rchild);
Visit(root->data);
}
}

void PrintTree(Bitree bt , int n)
{
int i ;
if(bt == NULL)
return ;
printf("\n");
for(i = 0 ; i < n ; i ++)
printf(" ");
Visit(bt->data);
PrintTree(bt->Lchild,n+1);
PrintTree(bt->Rchild,n+1);
}
void InOrder2(Bitree root)
{
int top;
Bitree p;
Bitree s[20];
top = 0;
p = root;
do{
while(p != NULL)
{
if(top>19)
return;
top = top + 1;
s[top] = p;
p = p->Lchild;
}
if(top != 0)
{
p = s[top];
top = top -1;
Visit(p->data);
p = p->Rchild;
}
}while(p != NULL || top != 0);
}

int main(int argc, char *argv[])
{
BitNode *root;
CreateBitree(&root);
printf("按树状结构输出二叉树：\n");
PrintTree(root,0);
printf("\n");
printf("先序遍历输出：\n");
PreOrder(root);
printf("\n");
printf("中序遍历输出： \n");
InOrder(root);
printf("\n");
printf("后序遍历输出： \n");
PostOrder(root);
printf("\n");
printf("非递归中序输出：\n");
InOrder2(root);
system("PAUSE");
return 0;
}

//这是以前有写过的代码，因为很久没接触了，也不知道是不是能调试成功，希望对朋友你有点用。