判断给定的二叉树是否为二分查找树。假设树的每个节点以整数为键值,且不同节点的键值互不相等。二分查找树成立的判定条件:
对任何非叶子节点A,如果A存在左子树,则A的键值大于其左子树所有节点的键值,且,如果A存在右子树,则A的键值小于其右子树所有节点的键值
判断给定的二叉树是否为二分查找树。假设树的每个节点以整数为键值,且不同节点的键值互不相等。二分查找树成立的判定条件:
对任何非叶子节点A,如果A存在左子树,则A的键值大于其左子树所有节点的键值,且,如果A存在右子树,则A的键值小于其右子树所有节点的键值
第一行:根节点键值;
第二行开始,二叉树的结构,每行代表一组根节点与左右子节点的对应关系,-1代表空节点。格式:
根节点键值:左子节点键值|右子节点键值
例如,
5:3|-1
表示键值为5的节点,左子节点的键值为3,右子节点为空节点
假设:所有节点的键值非负,且不超过1023
判断结果,0表示输入不是二分查找树,1表示输入是二分查找树
5 5:4|7 4:3|8 7:2|-1 3:-1|-1 8:-1|-1 2:-1|-1
0
#include <stdio.h> #include <stdlib.h> #define INF 0x3F3F3F3F #define IsValidBST(infos, key) __IsValidBST(infos, key, -INF, +INF) // ========== 二叉树节点信息表 ========== typedef int Key; typedef struct { Key key; Key l_child, r_child; } BST_NODE_INFO, *INFO; // ========== 二叉树节点信息表 ========== int __IsValidBST(INFO infos, Key key, Key low, Key high) { if (key == -1) return 1; return key > low && key < high && __IsValidBST(infos, (infos + key)->l_child, low, key) && __IsValidBST(infos, (infos + key)->r_child, key, high); } int main(const int argc, const char* const argv[]) { BST_NODE_INFO infos[1000]; Key root_key; fscanf(stdin, "%d", &root_key); Key fa, l_ch, r_ch; while (fscanf(stdin, "%d:%d|%d", &fa, &l_ch, &r_ch) != EOF) { (infos + fa)->key = fa; (infos + fa)->l_child = l_ch; (infos + fa)->r_child = r_ch; } return fprintf(stdout, "%d\n", IsValidBST(infos, root_key)), 0; }