二叉树的创建和前序，中序，后序遍历（详细）

完整二叉树的创建

思路：主要是利用递归的思想创建的，先不断调用该函数创建左子树，等创建到最后一个左子树的时候就开始往回创建右子树。
注意：pos要从1开始

p->lchild=CreateBinTree(nodes,2*pos, num);  
p->rchild=CreateBinTree(nodes,2*pos+1, num);  

二叉树的二叉链表存储结构

#define N 100
typedef char DATATYPE; 
typedef struct Node
{  
    DATATYPE data; // 数据域
    struct Node *lchild; // 左孩子指针域
    struct Node *rchild; // 右孩子指针域
}BTNode,*PBTNode,*BiTreeLink;

创建二叉树

BiTreeLink CreateBinTree(char *nodes,int pos,int num)//pos是节点号，num为该二叉树总结点数，nodes要存入的数据
{
    PBTNode p;        
    if(nodes[pos]==' '||pos>num)    // 递归结束条件
       return NULL;
    p = (PBTNode)malloc(sizeof(BTNode));  // 建立根结点
    if(!p)	判断结点是否创建成功                                             
    {
        printf("创建根结点失败！\n");                     
        return 0;
    }
    p->data = nodes[pos];      // 将数据存入数据域
    p->lchild=CreateBinTree(nodes,2*pos, num);    // 利用递归建立左子树
    p->rchild=CreateBinTree(nodes,2*pos+1, num);  // 利用递归建立右子树
    return p;
}

遍历的大概思路：
主要是访问根的顺序，
树的前序遍历
口诀：根左右
原理：
1.访问根节点
2.前序遍历根结点的左子树
3.前序遍历根节点的右子树

void preOrder(BTNode *p)
{
    if(p != NULL)
    {
        printf("%c  ",p->data);//根
        preOrder(p->lchild);//访问根的左子树
       	preOrder(p->rchild);//访问根的右子树
    }
}

二叉树中序遍历
口诀就是：左根右
原理：
1.中序遍历根结点的左子树
2.访问根节点
3.中序遍历根节点的右子树

void inOrder(BTNode *p)
{
    if(p!=NULL)
    {
        inorder(p->lchild); //访问根的左子树
        printf("%c  ",p->data);
        inorder(p->rchild);//访问根的右子树
    }
}

二叉树的后序遍历

口诀就是：左右根
原理：
1.后序遍历根结点的左子树
2.后序遍历根节点的右子树
3.访问根节点

void postOrder(BTNode *p)
{
    if(p != NULL)
    {
        postOrder(p->lchild);//访问根的左子树
        postOrder(p->rchild);//访问根的右子树
         printf("%c  ",p->data);//根
    }
}

主函数

 void main()
 {
    int i;    
    BiTreeLink tree;     
    int length;         
    char nodes[N],str[N];                 
    gets(str);                                // 获取用户输入序列
    length = strlen(str);             
    for (i = 0; i < length;i++)
    {
        if (str[i] == ' ')                    // 检查用户输入是否有空格
        {
            nodes[i+1] = '*';                    // 如有空格则用*代替
        }
        else                                // 否则按照实际输入存储
        {
            nodes[i+1] = str[i];
        }
    }

    tree = CreateBinTree(nodes,1,length);    // 创建二叉树
    preOrder(tree);					// 前序遍历
    inOrder(tree);                         // 中序遍历
    postOrder(tree);					// 后序遍历
}