此二叉树前序输入为
AB#D##C##
前序输出为 ABDC
中序输出为 BDAC
后序输出为 DBCA
一、定义二叉树的存储结构
一个二叉树有一个数据域和两个指针域
代码如下
typedef struct BiTNode
{
char data;
struct BiTNode *lchild;
struct BiTNode *rchild;
}BiTNode,*BiTree;
二、创建一个二叉树（前序递归方法创建二叉树）
void CreateBiTree(BiTree *T)
{
char x;
scanf("%c",&x);
if(x=='#')
*T=NULL;
else
{
*T=(BiTree)malloc(sizeof(BiTNode));
(*T)->data=x;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
三、前序遍历一个二叉树 依次访问二叉树 根结点->左孩子->右孩子
void PreOrderTraverse(BiTree T)
{
if(T==NULL)
return;
printf("%c ",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
四、中序遍历二叉树 依次访问二叉树 左孩子->根结点->右孩子
void MiOrderTraverse(BiTree T)
{
if(T==NULL)
return;
MiOrderTraverse(T->lchild);
printf("%c ",T->data);
MiOrderTraverse(T->rchild);
}
}五、后序遍历二叉树
依次访问二叉树 左孩子->右孩子->根结点
void BackOrderTraverse(BiTree T)
{
if(T==NULL)
return;
BackOrderTraverse(T->lchild);
BackOrderTraverse(T->rchild);
printf("%c ",T->data);
}
六、最后是主函数，输出前中后序遍历结果
int main()
{
printf("先序方式输入一棵二叉树：");
BiTree T;
CreateBiTree(&T);
printf("先序方式遍历结果：\n");
PreOrderTraverse(T);
printf("\n");
printf("中序方式遍历结果：\n");
MiOrderTraverse(T);
printf("\n");
printf("后序方式遍历结果：\n");
BackOrderTraverse(T);
printf("\n");
return 0;
}
最后完整代码如下 #include<stdio.h>
#include<stdlib.h>
typedef struct BiTNode
{
char data;
struct BiTNode *lchild;
struct BiTNode *rchild;
}BiTNode,*BiTree;
void CreateBiTree(BiTree *T)
{
char x;
scanf("%c",&x);
if(x=='#')
*T=NULL;
else
{
*T=(BiTree)malloc(sizeof(BiTNode));
(*T)->data=x;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
void PreOrderTraverse(BiTree T)
{
if(T==NULL)
return;
printf("%c ",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
void MiOrderTraverse(BiTree T)
{
if(T==NULL)
return;
MiOrderTraverse(T->lchild);
printf("%c ",T->data);
MiOrderTraverse(T->rchild);
}
void BackOrderTraverse(BiTree T)
{
if(T==NULL)
return;
BackOrderTraverse(T->lchild);
BackOrderTraverse(T->rchild);
printf("%c ",T->data);
}
int main()
{
printf("先序方式输入一棵二叉树：");
BiTree T;
CreateBiTree(&T);
printf("先序方式遍历结果：\n");
PreOrderTraverse(T);
printf("\n");
printf("中序方式遍历结果：\n");
MiOrderTraverse(T);
printf("\n");
printf("后序方式遍历结果：\n");
BackOrderTraverse(T);
printf("\n");
return 0;
}
/*
AB#D##C##
前序输出为 ABDC
中序输出为 BDAC
后序输出为 DBCA
*/
全部评论
(0) 回帖