题目24 二叉搜索树的后序遍历

深碍√TFBOYSˉ_ 2021-11-02 01:02 205阅读 0赞

/  
// 6. 题目24 二叉搜索树的后序遍历  
// 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果！！！  
/\*  
8  
/ \\  
6 10  
/ \\ / \\  
5 7 9 11

输入数组: \{5, 7, 6, 9, 11, 10, 8\}

// 左 -> 右 -> 中  
后序遍历: 5 7 6 9 11 10 8  
特点:  
1.最后一个元素为根节点  
2.小于根节点的为左子树,大于根节点的为右子树

\*/  
//

bool BinaryTreePostTraval(int aiArray[], int iLen)
    {
        if (NULL == aiArray || iLen <= 0)
        {
            return false;
        }
    
        int iRootVal = aiArray[iLen - 1];
        int iLeft = 0;
    
        // 1. 左子树比根节点小
        for (; iLeft < iLen - 1; iLeft++)
        {
            if (aiArray[iLeft] > iRootVal)
            {
                break;
            }
        }
    
        // 2.右子树比根节点大
        int iRight = iLeft;
        for (; iRight < iLen - 1; iRight++)
        {
            if (aiArray[iRight] < iRootVal)
            {
                return false;
            }
        }
    
        // 3.判断左子树是不是二叉搜索树
        bool bLeft = true;
        if (iLeft > 0)
        {
            bLeft = BinaryTreePostTraval(aiArray, iLeft);
        }
    
        // 4.判断右子树是不是二叉搜索树
        bool bRight = true;
        if (iRight > 0)
        {
            bRight = BinaryTreePostTraval(aiArray, bRight);
        }
    
        return bLeft && bRight;
    }
    
    void VerifySquenceOfBSTTestFunc()
    {
        cout << "\n\n --------------- VerifySquenceOfBSTTestFunc Start -------------->" << endl;
    
        int aiArray[] = {
        8, 6, 10, 5, 7, 9, 11};
        int aiArray2[] = {
        5, 7, 6, 9, 11, 10, 8};
    
        int iLen = sizeof(aiArray) / sizeof(int);
        TRAVERSAL_ARRAY(aiArray, iLen);
    
        // 判断数组是不是二叉搜索树的后序排序
        bool bFlag = BinaryTreePostTraval(aiArray, iLen);
        if (bFlag)
        {
            cout << "TRUE" << endl;
        }
        else
        {
            cout << "FALSE" << endl;
        }
    
        TRAVERSAL_ARRAY(aiArray2, iLen);
        bFlag = BinaryTreePostTraval(aiArray2, iLen);
        if (bFlag)
        {
            cout << "TRUE" << endl;
        }
        else
        {
            cout << "FALSE" << endl;
        }
        cout << "\n\n --------------- VerifySquenceOfBSTTestFunc End -------------->" << endl;
    
    }

转载于:https://www.cnblogs.com/yzdai/p/11258730.html