#方法创建二叉树

以下给出先序遍历的结果来创建二叉树，#方法可以唯一创建一颗二叉树，因为规定叶子节点后面必须要#来标识结束，所以，不管左子树和右子树如果没有，就肯定会有#,下面的例子可知，1是根，2是1的左子树，4是2的左子树，4为叶子节点，2的右子树为空，到此处就知道2这棵树结束，3为1的右子树，3为叶子节点。所以可以唯一确定这棵树。这种方法还是可以用在简单开发里面的。

（此图来源于传智播客课程）

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

using namespace std;

//二叉链表

struct BinNode

{

    char data;

    struct BinNode * lchild, *rchild;

};

typedef struct BinNode BinNode;

typedef struct BinNode * BinTree;

//中序遍历递归实现

void Middleindex(BinNode * root)

{

    if (root == NULL)

    {

        return;

    }

    Middleindex(root->lchild);

    printf("%c ", root->data);

    Middleindex(root->rchild);

}

//创建#二叉树

BinNode * createTree()

{

    BinNode * node = NULL;

    BinNode * pl = NULL, *pr = NULL;

    node = (BinNode *)malloc(sizeof(BinNode));

    memset(node, 0, sizeof(BinNode));

    if (node == NULL)

    {

        return NULL;

    }

    char h;

    scanf("%c", &h);

    if (h == '#' || h ==NULL)

        return NULL;

    node->data = h;

    //创建左子树

    pl = createTree();

    if (pl != NULL)

        node->lchild = pl;

    else

        node->lchild = NULL;

    //创建右子树

    pr = createTree();

    if (pr != NULL)

        node->rchild = pr;

    else

        node->rchild = NULL;

    return node;

}

int main()

{

    BinNode * p = NULL;

    p = createTree();

    Middleindex(p);

    return 0;

}

运行结果：

例2：先序遍历结果：ABDH#K###E##CFI###G#J##,求这颗二叉树的形状

代码运行结果：