二叉搜索树的判断

1. 二叉树

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

2. 二叉搜索树

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

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

左子树右节点问题

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

右子树左节点问题

3. 判断方法

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

3.1 左子树判断方法

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

详细的信息参考该函数:

bool SearchLeftSubTree(const Node_s * pTree, const int nMaxValue)

3.2 右子树判断方法

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

详细的信息参考该函数:

bool SearchRightSubTree(const Node_s * pTree, const int nMinValue)

4. 完整代码

/**
 * @file SearchBinaryTree.cpp
 * @author DennisMi (https://www.dennisthink.com/)
 * @brief 二叉树的相关代码
 * @version 0.1
 * @date 2020-07-02
 * 
 * @copyright Copyright (c) 2020
 * 
 */

#include <iostream>
#include <algorithm>
#include <limits>

/**
 * @brief 二叉树的节点定义
 * 
 */
struct Node_s
{
	int m_value; //节点值
	Node_s * m_pLeft;//左子树节点
	Node_s * m_pRight;//右子树节点
	
	Node_s()//构造函数
	{
		m_value = 0;
		m_pLeft = nullptr;
		m_pRight = nullptr;
	}
};

/**
 * @brief 先序遍历
 * 
 * @param pTree 
 */
void LeftFirstTraversalRecursion(const Node_s* pTree)
{
	if (pTree)
	{
		if (pTree->m_pLeft)
		{
			LeftFirstTraversalRecursion(pTree->m_pLeft);
		}
		std::cout << "Node: " << pTree->m_value << std::endl;
		if (pTree->m_pRight)
		{
			LeftFirstTraversalRecursion(pTree->m_pRight);
		}
	}
}

/**
 * @brief 构造二叉树的一个节点
 * 
 * @return Node_s* 构造好的节点
 */
Node_s * CreateNode()
{
	std::cout << "请输入节点值(整数):";
	Node_s * pNode = new Node_s();
	std::cin >> pNode->m_value;
	return pNode;
}

/**
 * @brief 构造二叉树
 * 
 * @param pTree 
 * @return Node_s* 
 */
Node_s* CreateNodeTree(Node_s* pTree)
{
	if (pTree)
	{
		{
			int nChoice = 2;
			std::cout << "是否为节点 "<< pTree->m_value <<" 创建左子树(0---不创建,1---创建):";
			std::cin >> nChoice;
			if(1 == nChoice)
			{
				Node_s* pNode = CreateNode();
				pTree->m_pLeft = pNode;
				CreateNodeTree(pTree->m_pLeft);
			}
		}

		{
			int nChoice = 2;
			std::cout << "是否为节点 " << pTree->m_value << " 创建右子树(0---不创建,1---创建):";
			std::cin >> nChoice;
			if(1 == nChoice)
			{
				Node_s* pNode = CreateNode();
				pTree->m_pRight = pNode;
				CreateNodeTree(pTree->m_pRight);
				return pNode;
			}
		}

		return pTree;
	}
	else
	{
		Node_s* pNode = CreateNode();
		CreateNodeTree(pNode);
		return pNode;
	}
}

bool SearchLeftSubTree(const Node_s * pTree, const int nMaxValue);
bool SearchRightSubTree(const Node_s* pTree, const int nMinValue);


/**
 * @brief 判断二叉树的左子树是不是搜索二叉树
 * 
 * @param pTree 
 * @param nMaxValue 
 * @return true 
 * @return false 
 */
bool SearchLeftSubTree(const Node_s * pTree, const int nMaxValue)
{
	if (pTree)
	{
		bool bLeft = false;
		if (pTree->m_pLeft)
		{
			if (pTree->m_pLeft->m_value >= pTree->m_value)
			{
				bLeft = false;
			}
			else
			{
				bLeft = SearchLeftSubTree(pTree->m_pLeft, std::max(pTree->m_value, pTree->m_pLeft->m_value));
			}
		}
		else
		{
			bLeft = true;
		}

		bool bRight = false;
		if (pTree->m_pRight)
		{
			if (pTree->m_pRight->m_value < pTree->m_value || pTree->m_pRight->m_value > nMaxValue)
			{
				bRight = false;
			}
			else
			{
				bRight = SearchRightSubTree(pTree->m_pRight, std::max(pTree->m_value, nMaxValue));
			}
		}
		else
		{
			bRight = true;
		}
		return bLeft && bRight;
	}
	else
	{
		return true;
	}
}

/**
 * @brief 判断二叉树的右子树是不是搜索二叉树
 * 
 * @param pTree 
 * @param nMinValue 
 * @return true 
 * @return false 
 */
bool SearchRightSubTree(const Node_s * pTree, const int nMinValue)
{
	if (pTree)
	{
		bool bLeft = false;
		if (pTree->m_pLeft)
		{
			if (pTree->m_pLeft->m_value >= pTree->m_value || pTree->m_pLeft->m_value < nMinValue)
			{
				bLeft = false;
			}
			else
			{
				bLeft = SearchLeftSubTree(pTree->m_pLeft, std::max(pTree->m_value, pTree->m_pLeft->m_value));
			}
		}
		else
		{
			bLeft = true;
		}

		bool bRight = false;
		if (pTree->m_pRight)
		{
			if (pTree->m_pRight->m_value < pTree->m_value)
			{
				bRight = false;
			}
			else
			{
				bRight = SearchRightSubTree(pTree->m_pRight, std::min(pTree->m_value, nMinValue));
			}
		}
		else
		{
			bRight = true;
		}
		return bLeft && bRight;
	}
	else
	{
		return true;
	}
}

/**
 * @brief 判断某个二叉树是否为搜索二叉树
 * 
 * @param pTree 
 * @return true 
 * @return false 
 */
bool IsSearchBinaryTree(const Node_s* pTree)
{
	if (pTree)
	{
		bool bLeft = false;
		if (pTree->m_pLeft)
		{
			if (pTree->m_pLeft->m_value < pTree->m_value)
			{
				bLeft = SearchLeftSubTree(pTree->m_pLeft, pTree->m_value);
			}
			else
			{
				bLeft = false;
			}
		}
		else
		{
			bLeft = true;
		}

		bool bRight = false;
		if (pTree->m_pRight)
		{
			if (pTree->m_pRight->m_value > pTree->m_value)
			{
				bRight = SearchRightSubTree(pTree->m_pLeft, pTree->m_value);
			}
			else
			{
				bRight = false;
			}
		}
		else
		{
			bRight = true;
		}

		return bLeft && bRight;
	}
	else
	{
		return true;
	}
}

/**
 * @brief 主函数
 * 
 * @param argc 
 * @param argv 
 * @return int 
 */
int main(int argc,char* argv[])
{
	Node_s * pTree = CreateNodeTree(nullptr);
	LeftFirstTraversalNoRecursion(pTree);
	std::cout << "Is Search Tree" << IsSearchBinaryTree(pTree) << std::endl;
	return 0;
}