Java二叉树的四种遍历方式详解
二叉树的四种遍历方式：
- 二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被访问依次且仅被访问一次。
四种遍历方式分别为：先序遍历、中序遍历、后序遍历、层序遍历。
遍历之前，我们首先介绍一下，如何创建一个二叉树，在这里用的是先建左树在建右树的方法，
首先要声明结点treenode类，代码如下：
public class treenode {
public int data;
public treenode leftchild;
public treenode rightchild;
public treenode(int data){
this.data = data;
}
}
再来创建一颗二叉树：
/**
* 构建二叉树
* @param list 输入序列
* @return
*/
public static treenode createbinarytree(linkedlist<integer> list){
treenode node = null;
if(list == null || list.isempty()){
return null;
}
integer data = list.removefirst();
if(data!=null){
node = new treenode(data);
node.leftchild = createbinarytree(list);
node.rightchild = createbinarytree(list);
}
return node;
}
接下来按照上面列的顺序一一讲解，
首先来看前序遍历，所谓的前序遍历就是先访问根节点，再访问左节点，最后访问右节点，
如上图所示，前序遍历结果为：
abdfecghi
实现代码如下：
/**
* 二叉树前序遍历 根-> 左-> 右
* @param node 二叉树节点
*/
public static void preordertraveral(treenode node){
if(node == null){
return;
}
system.out.print(node.data+" ");
preordertraveral(node.leftchild);
preordertraveral(node.rightchild);
}
再者就是中序遍历，所谓的中序遍历就是先访问左节点，再访问根节点，最后访问右节点，
如上图所示，中序遍历结果为：
dbefaghci
实现代码如下：
/**
* 二叉树中序遍历 左-> 根-> 右
* @param node 二叉树节点
*/
public static void inordertraveral(treenode node){
if(node == null){
return;
}
inordertraveral(node.leftchild);
system.out.print(node.data+" ");
inordertraveral(node.rightchild);
}
最后就是后序遍历，所谓的后序遍历就是先访问左节点，再访问右节点，最后访问根节点。
如上图所示，后序遍历结果为：
defbhgica
实现代码如下：
/**
* 二叉树后序遍历 左-> 右-> 根
* @param node 二叉树节点
*/
public static void postordertraveral(treenode node){
if(node == null){
return;
}
postordertraveral(node.leftchild);
postordertraveral(node.rightchild);
system.out.print(node.data+" ");
}
讲完上面三种递归的方法，下面再给大家讲讲非递归是如何实现前中后序遍历的
还是一样，先看非递归前序遍历
1.首先申请一个新的栈，记为stack；
2.声明一个结点treenode，让其指向node结点；
3.如果treenode的不为空，将treenode的值打印，并将treenode入栈，然后让treenode指向treenode的右结点，
4.重复步骤3，直到treenode为空；
5.然后出栈，让treenode指向treenode的右孩子
6.重复步骤3，直到stack为空.
实现代码如下：
public static void preordertraveralwithstack(treenode node){
stack<treenode> stack = new stack<treenode>();
treenode treenode = node;
while(treenode!=null || !stack.isempty()){
//迭代访问节点的左孩子，并入栈
while(treenode != null){
system.out.print(treenode.data+" ");
stack.push(treenode);
treenode = treenode.leftchild;
}
//如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子
if(!stack.isempty()){
treenode = stack.pop();
treenode = treenode.rightchild;
}
}
}
中序遍历非递归，在此不过多叙述具体步骤了，
具体过程：
1.申请一个新栈，记为stack，申请一个变量cur，初始时令treenode为头节点；
2.先把treenode节点压入栈中，对以treenode节点为头的整棵子树来说，依次把整棵树的左子树压入栈中，即不断令treenode=treenode.leftchild，然后重复步骤2；
3.不断重复步骤2，直到发现cur为空，此时从stack中弹出一个节点记为treenode，打印node的值，并让treenode= treenode.right，然后继续重复步骤2；
4.当stack为空并且cur为空时结束。
public static void inordertraveralwithstack(treenode node){
stack<treenode> stack = new stack<treenode>();
treenode treenode = node;
while(treenode!=null || !stack.isempty()){
while(treenode != null){
stack.push(treenode);
treenode = treenode.leftchild;
}
if(!stack.isempty()){
treenode = stack.pop();
system.out.print(treenode.data+" ");
treenode = treenode.rightchild;
}
}
}
后序遍历非递归实现，后序遍历这里较前两者实现复杂一点，我们需要一个标记位来记忆我们此时节点上一个节点，具体看代码注释
public static void postordertraveralwithstack(treenode node){
stack<treenode> stack = new stack<treenode>();
treenode treenode = node;
treenode lastvisit = null; //标记每次遍历最后一次访问的节点
while(treenode!=null || !stack.isempty()){//节点不为空，结点入栈，并且指向下一个左孩子
while(treenode!=null){
stack.push(treenode);
treenode = treenode.leftchild;
}
//栈不为空
if(!stack.isempty()){
//出栈
treenode = stack.pop();
/**
* 这块就是判断treenode是否有右孩子，
* 如果没有输出treenode.data，让lastvisit指向treenode，并让treenode为空
* 如果有右孩子，将当前节点继续入栈，treenode指向它的右孩子,继续重复循环
*/
if(treenode.rightchild == null || treenode.rightchild == lastvisit) {
system.out.print(treenode.data + " ");
lastvisit = treenode;
treenode = null;
}else{
stack.push(treenode);
treenode = treenode.rightchild;
}
}
}
}
最后再给大家介绍一下层序遍历
具体步骤如下：
1.首先申请一个新的队列，记为queue；
2.将头结点head压入queue中；
3.每次从queue中出队，记为node，然后打印node值，如果node左孩子不为空，则将左孩子入队；如果node的右孩子不为空，则将右孩子入队；
4.重复步骤3，直到queue为空。
实现代码如下：
public static void levelorder(treenode root){
linkedlist<treenode> queue = new linkedlist<>();
queue.add(root);
while(!queue.isempty()){
root = queue.pop();
system.out.print(root.data+" ");
if(root.leftchild!=null) queue.add(root.leftchild);
if(root.rightchild!=null) queue.add(root.rightchild);
}
}
总结
本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注的更多内容！