搜索二叉树的判断方法

搜索二叉树的判断方法

二叉搜索树的判断

1. 二叉树

二叉树是指每个父节点有两个子节点的树。用图形化的描述如下:
标准二叉树

2. 二叉搜索树

二叉搜索书是在二叉树的基础上,要求对于某个节点来说,所有小于该节点值的节点都在该节点的左子树上,所有大于该节点值的节点都在该节点的右子树上。

2.1 左子树存在大于某个父节点的值

左子树右节点问题

2.2 右子树存在小于某个父节点的值

右子树左节点问题

3. 判断方法

对于左右子树采用不同的函数来判断,接下来分别介绍。

3.1 左子树判断方法

当某节点为左子树节点的时候,其右子树节点可能大于该节点的父节点的情况,我们选择保存该节点和父节点的最大值传入判断函数。此时不仅要求该右子树节点的值大于当前节点,同时也需要小于该节点的父节点。

详细的信息参考该函数:

3.2 右子树判断方法

当某节点为右子树节点的时候,其左子树节点可能小于该节点的父节点的情况,我们选择保存该节点和父节点的最小值传入判断函数。此时不仅要求该左子树节点的值小于当前节点,同时也需要大于该节点的父节点。

详细的信息参考该函数:

4. 完整代码

Leave a Reply

Your email address will not be published. Required fields are marked *