数据结构之二叉树的先序后序中序遍历比较（C语言描述）

1.二叉树的遍历是指从根节点出发，按照某种次序依次访问二叉树中的所有节点，使每个节点被且仅被访问一次。访问，小编主要是对节点信息进行了打印当然你可以根据具体情况来选择你需要的操作。遍历次序有先序遍历（前序遍历）指先遍历根节点，然后遍历左子树，最后遍历右子树；中序遍历指先遍历左子树，然后遍历根节点，最后遍历右子树；后序遍历指先遍历左子树，然后遍历右子树，最后遍历根节点；层序遍历指从上到下，从左到右，一层一层的对每个节点进行访问。
2.二叉树的结构体定义就是一个数据域，两个指针域（一个左子树指针，一个右子树指针）

3.二叉树的建立，按照先序方式进行二叉树的建立，先进行数据的录入，此处小编直接定义了一个char类型的变量，你可以根据实际情况自行定义所需要的类型的变量，当用户输入‘#’时意味着该处为空即没有节点，当用户输入其他的字符的时候先对根节点进行内存申请，然后对根节点数据域进行赋值，然后递归的建立左子树，递归的建立右子树（按照先序的顺完成树的建立）

那么此时有很多童靴就要问了，我代码这么写，那我输入的时候应该怎么在控制台输入才能得到我想要的二叉树呢。举个例子吧：在用先序输入建立二叉树的时候，如果你输入的是AB#D##C##,那么出来的二叉树是这个样子的，他的有效部分只有黑笔圈起来的那一块，你的输入顺序在图形中就是按照序号体现出来的，有效部分只有序号1，2, 4，7。因此在二叉树的建立的时候，用户应该注意自己的输入方式，避免建立的二叉树跟自己所想的二叉树不相匹配。

4.二叉树的三种遍历：先序遍历，先遍历根节点，然后遍历左子树，最后遍历右子树，代码如下

5.中序遍历，先遍历左子树，在遍历根节点，最后遍历右子树。

6.后序遍历：先遍历左子树，在遍历右子树，最后遍历根节点。

可以看出，*小编的遍历直接采用了递归算法。
其实以上三种遍历方法只是在顺序上进行了改变，对代码本身来讲并没有什么改动
7.*整体代码及测试数据运行结果

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
 
#define MAXSIZE 100
 
//二叉树数据结构定义
typedef struct BiTreeNode
{
    char data;
    struct BiTreeNode *left;
    struct BiTreeNode *right;
}BiTreeNode,*BiTree;
 
//二叉树的建立--按照先序方式建立--插入
void CreateBiTree(BiTree *T)
{
    char val;
    scanf("%c",&val);
 
    if(val == '#')
        *T = NULL;  				//null表示为空枝
 
    else
    {
        *T = (BiTree)malloc(sizeof(BiTreeNode));		//节点申请内存 
        (*T)->data = val;								//节点数据与进行赋值 
        CreateBiTree(&(*T)->left);						//递归创建左子树 
        CreateBiTree(&(*T)->right);						//递归创建右子树
    }
}
 
 
//先序遍历  根左右
void PreOrderTravel(BiTree T)
{
    if(T==NULL)
        return;
    printf("%c ",T->data);
    PreOrderTravel(T->left);
    PreOrderTravel(T->right);
}
 
//中序遍历 左根右
void InOrderTravel(BiTree T)
{
    if(T==NULL)
        return;
    InOrderTravel(T->left);
    printf("%c ",T->data);
    InOrderTravel(T->right);
}
 
//后序遍历 左右根
void TailOrderTravel(BiTree T)
{
    if(T==NULL)
        return;
    TailOrderTravel(T->left);
    TailOrderTravel(T->right);
    printf("%c ",T->data);
}

int main()
{
    BiTree T;
    T = (BiTree)malloc(sizeof(BiTreeNode));

//	ABDH#K###E##CFI###G#J## 
    printf("请给二叉树按照先序方式依次输入结点的值(空结点为#):\n");
    CreateBiTree(&T);
 
 
    printf("先序方式遍历结果：\n");
    PreOrderTravel(T);
    printf("\n");
 
    printf("中序方式遍历结果：\n");
    InOrderTravel(T);
    printf("\n");
 
    printf("后序方式遍历结果：\n");
    TailOrderTravel(T);
    printf("\n");
    system("color c");
    
    return 0;
}