C数据结构与算法——二叉树应用一

实验任务

(1) 掌握二叉树的二叉链表存储结构定义；
(2) 掌握该存储方式下的二叉树基本算法；
(3) 掌握三种遍历的递归算法。

实验内容

实现二叉链表存储结构及其基本算法
算法简单应用
- 创建一颗二叉树的二叉链表
- 输出该二叉树的三种遍历序列（前、中、后序遍历）

实验源码

#include <stdio.h>
#include <malloc.h>

typedef struct BiTNode {
    char data;
    struct BiTNode *lChild, *rChild;
} BiTNode, *BiTree;


void InitBiTree(BiTree *tree);

void CreateBiTree(BiTree *tree);

BiTree InsertLeftNode(BiTree tree, char data);

BiTree InsertRightNode(BiTree tree, char data);

void PreOrderTraverse(BiTree tree);

void InOrderTraverse(BiTree tree);

void PostOrderTraverse(BiTree tree);

void VisitNode(BiTree tree);


/**
 * <h2>二叉树实验一</h2>
 * <h3>左右插入结点法</h3>
 * @return 0
 */
int main() {

    // 定义一棵二叉树
    BiTree tree;

    // 初始化
    InitBiTree(&tree);

    // 创建二叉树
    CreateBiTree(&tree);

    // 前序遍历
    printf("前序遍历：");
    PreOrderTraverse(tree);
    printf("\n");

    // 中序遍历
    printf("中序遍历：");
    InOrderTraverse(tree);
    printf("\n");

    // 后序遍历
    printf("后序遍历：");
    PostOrderTraverse(tree);
    printf("\n");

    return 0;
}

void InitBiTree(BiTree *tree) {
    *tree = NULL;
}

void CreateBiTree(BiTree *tree) {
    *tree = InsertLeftNode(*tree, 'A');
    *tree = InsertLeftNode(*tree, 'B');
    *tree = InsertLeftNode(*tree, 'E');
    (*tree)->lChild->lChild = InsertRightNode((*tree)->lChild->lChild, 'F');
    (*tree)->lChild = InsertRightNode((*tree)->lChild, 'C');
    (*tree)->lChild = InsertRightNode((*tree)->lChild, 'D');
    (*tree)->lChild->rChild->rChild = InsertLeftNode((*tree)->lChild->rChild->rChild, 'G');
}

// 左插入
BiTree InsertLeftNode(BiTree tree, char data) {
    if (tree != NULL) {
        // 遍历左孩子
        tree->lChild = InsertLeftNode(tree->lChild, data);
    } else {
        // 插入结点到左孩子
        tree = (BiTree) malloc(sizeof(BiTNode));
        if (tree == NULL) {
            return NULL;
        }
        tree->data = data;
        tree->lChild = tree->rChild = NULL;
    }
    return tree;
}

// 右插入
BiTree InsertRightNode(BiTree tree, char data) {
    if (tree != NULL) {
        // 遍历右孩子
        tree->rChild = InsertRightNode(tree->rChild, data);
    } else {
        // 插入结点到右孩子
        tree = (BiTree) malloc(sizeof(BiTNode));
        if (tree == NULL) {
            return NULL;
        }
        tree->data = data;
        tree->lChild = tree->rChild = NULL;
    }
    return tree;
}

void PreOrderTraverse(BiTree tree) {
    if (tree != NULL) {
        VisitNode(tree); // 前序
        PreOrderTraverse(tree->lChild);
        PreOrderTraverse(tree->rChild);
    }
}

void InOrderTraverse(BiTree tree) {
    if (tree != NULL) {
        InOrderTraverse(tree->lChild);
        VisitNode(tree); // 中序
        InOrderTraverse(tree->rChild);
    }
}

void PostOrderTraverse(BiTree tree) {
    if (tree != NULL) {
        PostOrderTraverse(tree->lChild);
        PostOrderTraverse(tree->rChild);
        VisitNode(tree); // 后序
    }
}

void VisitNode(BiTree tree) {
    printf("%c ", tree->data);
}