• 二叉树是树的特殊一种，具有如下特点：1、每个结点最多有两颗子树，结点的度最大为2。2、左子树和右子树是有顺序的，次序不能颠倒。3、即使某结点只有一个子树，也要区分左右子树。
  

#include<bits/stdc++.h>
#include<queue>
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#define n 6
#define m 2*n-1
#define maxval 1
#define maxsize 1024
typedef struct node
{
    char data;
    struct node *lc,*rc;
} bitree;
bitree *creatree()
{
    char ch;
    bitree *Q[maxsize];
    int ffront,rrear;//表示队头和队尾，建立一个队列储存两个孩子还没有储存完的结点
    bitree *root,*s;//根结点指针和中间变量
    root=NULL;
    ffront=1;
    rrear=0;
    printf("请输入二叉树的各结点，@表示虚结点，#表示结束：\n");
    scanf("%c",&ch);
    while(ch!='#')//若不是结束符
    {
        putchar(ch);//按层数从左到右输出二叉树（@表示虚结点）
        s=NULL;
        if(ch!='@')
        {
            s=(bitree *)malloc(sizeof(bitree));//向系统申请分配指定size个字节的内存空间
            s->data=ch;
            s->lc=NULL;
            s->rc=NULL;
        }
        rrear++;
        Q[rrear]=s;
        if(rrear==1)//若是根结点
            root=s;
        else//若不是根结点
        {
            if(s)//若不是虚结点，则需寻找它的父亲结点
            //书上写的是if(s&&Q[ffront])，感觉后面那个条件应该没有必要，因为s不是虚结点那此时ffront对应的也不会是虚结点
            //换句话说除了根结点，不会出现第二个没有父亲结点的结点
            {
                if(rrear%2==0)//（利用二叉树第五个性质）判断它是左孩子还是右孩子
                    Q[ffront]->lc=s;
                else
                    Q[ffront]->rc=s;
            }
            if(rrear%2==1)//因为每个结点有两个度（算上虚结点），所以每遍历两个结点（包括虚结点），队头更新一次
                ffront++;//（Q[ffront]的两个孩子处理完毕，出队列）
        }
        scanf("%c",&ch);
    }
    return root;//返回根指针
}
void preorder(bitree *p)//三种遍历都是用的递归
{
    if(p!=NULL)
    {
        printf("%c ",p->data);
        preorder(p->lc);
        preorder(p->rc);
    }
    return;
}
void inorder(bitree *p)
{
    if(p!=NULL)
    {
        inorder(p->lc);
        printf("%c ",p->data);
        inorder(p->rc);
    }
    return;
}
void postorder(bitree *p)
{
    if(p!=NULL)
    {
        postorder(p->lc);
        postorder(p->rc);
        printf("%c ",p->data);
    }
    return;
}
int main()
{
    bitree *root;
    root=creatree();
    printf("\n先序遍历结果如下：\n");
    preorder(root);
    printf("\n中序遍历结果如下：\n");
    inorder(root);
    printf("\n后续遍历结果如下：\n");
    postorder(root);
    return 0;
}
//ABCD@EF@G@@@@H#

• 实验结果
  

• 二叉树创建完成后，一维数组Q的存储情况如下图
  P1、P2、P3、P4、P5、P6、、、分别表示数组元素Q1、Q2、Q3、Q4、Q5、Q6、、、的地址，
  如图所示，P1所指向的结构体中三个变量分别为A、P1、P2。
  

• 没有注释的代码

#include<bits/stdc++.h>
#include<queue>
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#define n 6
#define m 2*n-1
#define maxval 1
#define maxsize 1024
typedef struct node
{
     char data;
     struct node *lc,*rc;
}bitree;
bitree *creatree()
{
     char ch;
     bitree *Q[maxsize];
     int ffront,rrear;
     bitree *root,*s;
     root=NULL;
     ffront=1;rrear=0;
     printf("请输入二叉树的各结点，@表示虚结点，#表示结束：\n");
     scanf("%c",&ch);
     while(ch!='#')
     {
          putchar(ch);
          s=NULL;
          if(ch!='@')
          {
               s=(bitree *)malloc(sizeof(bitree));
               s->data=ch;
               s->lc=NULL;
               s->rc=NULL;
          }
          rrear++;
          Q[rrear]=s;
          if(rrear==1) root=s;
          else
          {
               if(s&&Q[ffront])
               {
                    if(rrear%2==0)
                         Q[ffront]->lc=s;
                    else
                         Q[ffront]->rc=s;
               }
               if(rrear%2==1)
                   ffront++;
          }
          scanf("%c",&ch);
     }
     return root;
}
void preorder(bitree *p)
{
     if(p!=NULL)
     {
          printf("%c ",p->data);
          preorder(p->lc);
          preorder(p->rc);
     }
     return;
}
void inorder(bitree *p)
{
     if(p!=NULL)
     {
          inorder(p->lc);
          printf("%c ",p->data);
          inorder(p->rc);
     }
     return;
}
void postorder(bitree *p)
{
     if(p!=NULL)
     {
          postorder(p->lc);
          postorder(p->rc);
          printf("%c ",p->data);
     }
     return;
}
int main()
{
    bitree *root;
    root=creatree();
    printf("\n先序遍历结果如下：\n");
    preorder(root);
    printf("\n中序遍历结果如下：\n");
    inorder(root);
    printf("\n后续遍历结果如下：\n");
    postorder(root);
    return 0;
}