二叉树的四种遍历方式:
- 二叉树的遍历(traversing binary tree)是指从根结点出发,按照某种次序依次访问二叉树中所有的结点,使得每个结点被访问依次且仅被访问一次。
四种遍历方式分别为:先序遍历、中序遍历、后序遍历、层序遍历。
遍历之前,我们首先介绍一下,如何创建一个二叉树,在这里用的是先建左树在建右树的方法,
首先要声明结点treenode类,代码如下:
1
2
3
4
5
6
7
8
|
public class treenode { public int data; public treenode leftchild; public treenode rightchild; public treenode( int data){ this .data = data; } } |
再来创建一颗二叉树:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
/** * 构建二叉树 * @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
实现代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
|
/** * 二叉树前序遍历 根-> 左-> 右 * @param node 二叉树节点 */ public static void preordertraveral(treenode node){ if (node == null ){ return ; } system.out.print(node.data+ " " ); preordertraveral(node.leftchild); preordertraveral(node.rightchild); } |
再者就是中序遍历,所谓的中序遍历就是先访问左节点,再访问根节点,最后访问右节点,
如上图所示,中序遍历结果为:
dbefaghci
实现代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
|
/** * 二叉树中序遍历 左-> 根-> 右 * @param node 二叉树节点 */ public static void inordertraveral(treenode node){ if (node == null ){ return ; } inordertraveral(node.leftchild); system.out.print(node.data+ " " ); inordertraveral(node.rightchild); } |
最后就是后序遍历,所谓的后序遍历就是先访问左节点,再访问右节点,最后访问根节点。
如上图所示,后序遍历结果为:
defbhgica
实现代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
|
/** * 二叉树后序遍历 左-> 右-> 根 * @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为空.
实现代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
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为空时结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
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; } } } |
后序遍历非递归实现,后序遍历这里较前两者实现复杂一点,我们需要一个标记位来记忆我们此时节点上一个节点,具体看代码注释
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
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为空。
实现代码如下:
1
2
3
4
5
6
7
8
9
10
|
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); } } |
总结
本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注服务器之家的更多内容!
原文链接:https://www.cnblogs.com/du001011/p/11229170.html