C语言实现链式二叉树&遍历二叉树

二叉树（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/-