二叉搜索树判定方法（c++实现）

一时失言乱红尘 2022-02-28 08:16 228阅读 0赞

# [二叉搜索树判定方法（c++实现）][c] #

\--- 欢迎指正---

自己想到的方法是：使用 中序遍历数组或者链表，然后比较数组或者链表中的数据是否有序。

CC150 提供了更棒的解法。

原文大致描述：

//<方法1>
    //首先我们想到的是二叉树中序遍历后的结果是有序的，根据这个结果，我们可以中序遍历二叉树，并把遍历结果存放在一个数组里面，
    // 然后判断这个数组大小是否是有序数组，如果是有序数组，则是二叉查找树，否则就不是。
    //这个方法的时间复杂度是O(N)，但是空间复杂度比较高，需要浪费O（N）的存储空间。
    //<方法2>
    //其实在<方法1>的基础上，我们可以在中序遍历的同时，比较大小，每次记录下上次遍历过的元素的值，如果当前元素的值大于上次遍历元素的值，则接着遍历，否则返回false，
    // 因为这个记录是一个址传递，所以需要用到引用形参进行传递。
    //这个方法的时间复杂度与<方法1>的时间复杂度相同，只是空间复杂度只需要一个元素O(1)。

按照提供的思路，自己尝试写了下代码：

结点结构:

struct node 
    {
        // 数据域
        int data;
    
        // 左节点
        node *lc;
    
        // 右结点
        node *rc;
    
        // 构造函数
        node()
            : data(0)
            , lc(NULL)
            , rc(NULL)
        {
        }
    };

判定方法：

// 采用中序遍历的思路
        bool is_bst(node *pnode, int &last_val)
        {
            if (NULL == pnode)
                return true;
            
            // 开始遍历左子树
            if (!is_bst(pnode->lc, last_val))
                return false;
            
            // 因为左孩子的结点值比当前结点的值还要小。否则 就不是 二叉搜索树
            if (last_val > pnode->data)
                return false;
    
            last_val = pnode->data;
    
            // 遍历右子树
            if (!is_bst(pnode->rc, last_val))
                return false;
    
            return true;
        }

GitHub地址： [https://github.com/mohistH/base\_data\_structure][https_github.com_mohistH_base_data_structure]

posted @ 2019-03-23 08:33 [mohist][] 阅读( ...) 评论( ...) [编辑][Link 1] 收藏

[c]: https://www.cnblogs.com/pandamohist/p/10582448.html
[https_github.com_mohistH_base_data_structure]: https://github.com/mohistH/base_data_structure
[mohist]: https://www.cnblogs.com/pandamohist/
[Link 1]: https://i.cnblogs.com/EditPosts.aspx?postid=10582448