二叉树的前序中序后序遍历（C语言描述）

此二叉树前序输入为

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
		

	

	
		*/