二叉树的广度优先遍历和深度优先遍历(Java版)
程序员文章站
2022-05-21 19:28:29
...
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int x){val=x;}
}
public class Main {
static List<Integer> BFSList=new ArrayList<>();
static List<Integer> DFSList=new ArrayList<>();
public static void main(String[] args) {
TreeNode root=new TreeNode(1);
TreeNode second=new TreeNode(2);
TreeNode three=new TreeNode(3);
TreeNode four=new TreeNode(4);
TreeNode five=new TreeNode(5);
TreeNode six=new TreeNode(6);
TreeNode seven=new TreeNode(7);
root.right=three;
root.left=second;
second.right=five;
second.left=four;
three.right=seven;
three.left=six;
BFS(root);
DFS(root);
System.out.print("广度优先遍历结果:");
printList(1);
System.out.println();
System.out.print("深度优先遍历结果:");
printList(2);
}
public static void BFS(TreeNode root)
{
if(root==null)
return;
//广度优先遍历使用队列实现
Queue<TreeNode> queue=new LinkedList<>();//使用LinkedList来实现队列
queue.add(root);//将根结点入队
while (!queue.isEmpty())
{
//如果队列元素不为空,则进行出队操作
TreeNode node=queue.poll();
/*poll返回当前删除的节点,若为空则返回null。也可以用remove,若为空,则抛出异常"NoSuchElementException"
*/
BFSList.add(node.val);//保存当前遍历结点的值
if(node.left!=null)
queue.add(node.left);
if(node.right!=null)
queue.add(node.right);
}
}
public static void DFS(TreeNode root)
{
if(root==null)
return;
//深度优先遍历使用栈实现
Stack<TreeNode> stack=new Stack<TreeNode>();
stack.add(root);//将根结点入栈
//如果栈元素不为空,则进行出出栈操作
while (!stack.isEmpty())
{
TreeNode node=stack.pop();
DFSList.add(node.val);
if(node.right!=null)
stack.push(node.right);
if(node.left!=null)
stack.push(node.left);
}
}
public static void printList(int flag)
{
//打印广度优先遍历结果
if(flag==1)
{
for(int i=0;i<BFSList.size();i++)
{
System.out.print(BFSList.get(i)+" ");
}
}
//打印广度优先遍历结果
else if(flag==2)
{
for(int i=0;i<DFSList.size();i++)
{
System.out.print(DFSList.get(i)+" ");
}
}
else
return;
}
}
上一篇: 二叉树深度优先和广度优先的两种遍历方式
下一篇: 广度优先遍历和深度优先遍历
推荐阅读