如何判断此矩阵是二进制搜索树还是二叉树.

Question

我试图回答以下问题,但我不确定矩阵是二进制搜索树还是二进制树.有什么方法可以说出来吗？

在二叉搜索树上找到两个节点之间的最不常见的祖先.最不常见的祖先是距离根最远的节点,它是两个节点的祖先.例如,根是树上所有节点的共同祖先,但如果两个节点都是根的左子节点的后代,则该左子节点可能是最低的共同祖先.您可以假设两个节点都在树中,并且树本身遵循所有BST属性.函数定义应该类似于question4(T,r,n1,n2),其中T是表示为矩阵的树,其中列表的索引等于存储在该节点中的整数,1表示子节点, r是表示根的非负整数,n1和n2是非负整数,表示两个节点没有特定的顺序.例如,一个测试用例可能是

question4([[0, 1, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[1, 0, 0, 0, 1],
[0, 0, 0, 0, 0]],
3,
1,
4)

Answer 1

我认为,矩阵代表下图:

矩阵应如下所示:

0 1 0 0 0
0 0 0 0 0
0 0 0 0 0
1 0 0 0 1
0 0 0 0 0

行0代表节点0.它有一个1at索引1,即节点1是节点的子节点0.相同的方法应该适用于其他行.例如,节点0和节点4是节点的子节点3.

要检查图形是否为树,请执行以下操作:树中的每个节点(根除外)只有一个父节点.因此,您需要确保矩阵中的所有列都只有一个1条目(根列除外,它应该没有1条目).

要检查树是否是二叉树,您需要检查节点最多是否有两个子节点.您可以通过检查每行是否最多包含两个1条目来执行此操作.

要检查二叉树是否为二叉搜索树,您必须检查每个子树中是否至多有一个子节点.即,在行中i,1条目中最多一个条目,条目[0 .. i-1]中最多一个1条目[i+1 .. n-1].正如greybeard指出的那样,这种情况还不够,因为它不考虑更高级别的祖先.要检查这一点,您需要构造树并从根遍历到叶子,检查节点是否落在允许的间隔内.