淘先锋技术网

首页 1 2 3 4 5 6 7

满二叉树是指在二叉树中,除最后一层外,每一层上的所有节点都有两个子节点。最后一层上的节点可以有一个或两个子节点。Java中可以使用类来实现满二叉树的数据结构。

public class FullBinaryTree {
Node root;
class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
left = null;
right = null;
}
}
public FullBinaryTree() {
root = null;
}
}

在满二叉树中,每一层都有2^(level-1)个节点,其中level表示层数(从1开始)。最大层数即是最后一层有节点的层数,可以通过递归遍历树来找到最大层数。

public int getMaxLevel(Node node) {
if (node == null)
return 0;
int leftMax = getMaxLevel(node.left);
int rightMax = getMaxLevel(node.right);
return Math.max(leftMax, rightMax) + 1;
}

以上代码使用递归来遍历二叉树,分别找到左子树和右子树的最大层数,然后比较两者的大小,并加1返回。最大层可以在创建满二叉树的时候就保存下来。