三叉树，存储在数组中，如何根据节点ID，查询出该节点在树的第几层

技术交流
1

每个节点有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;
	}
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;
    }
}
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 Like