【Java实现】判断一棵树是否为BST,一棵树是否为完全二叉树

时间:2022-08-26 20:50:10

给定一个二叉树,判断它是不是二叉搜索树。

思路:对于一棵二叉树,最简单的方法就是中序遍历,看是不是一个递增数列,如果是,则是一棵二叉搜索树,如果不是,则不是二叉搜索树。在这里用一个lastVisit去记录上一次搜索的节点。这个过程就是先找到最左下角的节点,更新lastVisit为这个节点的值,然后按照中序遍历依次更新即可。

代码

class Node {
int data;
Node left;
Node right;
}
public class BSTChecker {
private static int lastVisit = Integer.MIN_VALUE;

public static boolean isBST(Node root) {
if(root == null) return true;

boolean judgeLeft = isBST(root.left); // 先判断左子树

if(root.data >= lastVisit && judgeLeft) { // 当前节点比上次访问的数值要大
lastVisit = root.data;
} else {
return false;
}

boolean judgeRight = isBST(root.right); // 后判断右子树

return judgeRight;
}
}

给定一棵二叉树,判断它是不是一棵完全二叉树。

思路:对于一棵完全二叉树采用广度优先遍历,从根节点开始,入队列,如果队列不为空,循环。遇到第一个没有左儿子或者右儿子的节点,设置标志位,如果之后再遇到有左儿子或者右儿子的节点,那么这不是一棵完全二叉树。这个方法需要遍历整棵树,复杂度为O(N),N为节点的总数。

代码

import java.util.LinkedList;

class Node {
int data;
Node left;
Node right;
}

public class CompleteTreeChecker {
//实现广度遍历需要的队列
private LinkedList<Node> queue = new LinkedList<Node>();
//第n层最右节点的标志
private boolean leftMost = false;

public boolean processChild(Node child) {
if(child != null) {
if(!leftMost) {
queue.addLast(child);
} else {
return false;
}
} else {
leftMost = true;
}
return true;
}

public boolean isCompleteTree(Node root) {
//空树也是完全二叉树
if(root == null) return true;

//首先根节点入队列
queue.addLast(root);

while(!queue.isEmpty()) {
Node node = queue.removeFirst();

//处理左子结点
if(!processChild(node.left))
return false;
//处理右子结点
if(!processChild(node.right))
return false;
}

//广度优先遍历完毕,此树是完全二叉树
return true;
}
}