二叉树（binary tree）是一种常见的树形数据结构，其特点是每个结点至多有两棵子树，并且，二叉树的子树有左右树之分，其次序不能任意颠倒。
在对二叉树进行遍历之前，我们先构造一个二叉树。我们这里使用链式二叉树来构造我们的树。
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild; // 左节点
struct BiTNode *rchild; // 右节点
}BiTNode, *BiTree;
接下来我们开始构造我们的二叉树：
这里我们采用先序构造的方式
char auxiliary(){
// 自暴自弃系列
const char data[] = "-+a *b -c d /e f "; // 课本图6.9中的例子
int length = strlen(data);
// printf("length is %d", length);
if (i < length){
return data[i++];
}else{
return ' ';
}
}
void createBiTree(BiTree *t){
// 创建一个二叉树，以先序序列创建
TElemType ch = auxiliary();
// scanf(&ch);
if (ch == ' ') *t = NULL;
else{
// 分配空间
*t = malloc(sizeof(BiTNode));
if (!*t) perror("can't allocate memory");
(*t) -> data = ch;
// left subtree
createBiTree(&((*t)->lchild));
// right subtree
createBiTree(&((*t)->rchild));
}
}
完整代码如下所示：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int i = 0;
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild; // 左节点
struct BiTNode *rchild; // 右节点
}BiTNode, *BiTree;
char auxiliary(){
// 自暴自弃系列
const char data[] = "-+a *b -c d /e f "; // 课本图6.9中的例子
int length = strlen(data);
// printf("length is %d", length);
if (i < length){
return data[i++];
}else{
return ' ';
}
}
void createBiTree(BiTree *t){
// 创建一个二叉树，以先序序列创建
TElemType ch = auxiliary();
// scanf(&ch);
if (ch == ' ') *t = NULL;
else{
// 分配空间
*t = malloc(sizeof(BiTNode));
if (!*t) perror("can't allocate memory");
(*t) -> data = ch;
// left subtree
createBiTree(&((*t)->lchild));
// right subtree
createBiTree(&((*t)->rchild));
}
}
int preorderTraverse(BiTree b){
// 先序遍历
if (b){
if (printf("%c", b->data)){
if (preorderTraverse(b->lchild)){
if (preorderTraverse(b->rchild)) return 1;
}
}
return 0;
}else{
return 1;
}
}
void inorderTraverser(BiTree b){
// 中序遍历
if (b){
if (b->lchild) inorderTraverser(b->lchild);
printf("%c", b->data);
if (b->rchild){
inorderTraverser(b->rchild);
}
}
}
void postOrderTraverse(BiTree b){
if (b){
if (b->lchild) postOrderTraverse(b->lchild);
if (b->rchild) postOrderTraverse(b->rchild);
printf("%c", b->data);
}
}
void insertChild(BiTree t, BiTNode p, int LR, TElemType c){};
void main(){
BiTree t; // 初始化一个头结点
// printf('initial data is %c', t->data);
createBiTree(&t);
preorderTraverse(t);
printf("\n");
inorderTraverser(t);
printf("\n");
postOrderTraverse(t);
}
运行结果如下：
-+a*b-cd/ef
a+b*c-d-e/f
abcd-*+ef/-
