1.二叉树中序非递归实现

    1. #include<stdio.h>
    2. #include<stdlib.h> 
    3. #define MaxSize 100   
    4. typedef struct TreeNode * ElementType;  
    5. typedef struct SNode *Stack;
    7. struct TreeNode 
    8. {
    9.     int Data;
    10.     struct TreeNode *Left;
    11.     struct TreeNode *Right;
    12. }; 
    14. struct SNode
    15. {
    16.     ElementType Data[MaxSize];   
    17.     int Top; 
    18. }; 
    19. Stack S;
    21. struct TreeNode * CreateBinTree(void);
    22. Stack CreateStack();  
    23. bool IsFull(Stack S); 
    24. bool IsEmpty(Stack S);   
    25. void Push(Stack S,ElementType item);   
    26. ElementType Pop(Stack S);   
    27. void InOrderTraversal(struct TreeNode * BT); 
    29. int main(void)
    30. {
    31.     struct TreeNode *pT = CreateBinTree();
    32.     printf("二叉树非递归遍历:\n");
    33.     InOrderTraversal(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. Stack CreateStack()
    67. {
    68.     S = (Stack)malloc(sizeof(struct SNode));
    69.     S->Top = -1;
    70.     return S;
    71. } 
    73. bool IsFull(Stack S)
    74. {
    75.     return (S->Top == MaxSize-1);
    76. }
    78. bool IsEmpty(Stack S)
    79. {
    80.     return (S->Top == -1); 
    81. } 
    83. void Push(Stack S,ElementType item)
    84. {
    85.     if(IsFull(S))
    86.     {   
    87.         printf("堆栈满");
    88.         return;
    89.     }else
    90.     {
    91.         S->Top++;   
    92.         S->Data[S->Top] = item;   
    93.         return;
    94.     }
    95. }
    97. ElementType Pop(Stack S)
    98. {
    99.     if(IsEmpty(S))
    100.     {
    101.         printf("堆栈空");
    102.         return NULL;
    103.     }
    104.     else
    105.     {
    106.         ElementType val = S->Data[S->Top];  
    107.         S->Top--;  
    108.         return val;
    109.     }
    110. }
    112. void InOrderTraversal(struct TreeNode * BT)
    113. {
    114.     struct TreeNode * T = BT;
    115.     Stack S = CreateStack();
    116.     while(T || !IsEmpty(S))
    117.     {
    118.     while(T)
    119.     {
    120.         Push(S,T);
    121.         T = T->Left;
    122.     }
    123.     if(!IsEmpty(S))
    124.     {
    125.         T = Pop(S);
    126.         printf("%d\n", T->Data);
    127.         T = T->Right;
    128.     }
    129.      } 
    130. }

    2.KMP算法