二叉搜索树的判断
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;
}