用Java实现分层二叉树
时间: 2023-11-18 14:06:26 浏览: 37
分层二叉树是一种特殊的二叉树,每层节点数都是2的幂次方。以下是用Java实现分层二叉树的代码:
```java
class Node {
int val;
Node left, right;
public Node(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
class LayeredBinaryTree {
Node root;
public LayeredBinaryTree() {
root = null;
}
public void insert(int val) {
if (root == null) {
root = new Node(val);
return;
}
Node curr = root;
while (curr.left != null && curr.right != null) {
if (val <= curr.val) {
curr = curr.left;
} else {
curr = curr.right;
}
}
if (val <= curr.val) {
curr.left = new Node(val);
} else {
curr.right = new Node(val);
}
}
public void printLevelOrder() {
int h = height(root);
for (int i = 1; i <= h; i++) {
printLevel(root, i);
System.out.println();
}
}
public int height(Node node) {
if (node == null) {
return 0;
} else {
int lheight = height(node.left);
int rheight = height(node.right);
return Math.max(lheight, rheight) + 1;
}
}
public void printLevel(Node node, int level) {
if (node == null) {
return;
}
if (level == 1) {
System.out.print(node.val + " ");
} else if (level > 1) {
printLevel(node.left, level - 1);
printLevel(node.right, level - 1);
}
}
}
```
这里定义了一个Node类和LayeredBinaryTree类,Node类表示树中的节点,LayeredBinaryTree类表示分层二叉树。insert方法用于插入节点,printLevelOrder方法用于按层遍历并打印分层二叉树,height方法用于计算分层二叉树的高度,printLevel方法用于打印某一层的节点。