判别给定的二叉树是否是二叉树

判断给定的二叉树是否是二叉搜索树的方法有多种，以下是其中一种常见的方法：

1. 对于每个节点，其左子树中的所有节点都小于该节点的值，右子树中的所有节点都大于该节点的值。
2. 递归地检查每个节点的左子树和右子树是否满足上述条件。

具体步骤如下：
1. 如果二叉树为空，则返回True。
2. 如果二叉树只有一个节点，则返回True。
3. 对于每个节点，检查其左子树中的所有节点是否小于该节点的值，右子树中的所有节点是否大于该节点的值。
4. 递归地检查每个节点的左子树和右子树是否满足上述条件。

如果以上条件都满足，则给定的二叉树是二叉搜索树，否则不是。

相关问题

编写算法判别给定二叉树是否为完全二叉树。

### 回答1：
判断一棵二叉树是否为完全二叉树的算法如下：

1. 如果二叉树为空，则是完全二叉树。

2. 如果二叉树不为空，但是左子树为空，右子树不为空，则不是完全二叉树。

3. 如果二叉树不为空，但是左子树不为空，右子树为空，则只有当左子树为叶子节点或者是满二叉树时，才是完全二叉树。

4. 如果二叉树不为空，左右子树都不为空，则需要递归判断左右子树是否为完全二叉树。

5. 如果左右子树都是完全二叉树，且左子树的高度等于右子树的高度或者左子树的高度比右子树的高度小1，则该二叉树是完全二叉树，否则不是完全二叉树。

以上就是判断一棵二叉树是否为完全二叉树的算法。

### 回答2：
一棵完全二叉树的特点有：

1. 如果树的深度为d，除了第d层，其他各层的节点数都达到了最大个数，第d层所有的节点都连续集中在最左边；

2. 如果该树的右子树不为空，那么右子树的每个节点都必须具有两个子节点，否则该树不是完全二叉树。

基于这两个特点，我们可以设计算法来判定一棵二叉树是否为完全二叉树。

首先，我们需要用广度优先搜索(BFS)来遍历这棵二叉树。从根节点出发，按照从上到下、从左到右的顺序，依次访问每个节点。如果当前节点有左子节点但没有右子节点，那么该树不是完全二叉树。因为在完全二叉树中，如果一个节点有左子节点却没有右子节点，那么该节点的右边所有节点都必须不存在。

如果当前节点有右子节点但没有左子节点，或者左右子节点都不存在，那么它以后的所有节点都必须是叶子节点，否则该树也不是完全二叉树。因为在完全二叉树中，如果一个节点存在右子节点却不存在左子节点，或者左右子节点都不存在，那么该节点的左边节点应该达到最大个数，而其右边节点都不存在。

最后，如果BFS遍历完整棵树，都没有遇到以上两种情况，那么该树是完全二叉树。

算法的核心是用BFS遍历整个树，时间复杂度为O(n)，其中n为节点数目。因此，该算法是高效的，可以在不占用过多空间的情况下(空间复杂度为O(n))快速判定一棵树是否为完全二叉树。

### 回答3：
什么是完全二叉树

在二叉树中，如果所有的叶子节点都出现在最后一层或者倒数第二层，并且最后一层的叶子节点都集中在左边，那么这棵二叉树就是完全二叉树。

如何判断一棵二叉树是否为完全二叉树

在判断完全二叉树时，我们可以使用以下的算法：

1.首先，我们需要计算出树的总结点数。

2.接着，我们需要遍历二叉树的每个节点，逐一进行如下的判断：

• 如果一个节点的序号等于n，那么它的左节点的序号为2n，右节点的序号为2n+1。

• 如果当前节点的序号等于n，但是它的左节点或右节点的序号大于总结点数，那么它就不是完全二叉树。

• 如果当前节点的左节点为null，但是右节点不为null，那么它也不是完全二叉树。

3.如果二叉树中的所有节点都满足以上条件，则这棵二叉树为完全二叉树。

代码实现

以下是一个Java实现的示例代码：

public boolean isComplete(TreeNode root) {
if (root == null) {
return true;
}
int nodes = DFS(root, 1);
return DFS2(root, nodes, 1);
}

private int DFS(TreeNode node, int index) {
if (node == null) {
return index - 1;
}
int left = DFS(node.left, 2 * index);
int right = DFS(node.right, 2 * index + 1);
return left > right ? left : right;
}

private boolean DFS2(TreeNode node, int nodes, int index) {
if (node == null) {
return true;
}
if (index > nodes) {
return false;
}
return DFS2(node.left, nodes, 2 * index) && DFS2(node.right, nodes, 2 * index + 1);
}

其中，DFS函数用于计算树的总结点数，DFS2用于判断二叉树是否为完全二叉树。这个算法的时间复杂度为O(N)，其中N为二叉树节点的数量。

判别给定二叉树是否为二叉排序树的算法

判断给定二叉树是否为二叉排序树的算法如下：

1. 如果二叉树为空，则返回 true。

2. 如果二叉树不为空，则判断其左子树是否为二叉排序树，如果不是，则返回 false。

3. 判断当前节点是否大于其左子树的最大值，如果不是，则返回 false。

4. 判断当前节点是否小于其右子树的最小值，如果不是，则返回 false。

5. 判断其右子树是否为二叉排序树，如果不是，则返回 false。

6. 如果以上条件都满足，则返回 true。

其中，判断一个二叉树是否为二叉排序树，需要用到中序遍历，即先遍历左子树，再遍历根节点，最后遍历右子树。如果遍历的结果是一个递增的序列，则该二叉树为二叉排序树。