前端之家收集整理的这篇文章主要介绍了
【数据结构】二叉树的创建与遍历,
前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
#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;
}