java二叉树的遍历方式详解
更新时间是在2021年08月16日, 具体的时间点为09:48:12。
这篇文章的主要内容, 是为广大的朋友们去详细地介绍一下, 使用JAVA这个编程语言来实现二叉树的遍历的这个事情, 它一共有四种方式, 这种做法是具有一定的参考的价值意义的, 那些对这种内容感兴趣的小伙伴们, 是可以去参考看一看的, 希望能够给到你带来一些切实的帮助。
一、对于前序遍历这一点, 大家可以把它分成递归的情况还有非递归的情形来讲一讲。
前序遍历就是先遍历根再遍历左之后是右 根左右
递归实现：
public List preorderTraversal(TreeNode root) {
List list=new ArrayList<>();
pre(root,list);
return list;
}
public void pre(TreeNode root,List list){
if(root==null){
return ;
}
list.add(root.val);
pre(root.left,list);
pre(root.right,list);
}
迭代实现：
我们可以使用栈这种数据结构来完成操作, 具体的做法是先让把树的右子树放进堆栈里面去, 然后下一步再把左子树也放进去。
public List preorderTraversal(TreeNode root) {
List list=new LinkedList<>();
if(root==null) return list;
Stack stack=new Stack<>();
stack.push(root);
while(!
stack.isEmpty()){
TreeNode node=stack.pop();
list.add(node.val);
if(node.right!
=null) stack.push(node.right);
if(node.left!=null) stack.push(node.left);
}
return list;
}
二、中序遍历（递归和非递归）
中序遍历就是先遍历左再遍历根，最后遍历右 左根右
递归实现：
public List inorderTraversal(TreeNode root) {
List list=new ArrayList<>();
inorder(root,list);
return list;
}
public void inorder(TreeNode root,List list){
if(root==null){
return ;
}
inorder(root.left,list);
list.add(root.val);
inorder(root.right,list);
}
迭代实现
我们可以利用栈来实现二叉树的中序遍历, 因为中序遍历的规则是左根右, 所以第一步就是先定义好节点并且找到最靠左的那个节点把它压入栈中, 接下来就把这个节点弹出栈来检查它。在判断完之后我们再继续看看该节点是不是存在有右孩子的情况。
public List inorderTraversal(TreeNode root) {
//迭代实现
List list =new LinkedList<>();
Stack stack=new Stack<>();
TreeNode cur=root;
while(cur!
=null||!stack.isEmpty()){
//先找到左节点
while(cur!
=null){
stack.push(cur);
cur=cur.left;
}
TreeNode node=stack.pop();
list.add(node.val);
if(node.right!
=null){
cur=node.right;
}
}
return list;
}
三、后序遍历这种操作, 它包含递归的写法, 也包含非递归的写法。
后序遍历就是左右根
递归实现：
public List postorderTraversal(TreeNode root) {
List list=new ArrayList<>();
postorder(root,list);
return list;
}
public void postorder(TreeNode root,List list){
if(root==null){
return ;
}
postorder(root.left,list);
postorder(root.right,list);
list.add(root.val);
}
非递归实现：
使用两个栈, 这样才能够完成对二叉树的后序遍历这个任务。
先把第一个栈里面放入根节点, 然后弹出它并且放入第二个节点这里所说的位置或者状态中, 接着再把左右孩子放入第一个栈里, 之后再次弹出这些内容并放入第二个栈里面, 如此操作就可以实现了。
public List postorderTraversal(TreeNode root) {
//利用双栈实现后序遍历
Stack s1=new Stack<>();
Stack s2=new Stack<>();
List list=new LinkedList<>();
if(root==null) return list;
s1.push(root);
while(!
s1.isEmpty()){
TreeNode node=s1.pop();
s2.push(node);
if(node.left!
=null) s1.push(node.left);
if(node.right!=null) s1.push(node.right);
}
while(!
s2.isEmpty()){
TreeNode cur=s2.pop();
list.add(cur.val);
}
return list;
}
四、层序遍历
通过使用队列这个手段来完成层序遍历这样的操作。
public List> levelOrder(TreeNode root) {
//用队列实现层序遍历
//第一层节点先进队列，出的节点带下一层的节点
List > list=new ArrayList<>();
if(root==null) return list;
Queue queue=new LinkedList<>();
queue.offer(root);
while(!
queue.isEmpty()){
List list1=new ArrayList<>();
int size=queue.size();
while(size!
=0){
TreeNode cur=queue.poll();
list1.add(cur.val);
if(cur.left!
=null){
queue.offer(cur.left);
}
if(cur.right!
=null){
queue.offer(cur.right);
}
size--;
}
list.add(list1);
}
return list;
}
