二叉树链式存储

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

一、二叉树构造

int indexs = 1;
typedef char String[24]; /*  0号单元存放串的长度 */
String str;
Status StrAssign(String T,char *chars)
{
    int i;
    if(strlen(chars)>MAXSIZE)
        return ERROR;
    else
    {
        T[0]=strlen(chars);
        for(i=1;i<=T[0];i++)
            T[i]=*(chars+i-1);
        return OK;
    }
}

二、二叉树基本操作

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

1、打印数据

Status visit(CElemType e)
{
    printf("%c ",e);
    return OK;
}

2、构造空二叉树T

Status InitBiTree(BiTree *T)
{
    *T=NULL;
    return OK;
}

销毁二叉树
初始条件: 二叉树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 */
    }
}
#define ClearBiTree DestroyBiTree

创建二叉树
按前序输入二叉树中的结点值(字符),#表示空树;

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);
    }
}

二叉树T是否为空;
初始条件: 二叉树T存在
操作结果: 若T为空二叉树,则返回TRUE,否则FALSE

Status BiTreeEmpty(BiTree T)
{
    if(T)
        return FALSE;
    else
        return TRUE;
}

二叉树T的深度
初始条件: 二叉树T存在
操作结果: 返回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;
}

二叉树T的根
初始条件: 二叉树T存在
操作结果: 返回T的根

CElemType Root(BiTree T){
    if (BiTreeEmpty(T))
        return Nil;
    
    return T->data;
}

返回p所指向的结点值;
初始条件: 二叉树T存在，p指向T中某个结点
操作结果: 返回p所指结点的值

CElemType Value(BiTree p){
    return p->data;
}

给p所指结点赋值为value;
初始条件: 二叉树T存在，p指向T中某个结点
操作结果: 给p所指结点赋值为value

void Assign(BiTree p,CElemType value)
{
    p->data=value;
}

二、二叉树遍历

前序递归遍历T
初始条件:二叉树T存在;
操作结果: 前序递归遍历

void PreOrderTraverse(BiTree T)
{
    if(T==NULL)
        return;
    printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
    PreOrderTraverse(T->lchild); /* 再先序遍历左子树 */
    PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */
}

中序递归遍历T
初始条件:二叉树T存在;
操作结果: 中序递归遍历T

void InOrderTraverse(BiTree T)
{
    if(T==NULL)
        return ;
    InOrderTraverse(T->lchild); /* 中序遍历左子树 */
    printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
    InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */
}

后序递归遍历T
初始条件:二叉树T存在;
操作结果: 中序递归遍历T

void PostOrderTraverse(BiTree T)
{
    if(T==NULL)
        return;
    PostOrderTraverse(T->lchild); /* 先后序遍历左子树  */
    PostOrderTraverse(T->rchild); /* 再后序遍历右子树  */
    printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("二叉树链式存储结构实现!\n");
    
    int i;
    BiTree T;
    CElemType e1;
    
    InitBiTree(&T);
    
    StrAssign(str,"ABDH#K###E##CFI###G#J##");
    
    CreateBiTree(&T);
    printf("二叉树是否为空%d(1:是 0:否),树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
    
    e1=Root(T);
    printf("二叉树的根为: %c\n",e1);
    
    printf("\n前序遍历二叉树:");
    PreOrderTraverse(T);
    
    printf("\n中序遍历二叉树:");
    InOrderTraverse(T);
    
    printf("\n后序遍历二叉树:");
    PostOrderTraverse(T);
    
    printf("\n");
    
    return 0;
}