java编程判断一棵二叉树是否为二叉排序树。 实验要求 ⑴ 二叉树采用二叉链表作为存储结构,且树中结点的关键字均不相同。 ⑵ 要输出最后的判断结果。并输出运行结果
时间: 2024-05-27 11:13:32 浏览: 69
//该程序用于判断二叉树是否为二叉排序树
好的,您的问题是如何判断一棵二叉树是否为二叉排序树。以下是 Java 编程实现:
// 定义二叉树节点结构体
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Main {
// 判断是否为二叉排序树
public static boolean isValidBST(TreeNode root) {
return isValidBSTHelper(root, null, null);
}
// 辅助函数,使用min和max约束范围
public static boolean isValidBSTHelper(TreeNode node, Integer min, Integer max) {
if (node == null) return true;
int val = node.val;
if (min != null && val <= min) return false;
if (max != null && val >= max) return false;
if (!isValidBSTHelper(node.left, min, val)) return false;
if (!isValidBSTHelper(node.right, val, max)) return false;
return true;
}
public static void main(String[] args) {
// 构造一棵二叉搜索树,注意结点的关键字要均不相同
//
// 5
// / \
// 2 7
// / \ / \
// 1 4 6 8
//
TreeNode root = new TreeNode(5);
root.left = new TreeNode(2);
root.right = new TreeNode(7);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(4);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(8);
boolean result = isValidBST(root);
System.out.println("该二叉树是否为二叉排序树:" + result);
}
}
运行结果如下:
该二叉树是否为二叉排序树:true
阅读全文