二叉树的遍历_C

基本 *** 作：
- 定义结构体：
- 创建二叉树：
- 前序遍历：
- 中序遍历：
- 后序遍历：
- 测试：
- - 测试结果：
  - 创建的二叉树图示：
- 前序遍历图解分析：

基本 *** 作：

void CreatTree(TreeNode **T,char *data,int *index);    //创建二叉树
void PreOrder(TreeNode *T);     //前序遍历结点
void InOrder(TreeNode *T);     //中序遍历结点
void PostOrder(TreeNode *T);     //后序遍历结点

定义结构体：

#include 
#include 

typedef struct TreeNode
{
    char val;		//存储数据
    struct TreeNode *lchild;	//左孩子
    struct TreeNode *rchild;	//右孩子
}TreeNode;

创建二叉树：

void CreatTree(TreeNode **T,char *data,int *index)
{
    char ch;
    ch = data[*index];
    *index += 1;
    if(ch == '#')
    {
        //此时为空结点
        *T = NULL;
    }
    else
    {
        //非空结点
        *T = (TreeNode *)malloc(sizeof(TreeNode));
        (*T)->val = ch;	//存储传入的数据
        //创建左子树
        CreatTree(&((*T)->lchild),data,index);
        //创建右子树
        CreatTree(&((*T)->rchild),data,index);
    }
}

前序遍历：

//前序遍历：根-左-右
//      先访问根结点，
//      再判断是否存在左子树，若存在则递归前序遍历
//      若不存在左子树时则判断是否存在右子树，若存在则递归前序遍历
void PreOrder(TreeNode *T)
{
    if(T == NULL)
        return ;
    
    printf("%c\t",T->val);
    PreOrder(T->lchild);
    PreOrder(T->rchild);
}

中序遍历：

//中序遍历：左-根-右
void InOrder(TreeNode *T)
{
    if(T == NULL)
        return ;

    InOrder(T->lchild);
    printf("%c\t",T->val); 
    InOrder(T->rchild);
}

后序遍历：

//后序遍历：左-右-根
void PostOrder(TreeNode *T)
{
    if(T == NULL)
        return ;
    
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    printf("%c\t",T->val);
}

测试：

void main()
{
    TreeNode *tree;
    int index = 0;	//辅助利用data数组创建二叉树
    char *data = "ABD##E##CF##G##";
    printf("创建二叉树：\n");
    CreatTree(&tree,data,&index);
    printf("先序遍历：\n");
    PreOrder(tree);
    printf("\n");
    printf("中序遍历：\n");
    InOrder(tree);
    printf("\n");
    printf("后序遍历：\n");
    PostOrder(tree);
    printf("\n");

    system("pause");
    return ;
}