搜索二叉树的判断方法
二叉搜索树的判断
1. 二叉树
二叉树是指每个父节点有两个子节点的树。用图形化的描述如下:
2. 二叉搜索树
二叉搜索书是在二叉树的基础上,要求对于某个节点来说,所有小于该节点值的节点都在该节点的左子树上,所有大于该节点值的节点都在该节点的右子树上。
2.1 左子树存在大于某个父节点的值
2.2 右子树存在小于某个父节点的值
3. 判断方法
对于左右子树采用不同的函数来判断,接下来分别介绍。
3.1 左子树判断方法
当某节点为左子树节点的时候,其右子树节点可能大于该节点的父节点的情况,我们选择保存该节点和父节点的最大值传入判断函数。此时不仅要求该右子树节点的值大于当前节点,同时也需要小于该节点的父节点。
详细的信息参考该函数:
|
1 2 |
bool SearchLeftSubTree(const Node_s * pTree, const int nMaxValue) |
3.2 右子树判断方法
当某节点为右子树节点的时候,其左子树节点可能小于该节点的父节点的情况,我们选择保存该节点和父节点的最小值传入判断函数。此时不仅要求该左子树节点的值小于当前节点,同时也需要大于该节点的父节点。
详细的信息参考该函数:
|
1 2 |
bool SearchRightSubTree(const Node_s * pTree, const int nMinValue) |
4. 完整代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 |
/** * @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; } |