二叉树的链式存储

前序、中序、后序，区别可记忆为，访问自身节点的时机，从前往后。

定义类型

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

/* 存储空间初始分配量 */
#define MAXSIZE 100
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;

typedef char CElemType;
CElemType Nil=' '; /* 字符型以空格符为空 */
typedef struct BiTNode  /* 结点结构 */
{
    CElemType data;        /* 结点数据 */
    struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
} BiTNode, *BiTree;

创建二叉树

void CreateBiTree(BiTree *T) {
    
    CElemType ch;
    
    //获取字符
    ch = str[indexs++];
    
    //判断当前字符是否为'#'
    if (ch == '#') {
        *T = NULL;
    } else {
        //创建新的结点
        *T = (BiTree)malloc(sizeof(BiTNode));
        //是否创建成功
        if (!*T) {
            exit(OVERFLOW);
        }
        
        /* 生成根结点 */
        (*T)->data = ch;
        /* 构造左子树 */
        CreateBiTree(&(*T)->lchild);
        /* 构造右子树 */
        CreateBiTree(&(*T)->rchild);
    }
}

销毁二叉树

void DestroyBiTree(BiTree *T) {
    if(*T) {
        /* 有左孩子 */
        if ((*T)->lchild)
            DestroyBiTree(&(*T)->lchild); /* 销毁左孩子子树 */
        
        /* 有右孩子 */
        if ((*T)->rchild)
            DestroyBiTree(&(*T)->rchild); /* 销毁右孩子子树 */
        
        free(*T); /* 释放根结点 */
        
        *T = NULL; /* 空指针赋0 */
    }
}

二叉树T的深度

int BiTreeDepth(BiTree T) {
    
    int i,j;
    if (!T)
        return 0;
    
    //计算左孩子的深度
    if (T->lchild)
        i = BiTreeDepth(T->lchild);
    else
        i = 0;
    
    //计算右孩子的深度
    if (T->rchild)
        j = BiTreeDepth(T->rchild);
    else
        j = 0;
    
    //比较i和j
    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);/* 显示结点数据，可以更改为其它对结点操作 */
}