二叉树的递归创建

1. 二叉树的定义

首先，我们定义二叉树的节点结构和二叉树类型：

typedef char ElemType;

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

2. 从扩展的先序序列递归创建二叉树

给定扩展的先序序列 +-A##*F##G##C##，我们可以递归地创建二叉树。下面是具体的实现代码：

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

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

// 函数声明
BiTree CreateBiTree();

// 全局变量，用于遍历扩展的先序序列
char *preOrderSeq;

// 主函数
int main() {
    // 初始化扩展的先序序列
    preOrderSeq = "+-A##*F##G##C##";
    // 创建二叉树
    BiTree tree = CreateBiTree();
    return 0;
}

// 递归创建二叉树
BiTree CreateBiTree() {
    char ch = *preOrderSeq++;
    if (ch == '#') {
        return NULL;
    } else {
        BiTree node = (BiTree)malloc(sizeof(BiTNode));
        node->data = ch;
        node->lchild = CreateBiTree();
        node->rchild = CreateBiTree();
        return node;
    }
}