1.先序，中序，后序递归实现

    1. #include <stdio.h>
    2. #include <stdlib.h>
    4. struct TreeNode 
    5. {
    6.     char Data;
    7.     struct TreeNode *Left;
    8.     struct TreeNode *Right;
    9. }; 
    11. struct TreeNode * CreateBinTree(void);
    12. void InorderTraversal( struct TreeNode * BT );
    13. void PreorderTraversal( struct TreeNode * BT );
    14. void PostorderTraversal( struct TreeNode * BT );
    16. int main(void)
    17. {
    18.     struct TreeNode *pT = CreateBinTree();
    19.     printf("先序遍历:\n"); 
    20.     PreorderTraversal(pT);
    21.     printf("中序遍历:\n"); 
    22.     InorderTraversal(pT);
    23.     printf("后序遍历:\n"); 
    24.     PostorderTraversal(pT); 
    25.     free(pT);
    26.     return 0;
    27. }
    29. struct TreeNode * CreateBinTree(void)
    30. {
    31.     struct TreeNode *pA = (struct TreeNode *)malloc(sizeof(TreeNode));
    32.     struct TreeNode *pB = (struct TreeNode *)malloc(sizeof(TreeNode));
    33.     struct TreeNode *pC = (struct TreeNode *)malloc(sizeof(TreeNode));
    34.     struct TreeNode *pD = (struct TreeNode *)malloc(sizeof(TreeNode));
    35.     struct TreeNode *pE = (struct TreeNode *)malloc(sizeof(TreeNode));
    37.     pA->Data = 'A';
    38.     pB->Data = 'B';
    39.     pC->Data = 'C';
    40.     pD->Data = 'D';
    41.     pE->Data = 'E';
    43.     pA->Left = pB;
    44.     pA->Right = pC;
    45.     pB->Left = NULL;
    46.     pB->Right = NULL;
    47.     pC->Left = pD;
    48.     pC->Right = NULL;
    49.     pD->Left = NULL;
    50.     pD->Right = pE;
    51.     pE->Left = NULL;
    52.     pE->Right = NULL;
    54.     return pA;
    55. }
    57. void PreorderTraversal( struct TreeNode * BT )
    58. {
    59.     if( BT ) 
    60.     {
    61.         printf("%c\n", BT->Data );
    62.         PreorderTraversal( BT->Left );
    63.         PreorderTraversal( BT->Right );
    64.     }
    65. }
    67. void InorderTraversal( struct TreeNode * BT )
    68. {
    69.     if( BT ) 
    70.     {
    71.         InorderTraversal( BT->Left );
    72.         printf("%c\n", BT->Data);
    73.         InorderTraversal( BT->Right );
    74.     }
    75. }
    77. void PostorderTraversal( struct TreeNode * BT )
    78. {
    79.     if( BT ) 
    80.     {
    81.         PostorderTraversal( BT->Left );
    82.         PostorderTraversal( BT->Right );
    83.         printf("%c\n", BT->Data);
    84.     }
    85. }

    2.层序遍历

    1. #include <stdio.h>
    2. #include <stdlib.h>
    3. #define MaxSize 100
    5. struct TreeNode 
    6. {
    7.     int Data;
    8.     struct TreeNode *Left;
    9.     struct TreeNode *Right;
    10. }; 
    12. struct QNode
    13. {
    14.     struct TreeNode * Data[MaxSize];
    15.     int rear;
    16.     int front;
    17. };
    19. typedef struct QNode *Queue;
    21. struct TreeNode * CreateBinTree(void);
    22. Queue CreatQueue();
    23. void AddQ(Queue Q, struct TreeNode * X);
    24. bool IsFull(Queue Q);
    25. bool IsEmpty(Queue Q);
    26. struct TreeNode * Delete(Queue Q);
    27. void LevelorderTraversal ( struct TreeNode * BT );
    29. int main(void)
    30. {
    31.     struct TreeNode *pT = CreateBinTree();
    32.     printf("层序遍历:\n");
    33.     LevelorderTraversal(pT);
    34.     free(pT);
    35.     return 0;
    36. }
    38. struct TreeNode * CreateBinTree(void)
    39. {
    40.     struct TreeNode *pA = (struct TreeNode *)malloc(sizeof(TreeNode));
    41.     struct TreeNode *pB = (struct TreeNode *)malloc(sizeof(TreeNode));
    42.     struct TreeNode *pC = (struct TreeNode *)malloc(sizeof(TreeNode));
    43.     struct TreeNode *pD = (struct TreeNode *)malloc(sizeof(TreeNode));
    44.     struct TreeNode *pE = (struct TreeNode *)malloc(sizeof(TreeNode));
    46.     pA->Data = 5;
    47.     pB->Data = 6;
    48.     pC->Data = 7;
    49.     pD->Data = 8;
    50.     pE->Data = 9;
    52.     pA->Left = pB;
    53.     pA->Right = pC;
    54.     pB->Left = NULL;
    55.     pB->Right = NULL;
    56.     pC->Left = pD;
    57.     pC->Right = NULL;
    58.     pD->Left = NULL;
    59.     pD->Right = pE;
    60.     pE->Left = NULL;
    61.     pE->Right = NULL;
    63.     return pA;
    64. }
    66. Queue CreatQueue()
    67. {
    68.     Queue Q;
    69.     Q = (Queue)malloc(sizeof(struct QNode));
    70.     Q->rear = -1;
    71.     Q->front = -1;
    72.     return Q;
    73. }
    75. void AddQ(Queue Q, struct TreeNode * X)
    76. {
    77.     if(IsFull(Q))
    78.     {
    79.     printf("已满");
    80.     return ;
    81.     }
    82.     else
    83.     {
    84.         Q->rear = ((Q->rear) + 1) % MaxSize;
    85.         Q->Data[Q->rear] = X;
    86.     }
    87. }
    89. bool IsFull(Queue Q)
    90. {
    91.     return (((Q->rear) + 1) % MaxSize ) == Q->front;
    92. }
    94. bool IsEmpty(Queue Q)
    95. {
    96.     return (Q->front == Q->rear);
    97. }
    99. struct TreeNode * Delete(Queue Q)
    100. {
    101.     if(IsEmpty(Q))
    102.     {
    103.     printf("队空");
    104.     return NULL; 
    105.     }
    106.     else
    107.     {
    108.         Q->front = (Q->front + 1) % MaxSize;
    109.         return Q->Data[Q->front]; 
    110.     }
    111.  } 
    113. void LevelorderTraversal ( struct TreeNode * BT )
    114. { 
    115.     Queue Q; 
    116.     struct TreeNode * T;
    118.     if ( !BT )
    119.     return; 
    120.     Q = CreatQueue(); 
    121.     AddQ( Q, BT );
    122.     while ( !IsEmpty(Q) ) {
    123.         T = Delete( Q );
    124.         printf("%d\n", T->Data); 
    125.         if ( T->Left )   AddQ( Q, T->Left );
    126.         if ( T->Right )  AddQ( Q, T->Right );
    127.     }
    128. }