如何判断一颗二叉树中的结点所在的深度

（设根节点的深度为1）

在一棵二叉链表表示的二叉树中，求结点的深度。

设这样的一颗二叉树，深度为4，假设就D这个结点所在的深度

---

首先判断他的根节点是否为空，若为空，则报空指针异常；

定义一个队列将他的根节点放入，随后加上一个标志位"#",表示这一行的结点已经遍历完毕，由于根节点已经进入队列，所以令level = 1；

随后进入循环，判断这个队列是否为空，如果队列为该标志位，则终止循环，如果队列不为空，则执行下列循环；

队列结点出队，如果说出队的结点为为该标志位并且队列不为空（如果队列为空，则表示他的遍历已经结束），则level + 1，并且把该标志位重新放入队列中，如果出队的结点不是该标志位，则判断他的左右孩子是否为空，若不为空，则把该结点的左右孩子放入队列中，如果遍历到的结点为想要求结点层数的结点，则直接跳出循环，输出该值。

---

代码实现如下：

/** * 判断该结点所在的层数，利用层序遍历的方法 * * @param node 树结点 */ public void level(T node) { if (null == root) throw new NullPointerException("x == null"); ArrayDeque<BinaryNode<T>> que = new ArrayDeque<>(); BinaryNode<T> p = null; BinaryNode<T> emp = new BinaryNode<T>((T)"#"); que.offer(this.root); que.offer(emp); int level = 1; while (!que.isEmpty()) { p = que.pop(); if(p.data.equals(emp.data)){ if (que.isEmpty()) break; que.offer(emp); level++; } if(p.left != null ) que.offer(p.left); if(p.right != null) que.offer(p.right); if (p.data.equals(node)) break; } System.out.println(level); }

测试类如下：

public static void main(String[] args) { // 声明一个数组，带空结点描述的二叉树的前序遍历 String[] prelist_1 = { "A", "B", "D", null, "G", null, null, null, "C", "E", null, null, "F", "H", null, null, null }; // 声明一个二叉树对象，将声明的数组传入进去 BinaryTree<String> bitee_1 = new BinaryTree<> (prelist_1); System.out.print ("此树的结点的深度："); bitee_1.level("B"); }

运行结果