データ構造-ツリー-二叉のツリーは、完全に実行可能なコード(再帰的/非再帰的)を巡回します。

データ構造-ツリー-二叉のツリーは、完全に実行可能なコード(再帰的/非再帰的)を巡回します。
mark：いいブログがあります。再帰アルゴリズムについて詳しく説明しています。先に記録しました。http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html

#include <stdio.h>
#include <stdlib.h>

#define  MAXSIZE 20
//             
typedef struct BitNode
{
    char    data;
    struct BitNode* left,*right;
}BitTree;

//         
typedef struct stackelem
{
    BitTree* a[MAXSIZE];
    int top;
}Stack;

//           
typedef struct queueelem
{
    BitTree* b[MAXSIZE];
    int front,rear;
}Queue;

//     ，       
//       。   A # #(#    )
BitTree* Create()
{
    char ch;
    scanf("%c",&ch);
    getchar();    //     
    if (ch=='#')
    {
        return NULL;
    }
    else
    {
        BitTree* btree=(BitTree*)malloc(sizeof(BitTree));
        if (NULL==btree)
        {
            return NULL;
        }
        btree->data=ch;
        btree->left=Create();
        btree->right=Create();
        return btree;
    }
}

//    ，     
void Preorder(BitTree* bt)
{
    if (NULL!=bt)
    {
        printf("%c ",bt->data);
        Preorder(bt->left);
        Preorder(bt->right);
    }
}

//          
/*
   ：      ；     ，     ，  ，           ，  ，     ；  ，      （  ）,
          ，       ，      （  ）...      ，     。
 */
void Preorder2(BitTree* bt)
{
    BitTree* p;
    Stack st;
    st.top=-1;
    if (NULL==bt)
    {
        return;
    }
    else
    {
        st.top++;
        st.a[st.top]=bt;
        while (st.top!=-1)
        {
            p=st.a[st.top];
            st.top--;
            printf("%c ",p->data);
            if (p->right!=NULL)
            {
                st.top++;
                st.a[st.top]=p->right;
            }
            if (p->left!=NULL)
            {
                st.top++;
                st.a[st.top]=p->left;
            }
        }
    }
}

//    ，    
void Inorder(BitTree* bt)
{
    if (NULL!=bt)
    {
        Inorder(bt->left);
        printf("%c ",bt->data);
        Inorder(bt->right);
    }
}

//    ，     
/*
   ：   。      ，  ，          ，        。        ，            ，
      ，       。        ，            ，    ，        ；        
     ，   ；       ，       ，     ，      ；              ，       ，
     ，       。    ....
   ，     。
 */
void Inorder2(BitTree* bt)
{
    BitTree* p,*q;
    Stack st;
    st.top=-1;
    if (NULL==bt)
    {
        return;
    }
    else
    {
        while (bt!=NULL)
        {
            st.top++;
            st.a[st.top]=bt;
            bt=bt->left;
        }
        while (st.top!=-1)
        {
            p=st.a[st.top];
            st.top--;
            printf("%c ",p->data);
            while ( p->right!=NULL )
            {
                st.top++;
                st.a[st.top]=p->right;
                q=p->right;
                while (q->left!=NULL)
                {
                    st.top++;
                    st.a[st.top]=q->left;
                    q=q->left;
                }
                break;
            }
        }
    }
}

//    ，    
void Postorder(BitTree* bt)
{
    if (bt!=NULL)
    {
        Postorder(bt->left);
        Postorder(bt->right);
        printf("%c ",bt->data);
    }
}

//    ，     
/*
     ：      。      ，        ，   ，          。      （   ，    ），  
 1:              ，            ，     （     ，          ），      ，
     ，           。
 2:       ，      ，      ，            ，               。
 */
void Postorder2(BitTree* bt)
{
    Stack st;
    st.top=-1;
    BitTree* t;
    do
    {
        while (bt!=NULL)
        {
            st.top++;
            st.a[st.top]=bt;
            bt=bt->left;
        }
        t=NULL;
        while (st.top!=-1)
        {
            bt=st.a[st.top];
            if (bt->right==t)  //t:   null，           。
            {
                printf("%c ",bt->data);
                st.top--;
                t=bt;  //t          
            }
            else
            {
                bt=bt->right;
                break;
            }
        }
    } while (st.top!=-1);
}

//       ，    
int Height(BitTree* bt)
{
    int depth1,depth2;
    if (NULL==bt)
    {
        return 0;
    }
    else
    {
        depth1=Height(bt->left);
        depth2=Height(bt->right);
        if (depth1>depth2)
        {
            return (depth1+1);
        }
        else
        {
            return (depth2+1);
        }
    }
}

//       ,      
void TraversalOfLevel(BitTree* bt)
{
    Queue q;
    q.front=q.rear=0;
    if (bt!=NULL)
    {
        printf("%c ",bt->data);
    }
    q.b[q.front]=bt;
    q.rear=q.rear+1;
    while (q.front<q.rear)
    {
        bt=q.b[q.front];
        q.front=q.front+1;
        if (bt->left!=NULL)
        {
            printf("%c ",bt->left->data);
            q.b[q.rear]=bt->left;
            q.rear=q.rear+1;
        }
        if (bt->right!=NULL)
        {
            printf("%c ",bt->right->data);
            q.b[q.rear]=bt->right;
            q.rear=q.rear+1;
        }
    }
}

int main()
{
    BitTree* btr=Create();
    printf("    ：        ：
");
    Preorder(btr);
    printf("
");
    Preorder2(btr);
    printf("
");
    printf("    ：        ：
");
    Inorder(btr);
    printf("
");
    Inorder2(btr);
    printf("
");
    printf("    ：        ：
");
    Postorder(btr);
    printf("
");
    Postorder2(btr);
    printf("
");
    printf("      ：
");
    int Hgt=Height(btr);
    printf("%d 
",Hgt);
    printf("       :
");
    TraversalOfLevel(btr);
    printf("
");
    return 0;
}

/*      ：  
 d b a # # c # # f e # # g # #
     ：        ：
 d b a c f e g
 d b a c f e g
     ：        ：
 a b c d e f g
 a b c d e f g
     ：        ：
 a c b e g f d
 a c b e g f d
       ：
 3
        :
 d b f a c e g

*/

勉強の途中で、君と一緒に勉強します。