1.遞歸遍歷

遞歸遍歷非常簡單，，，，，，

1.1前序遍歷

void preOrderTraverse(BSTreeNode *root)
{
    if (root != NULL)
    {
        printf("%d \n", root->data);
        preOrderTraverse(root->left);
        preOrderTraverse(root->right);
    }
}

1.2中序遍歷

void InOrderTraverse(BSTreeNode *root)
{
    if (root != NULL)
    {        
        InOrderTraverse(root->left);
        printf("%d \n", root->data);
        InOrderTraverse(root->right);
    }
}

1.3後序遍歷

void PostOrderTraverse(BSTreeNode *root)
{
    if (root != NULL)
    {        
        PostOrderTraverse(root->left);
        PostOrderTraverse(root->right);
        printf("%d \n", root->data);
    }
}

2.非遞歸遍歷

棧和隊列的構建 詳見其他博文

2.1前序遍歷

void preOrderTraverseNR(BSTreeNode *root)
{
    //建立棧
    struct LinkedStack *Stack;
    Stack = initStack();
    while(NULL != root){
        printf("%d \n", root->data);
        if (NULL != root->right)
        {
            push(Stack, root->right);
        }
        if (NULL != root->left)
        {
            push(Stack, root->left);
        }
        root = pop(Stack);
    }
    free(Stack);
    Stack = NULL;
}

下週繼續

ok，繼續

2.2中序遍歷

void InOrderTraverseNR(BSTreeNode *root)
{
    //建立棧
    struct LinkedStack *Stack;
    Stack = initStack();
    while(NULL != root || Stack->size > 0){
        if (root != NULL)
        {
            push(Stack, root);
            root = root->left;
        }else{
            root = pop(Stack);
            printf("%d \n", root->data);
            root = root->right;
        }
    }
    free(Stack);
    Stack = NULL;
}

2.3後序遍歷

void PostOrderTraverseNR(BSTreeNode *root)
{
    //建立棧
    struct LinkedStack *Stack;
    struct LinkedStack *StackTmp;
    Stack    = initStack();
    StackTmp = initStack();
    while(NULL != root || StackTmp->size > 0){
        while (root != NULL)
        {
            push(Stack, root);
            push(StackTmp, root);
            root = root->right;
        }
        if (StackTmp->size > 0)
        {
            root = pop(StackTmp);
            root = root->left;
        }
    }
    while(Stack->size > 0){
        root = pop(Stack);
        printf("%d \n", root->data);
    }
    free(Stack);
    free(StackTmp);
    Stack = NULL;
    StackTmp = NULL;
}

測試：