每个节点有3个子节点，按序（从上往下，从左往右）存入数据库（理解为数组也行）。
-----------------------------------------------------------------------------------------------------------------------
L1 1
-----------------------------------------------------------------------------------------------------------------------
L2 2 3 4
-----------------------------------------------------------------------------------------------------------------------
L3 5 6 7 8 9 10 11 12 13
-----------------------------------------------------------------------------------------------------------------------
L4 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
-----------------------------------------------------------------------------------------------------------------------
现在，给定一个节点ID，如何计算出该节点在树的第几层。
/**
* @param nodeId 节点ID
* @param nodes 节点列表
* @return
*/
public static int level(int nodeId, int[] nodes) {
// TODO 检索出 nodeId 在三叉树的第几层
return -1;
}
Suc
2
public class TernaryTree {
public static int findNumberLevel(Node root, int target) {
int level = 1;
Node current = root;
while (current != null) {
if (current.getValue() == target) {
return level;
} else if (target < current.getValue()) {
current = current.getLeft();
} else if (target > current.getValue()) {
current = current.getRight();
} else {
current = current.getMiddle();
}
level++;
}
return -1; // 如果找不到目标数字，返回一个特殊值 -1 表示数字不在树中。
}
public static void main(String[] args) {
// 创建一个三叉树并初始化节点
Node root = new Node(5);
Node left = new Node(2);
Node middle = new Node(4);
Node right = new Node(8);
root.setLeft(left);
root.setMiddle(middle);
root.setRight(right);
left.setLeft(new Node(1));
left.setMiddle(new Node(3));
middle.setLeft(new Node(6));
middle.setMiddle(new Node(7));
right.setLeft(new Node(9));
right.setRight(new Node(10));
int target = 6;
int level = findNumberLevel(root, target);
if (level != -1) {
System.out.println("The level of number " + target + " is " + level);
} else {
System.out.println("Number " + target + " is not in the tree.");
}
}
}
class Node {
private int value;
private Node left;
private Node middle;
private Node right;
public Node(int value) {
this.value = value;
}
public int getValue() {
return value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getMiddle() {
return middle;
}
public void setMiddle(Node middle) {
this.middle = middle;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
Suc
3
数组到三叉树
public class TernaryTree {
public static Node buildTernaryTree(int[] array, int start, int end) {
if (start > end) {
return null;
}
int middle1 = start + (end - start) / 3;
int middle2 = start + 2 * (end - start) / 3;
Node node = new Node(array[middle1]);
node.setLeft(buildTernaryTree(array, start, middle1 - 1));
node.setMiddle(buildTernaryTree(array, middle1 + 1, middle2 - 1));
node.setRight(buildTernaryTree(array, middle2 + 1, end));
return node;
}
public static void main(String[] args) {
int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
Node root = buildTernaryTree(array, 0, array.length - 1);
// ...
}
}
class Node {
private int value;
private Node left;
private Node middle;
private Node right;
public Node(int value) {
this.value = value;
}
public int getValue() {
return value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getMiddle() {
return middle;
}
public void setMiddle(Node middle) {
this.middle = middle;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
1 个赞