Question

利用层序遍历非递归地求解树的深度

Answer 1

  求解树的深度如果用递归的话那就很简单，思想就是树的深度等于左子树深度+1和右子树深度+1的最大值，这里不再赘述，但如果用非递归的话那就可以利用层序遍历了，这个算法是在王道的数据结构书上看到的。

接下来以这个图为例解释一下这个算法。

下面我们来进行循环：

进入循环前:front=-1,rear=0,level=0,last=0
第一次：front+1=0,rear+2=2,last=front=0,level+1=1,last=rear=2；A出队，BC入队。

第二次：front+1=1,rear+2=4,last=2!=front=1 ；本次B出队，DE入队。

第三次：front+1=2,rear=4,last=front=2,level+1=2,last=rear=4；本次C出队。

第四次：front+1=3,rear+1=5,last=4!=front=3；本次D出队，F入队。

第五次：front+1=4,rear=5,last=front=4,level+1=3,last=rear=5；本次E出队。

第六次：front+1=5,rear=5,last=front=5,level+1=4,last=rear=5；本次F出队。

  循环中的关键就是这个if语句，if(front==last)其实就是问这层的所有节点有没有都出队，如果都出队了，自然level+1，此时在进行last=rear操作前，rear-last的值其实就表示下一层的总节点数，因为此时该层的最后一个节点都出队了，那说明下一层的所有节点都已经进入了队中，rear-last(上一次循环的rear)就表示新进来的节点数即下一层的总节点数，所以要进行last=rear操作，使last指向该层的最后一个节点。循环结束时，树的深度自然就求出了。