二叉树的遍历方式有很多,今天就来一一列举并且实现一下。
二叉树基本遍历分别用递归和非递归的方式进行实现,层序遍历我们需要使用一下栈和队列,所有的代码使用Java实现
前期工作
public class TreeNode { public int value; public TreeNode left; public TreeNode right; public TreeNode(int value) { this.value = value; } }
|
- 准备一个二叉树的插入算法,方便进行遍历的检验,插入的时候构建一个二叉查找树(至于啥是二叉查找树,请自行百度)
public class TreeNodeTool { public static TreeNode InsertTreeNode(TreeNode root,int value) { if(root==null) { root = new TreeNode(value); } else { TreeNode p = root; TreeNode parent = null; while (p!=null) { if(value < p.value) { parent = p; p=p.left; } else if(value>p.value) { parent = p; p = p.right; } else { return root; } } if (value < parent.value) { parent.left = new TreeNode(value); } else { parent.right = new TreeNode(value); } } return root; } }
|
前序遍历(DLR)
前序遍历就是先遍历根节点,然后前序遍历右子树,前序遍历左子树
定义里面就包含着递归的思想,但是任何递归都可以写成迭代的方式,所以以下提供两种方式进行前序遍历的编写
递归形式
public static void PreorderRecur(TreeNode root) { if(root==null) return; else { System.out.print(root.value+ " "); PreorderRecur(root.left); PreorderRecur(root.right); } }
|
非递归形式
利用栈来实现循环,首先跟节点入栈,进入while循环,循环条件是栈不为空,循环内,
- 根节点出栈输出
- 右子树入栈
- 左子树入栈
- 这样输出的时候就能够实现前序遍历
public static void PreorderRecur(TreeNode root) { if(root!=null) { Stack<TreeNode> s = new Stack<>(); s.push(root); while (!s.empty()) { TreeNode node = s.peek(); System.out.print(s.pop().value + " "); if(node.right!=null) { s.push(node.right); } if(node.left!=null) { s.push(node.left); } } } }
|
中序遍历 (LDR)
前序遍历就是中遍历左子树,然后根节点,中序遍历右子树
递归方式
public static void InorderRecur(TreeNode root) { if(root==null) return; else { InorderRecur(root.left); System.out.print(root.value+ " "); InorderRecur(root.right); } }
|
非递归方式
循环条件(栈不空||根节点不空){ 如果(根不空) 根入栈 根节点指向左子树 否则 根节点指向栈顶 出栈输出 根节点指向右子树}
所谓中序遍历,就是先遍历左子树,然后根节点,最后中序遍历右子树,所以我们应该先去让跟节点入栈,然后遍历左子树,当左子树的左边是空的了,那我们可以让右边入栈,并且输出根节点
public static void InorderRecur(TreeNode root) { if(root!=null) { Stack<TreeNode> s = new Stack<>(); while (!s.empty()||root!=null) { if(root!=null) { s.push(root); root = root.left; } else { root = s.pop(); System.out.print(root.value+" "); root = root.right;
} } } }
|
后序遍历(LRD)
后序遍历就是后序遍历左子树,后序遍历右子树,随后遍历根节点
递归方式
public static void PostorderRecur(TreeNode root) { if(root==null) return; else { PostorderRecur(root.left); PostorderRecur(root.right); System.out.print(root.value+ " "); } }
|
非递归形式
后序遍历比较麻烦 这里提供两种方式实现 分别使用两个栈和一个栈来实现
第一种两个栈实现
根入栈1 循环条件(栈1不空){ 根节点指向栈1顶 出栈 根入栈2 (左子树)先(右子树)入栈1} 循环条件(栈2不空){ 栈2出栈输出}
例如{1,2,3,4,5,6,7}这个树,我们一步一步看看是实现的
s1 |
s2 |
操作 |
root |
1 |
null |
s1根节点入栈,s2没有,初始化后进入循环 |
1 |
1 |
null |
s1根节点入栈,s2没有,初始化后进入循环 |
1 |
null |
1 |
s1弹出根节点,s2保存, |
1 |
2,3 |
1 |
s1压入根节点左右两个子节点 |
1 |
2 |
1,3 |
s1弹出栈顶3,s2压入3 |
3 |
2,6,7 |
1,3 |
s1压入root左右子节点,s2不动 |
3 |
2,6 |
1,3,7 |
s1弹出7,s2压入7 |
7 |
2 |
1,3,7,6 |
7左右都没有,所以s1弹出6,s2压入6 |
6 |
null |
1,3,7,6,2 |
6也是叶子节点,所以s1弹出2,s2压入2 |
2 |
4,5 |
1,3,7,6,2 |
2下面有4,5所以s1压入4,5 |
2 |
4 |
1,3,7,6,2,5 |
s1弹出5,s2压入5 |
5 |
null |
1,3,7,6,2,5,4 |
因为4,5是叶子节点,所以都压入s2 |
|
依次弹出s2:4,5,2,6,7,3,1.至此分析完毕
这里我真的想知道一件事,想出这种方法的人的脑子怎么长得,真的厉害啊
public static void PostorderRecur(TreeNode root) { if(root!=null) { Stack<TreeNode> s1 = new Stack<>(); Stack<TreeNode> s2 = new Stack<>(); s1.push(root); while (!s1.empty()) { root = s1.pop(); s2.push(root); if(root.left!=null) s1.push(root.left); if(root.right!=null) s1.push(root.right); } while(!s2.empty()) { System.out.print(s2.pop().value); } } }
|
利用一个栈实现后序遍历
根入栈 新建节点指针cur等于NULL 循环条件(栈不空){ cur=栈顶 如果(cur左子树非空&&根不为cur左子树&&根不为cur右子树) cur左子树入栈 如果(cur右子树非空&&根不为cur右子树) cur右子树入栈 否则 出栈输出 根节点等于cur}
- 这里的root更像一个标记值
- root所指的位置意味着其本身包括其子节点都已被访问
- 当root为某个节点的左节点时 表示这个节点的左节点已被访问
- 当root为某个节点的右节点时 表示这个节点的左节点和右节点都已被访问
这种方法也是牛逼的不行啊。
public static void PostorderRecur(TreeNode root) { if(root!=null) { Stack<TreeNode> s = new Stack<>(); s.push(root); TreeNode cur = null; while (!s.empty()) { cur = s.peek(); if(cur.left!=null && root!=cur.left && root !=cur.right) { s.push(cur.left); } else if(cur.right!=null && cur.right!=root) { s.push(cur.right); } else { System.out.print(s.pop().value+" "); root = cur; } } } }
|
层序遍历(BFS)–广度优先遍历
广度优先遍历是利用队列实现的
这个直接看代码理解去来还是比较快的
public static void Sequence(TreeNode root) { if(root!=null) { Queue<TreeNode> q = new LinkedList<TreeNode>(); q.offer(root); while (!q.isEmpty()) { root = q.poll(); System.out.print(root.value+" "); if(root.left!=null) { q.offer(root.left); } if(root.right!=null) { q.offer(root.right); } } } }
|
神级遍历 Morris算法
当树的节点数为N时 遍历的时间复杂度O(N) 额外空间复杂度O(1),空间复杂度是1,一听就够牛逼的
这种方法没有使用函数栈(递归)和栈(非递归) 降低了空间复杂度 主要是利用了叶子节点的right为NULL 利用两个指针 让某个节点的左子树的最右边的结点的right指向自己本身 进行遍历后 又会将right赋NULL 不会改变树的结构.
前序节点:给定某个节点,在中序遍历中,直接排在它前面的节点,我们称之为该节点的前序节点
前序遍历
- 如果当前节点的左子节点为空时,输出当前节点,并将当前节点置为该节点的右子节点;
- 如果当前节点的左子节点不为空,找到当前节点左子树的最右节点(该节点为当前节点中序遍历的前驱节点);
- 1、如果最右节点的右指针为空(right=null),将最右节点的右指针指向当前节点,并输出当前节点(在此处输出),当前节点置为其左子节点;
- 2、如果最右节点的右指针不为空,将最右节点右指针重新置为空(恢复树的原状),并将当前节点置为其右节点;
- 重复1~2,直到当前节点为空。
public static void MorrisPre(TreeNode root) { if(root!=null) { TreeNode cur1 = root; TreeNode cur2 = null; while (cur1!=null) { cur2 = cur1.left; if(cur2!=null) { while (cur2.right!=null && cur2.right!=cur1) { cur2 = cur2.right; } if(cur2.right == null) { cur2.right = cur1; System.out.print(cur1.value+" "); cur1 = cur1.left; continue; } else { cur2.right = null; } } else { System.out.print(cur1.value+" "); cur1 = cur1.right; } } } }
|
中序遍历
- 如果当前节点的左子节点为空时,输出当前节点,并将当前节点置为该节点的右子节点;
- 如果当前节点的左子节点不为空,找到当前节点左子树的最右节点(该节点为当前节点中序遍历的前驱节点);
- 1、如果最右节点的右指针为空(right=null),将最右节点的右指针指向当前节点,当前节点置为其左子节点;
- 2、如果最右节点的右指针不为空,将最右节点右指针重新置为空(恢复树的原状),输出当前节点,并将当前节点置为其右节点;
- 重复1~2,直到当前节点为空。
public static void MorrisIn(TreeNode root) { if(root!=null) { TreeNode cur1 = root; TreeNode cur2 = null; while (cur1!=null) { cur2 = cur1.left; if(cur2!=null) { while (cur2.right!=null && cur2.right!=cur1) { cur2 = cur2.right; } if(cur2.right==null) { cur2.right = cur1; cur1 = cur1.left; continue; } else { cur2.right = null; } } System.out.print(cur1.value+" "); cur1 =cur1.right; } } }
|
后序遍历
后序遍历较前两者比较麻烦,需要建立一个临时节点,并令该节点的左子节点为root,并且需要一个子过程,倒序输出某两个节点之间路径上的各个节点。
- 如果当前节点的左子节点为空时,则将其右子节点作为当前节点;
- 如果当前节点的左子节点不为空,找到当前节点左子树的最右节点(该节点为当前节点中序遍历的前驱节点);
- 1、如果最右节点的右指针为空(right=null),将最右节点的右指针指向当前节点,当前节点置为其左子节点;
- 2、如果最右节点的右指针不为空,将最右节点右指针重新置为空(恢复树的原状),倒序输出从当前节点的左子节点到该最右节点路径上的所有节点,并将当前节点置为其右节点;
- 重复1~2,直到当前节点为空。
public static void MorrisPost(TreeNode root) { if(root!=null) { TreeNode cur1 = root; TreeNode cur2 = null; while (cur1!=null) { cur2 = cur1.left; if(cur2!=null) { while (cur2.right!=null && cur2.right!=cur1) { cur2 = cur2.right; } if(cur2.right==null) { cur2.right = cur1; cur1 = cur1.left; continue; } else { cur2.right = null; printEdge(cur1.left); } } cur1 =cur1.right; } printEdge(root); } } static void printEdge(TreeNode root) { TreeNode tail = reverseEdge(root); TreeNode cur = tail; while (cur != null) { System.out.print(cur.value+" "); cur = cur.right; } reverseEdge(tail); } static TreeNode reverseEdge(TreeNode from) { TreeNode pre = null; TreeNode next = null; while (from != null) { next = from.right; from.right = pre; pre = from; from = next; } return pre; }
|