完整二叉樹的創(chuàng)建

思路：主要是利用遞歸的思想創(chuàng)建的，先不斷調(diào)用該函數(shù)創(chuàng)建左子樹，等創(chuàng)建到最后一個(gè)左子樹的時(shí)候就開始往回創(chuàng)建右子樹。
注意：pos要從1開始

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

二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)

#define N 100
typedef char DATATYPE; 
typedef struct Node
{  
    DATATYPE data; // 數(shù)據(jù)域
    struct Node *lchild; // 左孩子指針域
    struct Node *rchild; // 右孩子指針域
}BTNode,*PBTNode,*BiTreeLink;

創(chuàng)建二叉樹

BiTreeLink CreateBinTree(char *nodes,int pos,int num)//pos是節(jié)點(diǎn)號(hào)，num為該二叉樹總結(jié)點(diǎn)數(shù)，nodes要存入的數(shù)據(jù)
{
    PBTNode p;        
    if(nodes[pos]==' '||pos>num)    // 遞歸結(jié)束條件
       return NULL;
    p = (PBTNode)malloc(sizeof(BTNode));  // 建立根結(jié)點(diǎn)
    if(!p)	判斷結(jié)點(diǎn)是否創(chuàng)建成功                                             
    {
        printf("創(chuàng)建根結(jié)點(diǎn)失敗！\n");                     
        return 0;
    }
    p->data = nodes[pos];      // 將數(shù)據(jù)存入數(shù)據(jù)域
    p->lchild=CreateBinTree(nodes,2*pos, num);    // 利用遞歸建立左子樹
    p->rchild=CreateBinTree(nodes,2*pos+1, num);  // 利用遞歸建立右子樹
    return p;
}

遍歷的大概思路：
主要是訪問(wèn)根的順序，
樹的前序遍歷
口訣：根左右
原理：
1.訪問(wèn)根節(jié)點(diǎn)
2.前序遍歷根結(jié)點(diǎn)的左子樹
3.前序遍歷根節(jié)點(diǎn)的右子樹

void preOrder(BTNode *p)
{
    if(p != NULL)
    {
        printf("%c  ",p->data);//根
        preOrder(p->lchild);//訪問(wèn)根的左子樹
       	preOrder(p->rchild);//訪問(wèn)根的右子樹
    }
}

二叉樹中序遍歷
口訣就是：左根右
原理：
1.中序遍歷根結(jié)點(diǎn)的左子樹
2.訪問(wèn)根節(jié)點(diǎn)
3.中序遍歷根節(jié)點(diǎn)的右子樹

void inOrder(BTNode *p)
{
    if(p!=NULL)
    {
        inorder(p->lchild); //訪問(wèn)根的左子樹
        printf("%c  ",p->data);
        inorder(p->rchild);//訪問(wèn)根的右子樹
    }
}

二叉樹的后序遍歷

口訣就是：左右根
原理：
1.后序遍歷根結(jié)點(diǎn)的左子樹
2.后序遍歷根節(jié)點(diǎn)的右子樹
3.訪問(wèn)根節(jié)點(diǎn)

void postOrder(BTNode *p)
{
    if(p != NULL)
    {
        postOrder(p->lchild);//訪問(wèn)根的左子樹
        postOrder(p->rchild);//訪問(wèn)根的右子樹
         printf("%c  ",p->data);//根
    }
}

主函數(shù)

 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                                // 否則按照實(shí)際輸入存儲(chǔ)
        {
            nodes[i+1] = str[i];
        }
    }

    tree = CreateBinTree(nodes,1,length);    // 創(chuàng)建二叉樹
    preOrder(tree);					// 前序遍歷
    inOrder(tree);                         // 中序遍歷
    postOrder(tree);					// 后序遍歷
}