【数据结构】二叉树的创建与遍历

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


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

#define MAXSIZE 100    /* 存储空间初始分配量 */

typedef int Status;

typedef char TElemType; /* 假定二叉树的元素都是字符类型*/
TElemType Nil = ' ';

typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;


/* 模拟生成char数组， 用于构造二叉树所生产的数据***************/
int index$ = 1;
typedef char String[24];
String str;

/* 将chars 用String结构体表示*/
Status StrAssign(String S,char *chars)
{
    int i;
    if (strlen(chars) > MAXSIZE) {
        return ERROR; // 超过了最大容量
    } else {
        // 第一个位置存放字符串的长度
        S[0] = strlen(chars);
        for (i= 1; i < S[0]; i++) {
            S[i] = *(chars + i -1);
        }

        return OK;
    }


}

/* ******************************************************/

/* 构造空的的二叉树T */
Status InitBiTree(BiTree *T)
{
    *T = NULL;
    return OK;
}

/* 构造二叉树T， 使用的是递归创建的方法 */
void CreateBiTree(BiTree  *T)
{


    if (index$ == strlen(str)) // 所有的元素都分配完毕， 即结束
        return;
    TElemType ch = str[index$++];


    if (ch == '#') {
        // 碰到#号， 停止生成新的结点
        *T = NULL;
    } else {
        *T = (BiTree)malloc(sizeof(BiTNode));
        if (!*T){
            exit(OVERFLOW); // malloc失败
        }

        (*T)->data = ch; // 生成根节点
        CreateBiTree(&(*T)->lchild); // 构造左子树
        CreateBiTree(&(*T)->rchild); // 构造右子树
    }


}

/* 前序遍历*/
void PreOrderTraverse(BiTree *T)
{
    if (*T == NULL)
        return;

    printf("%c ",(*T)->data);
    PreOrderTraverse(&(*T)->lchild);
    PreOrderTraverse(&(*T)->rchild);
}



int main() {

    BiTree T;
    InitBiTree(&T);

    // 构造字符串
    StrAssign(str,"ABDH#K###E##CFI###G#J##");


    // 构造二叉树
    CreateBiTree(&T);

    PreOrderTraverse(&T);


    return 0;
}

（编辑：宣城站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!