链式二叉树的前中后续遍历

前言

三种遍历

链式二叉树又称二叉链表，遍历有三种，分别是前序(先序)，中序，后序。

定义二叉树的存储结构为链式存储

1 typedef struct BiNode{
2     int data;
3     BiNode *lchild,*rchild;   //左孩子和右孩子
5 }BiNode;
6 typedef struct BiNode* BiTree;

我们往往在创建之前要先初始化一下

/*初始化并建立二叉树*/
int index=0;
void CreateBiTree(BiTree* T,char data[]){
    *T =NULL;   //初始化为空
    char ch;
    if(index<strlen(data)){
        ch = data[index++];
    }else{
        return;
    }
    if(ch =='#')      //此节点为空
        *T =NULL;
    else{
        *T = (BiTree)malloc(sizeof(BiNode));
        if(!*T)
            exit(0);
        (*T)->data=ch;  //生成根节点
        CreateBiTree(&(*T)->lchild,data);
        CreateBiTree(&(*T)->rchild,data);        
    }
}

先序

先序：
1.访问根结点

2.访问左子树

3.访问右子树

总结三个字：中左右

/*先序遍历*/
void PreOrderTraverse(BiTree T){
    if(T ==NULL)
        return;
    printf("%c ",T->data);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}

中序

中序：1.访问左子树

2.访问根结点

3.访问右子树

总结三个字：左中右

/*中序遍历*/
void InOrderTraverse(BiTree T){
    if(T ==NULL)
        return;
    InOrderTraverse(T->lchild);
    printf("%c ",T->data);
    InOrderTraverse(T->rchild);
}

后序

后序：
1.访问左子树
2.访问右子树
3.访问根

总结三个字：左右中

/*后序遍历*/
void PostOrderTraverse(BiTree T){
    if(T ==NULL)
        return;
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c ",T->data);
}

对二叉树进行一些其他的操作

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct BiNode{
    int data;
    BiNode *lchild,*rchild;

}BiNode;
typedef struct BiNode* BiTree;

/*初始化并建立二叉树*/
int index=0;
void CreateBiTree(BiTree* T,char data[]){
    *T =NULL;   //初始化为空
    char ch;
    if(index<strlen(data)){
        ch = data[index++];
    }else{
        return;
    }
    if(ch =='#')      //此节点为空
        *T =NULL;
    else{
        *T = (BiTree)malloc(sizeof(BiNode));
        if(!*T)
            exit(0);
        (*T)->data=ch;  //生成根节点
        CreateBiTree(&(*T)->lchild,data);
        CreateBiTree(&(*T)->rchild,data);        
    }
}

/*判断是否为空二叉树*/
int BiTreeEmpty(BiTree T){
    if(T){
        return 0;
    }
    return 1;
}

/* 初始条件: 二叉树T存在。操作结果: 返回T的根 */
char Root(BiTree T){
    if(BiTreeEmpty(T))
        return NULL;
    else
        return T->data;
}

/* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */
int BiTreeDepth(BiTree T){
    int i,j;
    //没有根节点
    if(!T){
        return 0;
    }
    if(T->lchild){
        i = BiTreeDepth(T->lchild);
    }else{
        j=0;
    }
    if (T->rchild){
        j = BiTreeDepth(T->rchild);
    }else{
        i=0;
    }
    return i>j ?i+1:j+1;
}

/*先序遍历*/
void PreOrderTraverse(BiTree T){
    if(T ==NULL)
        return;
    printf("%c ",T->data);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}

/*中序遍历*/
void InOrderTraverse(BiTree T){
    if(T ==NULL)
        return;
    InOrderTraverse(T->lchild);
    printf("%c ",T->data);
    InOrderTraverse(T->rchild);
}
/*后序遍历*/
void PostOrderTraverse(BiTree T){
    if(T ==NULL)
        return;
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c ",T->data);
}

/* 初始条件: 二叉树T存在。操作结果: 销毁二叉树T */
void DestroyBiTree(BiTree *T){
    if(*T){
        if((*T)->lchild){   //有左孩子
            DestroyBiTree(&(*T)->lchild);   //销毁左孩子子树
        }
        if((*T)->rchild){
            DestroyBiTree(&(*T)->rchild);
        }
        free(*T);  /* 释放根结点 */
        *T = NULL;  //指向0
    }
}

int main(){
    BiTree tree;
    int i;
    char data[] = "ABDH#K###E##CFI###G#J##";
    //InitBiTree(&tree);
    CreateBiTree(&tree,data);
    printf("树是否为空：(1 或 0)：%d\n",BiTreeEmpty(tree));
    printf("树的深度为：%d\n",BiTreeDepth(tree));
    printf("此时树的头结点为：%c\n",Root(tree));

    printf("先序遍历：");
    PreOrderTraverse(tree);
    printf("\n");

    printf("中序遍历：");
    InOrderTraverse(tree);
    printf("\n");

    printf("后序遍历：");
    PostOrderTraverse(tree);
    printf("\n");

    printf("销毁二叉树\n");
    DestroyBiTree(&tree);
    printf("树是否为空：(1 或 0)：%d\n",BiTreeEmpty(tree));
    return 0;
}