完整二叉樹的創建

思路：主要是利用遞歸的思想創建的，先不斷調用該函數創建左子樹，等創建到最后一個左子樹的時候就開始往回創建右子樹。
注意：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);					// 后序遍歷
}