二叉树的递归和非递归层序遍历

非递归层序遍历二叉树

//非递归层序遍历 public void sequenceTraversal(){ //每一层加入队列的节点个数 int num=0; //当前层下一层的入队节点个数 int nextNum=0; //每一层已经遍历的节点个数 int alreadyNum=0; //存放节点的队列 Queue queue=new Queue(); //创建泛型为树节点的队列节点 QueueNode<TreeNode> queueNode=new QueueNode<>(); //声明树节点 TreeNode node=null; //为节点内容赋值 queueNode.setT(root); //先把根节点入队 queue.inQueue(queueNode); //更新各层在队列中的节点个数 num+=1; //遍历各层的树节点，若当前层存在下一层，就入队下一层的树节点 while (alreadyNum<num){ if(!queue.isNull()) { //出队当前层的队列节点 queueNode = queue.outQueue(); //获取当前层的树节点 node = queueNode.getT(); } /* 判断此节点是否有下一层节点 */ if(node!=null && node.getLeft()!=null){ //将此节点的左子节点入队 QueueNode<TreeNode> newQueueNode=new QueueNode<>(); newQueueNode.setT(node.getLeft()); queue.inQueue(newQueueNode); //更新当前层下一层的入队节点个数 nextNum+=1; } if(node!=null && node.getRight()!=null){ //将此节点的右子节点入队 QueueNode<TreeNode> newQueueNode=new QueueNode<>(); newQueueNode.setT(node.getRight()); queue.inQueue(newQueueNode); //更新当前层下一层的入队节点个数 nextNum+=1; } //输出当前节点的内容 System.out.println(node); //更新当前层已经遍历的节点数 alreadyNum+=1; //当前层的节点全部遍历完成 if(alreadyNum>=num){ //队列中还存在下一层的节点 if(!queue.isNull()) { //更新循环条件，使其继续遍历下一层 num = nextNum; alreadyNum = 0; //更新下一层队列中节点数为0 nextNum = 0; }else { //二叉树层序遍历完成 break; } } } }

递归层序遍历二叉树

//递归层序遍历对外提供的方法 public void recursionSequenceTraversal(){ //当前层的入队节点个数 int num=0; //把根节点入队 Queue queue=new Queue(); QueueNode<TreeNode> queueNode=new QueueNode<>(); queueNode.setT(root); queue.inQueue(queueNode); //更新num num+=1; //递归层序遍历 recursionSequenceTra(queue,num); } /* 层序遍历递归函数(遍历当前层的树节点并出队，若存在下一层，下一层的树节点入队) 参数： queue：存储树节点的队列 num：各层在队列中的树节点个数 */ private void recursionSequenceTra(Queue queue,int num){ //当前层下一层的入队节点个数 int nextNum=0; //接收出队树节点的对象 TreeNode node=null; /* 遍历各层的节点，并把下一层的节点加入队列 */ for(int i=0;i<num;i++){ //判断队列不为空则出队节点 if(!queue.isNull()) { //出队树节点 QueueNode<TreeNode> queueNode = queue.outQueue(); //获取树节点 node = queueNode.getT(); } /* 判断此节点是否有下一层节点 队列出队的最后一个节点为null，在条件中加入非空，防止空指针调用 */ if(node!=null && node.getLeft()!=null){ //将此节点的左子节点入队 QueueNode<TreeNode> newQueueNode=new QueueNode<>(); newQueueNode.setT(node.getLeft()); queue.inQueue(newQueueNode); //更新当前层下一层的入队节点个数 nextNum+=1; } if(node!=null && node.getRight()!=null){ //将此节点的右子节点入队 QueueNode<TreeNode> newQueueNode=new QueueNode<>(); newQueueNode.setT(node.getRight()); queue.inQueue(newQueueNode); //更新当前层下一层的入队节点个数 nextNum+=1; } //输出当前树节点中的内容 System.out.println(node); } //判断二叉树是否存在下一层 if(nextNum!=0){ //存在递归层序遍历下一层 recursionSequenceTra(queue,nextNum); } }