数据结构采用 --------------- 二叉链表结构
本文主要描述二叉树的先序、中序、后序、层序的递归和非递归遍历。
class TreeNode<T> {
//下标
public int index;
//数据
public T data;
//左子树
public TreeNode<T> left;
//右子树
public TreeNode<T> right;
public TreeNode(int index, T data) {
this.index = index;
this.data = data;
}
}
创建初始化数据
TestBinaryTree.TreeNode<String> treeNode1=new TestBinaryTree.TreeNode<String>(1,"A");
TestBinaryTree.TreeNode<String> treeNode2=new TestBinaryTree.TreeNode<String>(2,"B");
TestBinaryTree.TreeNode<String> treeNode3=new TestBinaryTree.TreeNode<String>(3,"C");
TestBinaryTree.TreeNode<String> treeNode4=new TestBinaryTree.TreeNode<String>(4,"D");
//指向关系
treeNode1.left=treeNode2;
treeNode1.right=treeNode3;
treeNode2.left=treeNode4;
4种遍历方法的基序一致，得到的结果却不一样：
先(前)序：当前移步操作到这个节点后，就输出该节点的值，并继续遍历其左右子树。(根左右)
中序：当前移步操作到这个节点后，将其暂存，遍历完左子树后，再输出该节点的值，然后遍历右子树。(左根右)
后序：当前移步操作到这个节点后，将其暂存，遍历完左右子树后，再输出该节点的值。(左右根)
层序：按照二叉树的层次输出，从左到右，从上到下依次输出。
层序：A B C D
前序：A B D C
中序：D B A C
后序：D B C A
二叉树数据源
PS:这里使用的二叉树画图是由一个网站生成的。数据结构动态生成神器
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
还有一个好用的在线作图工具：
https://www.processon.com/
前序遍历：
前序
递归先序遍历
递归前序遍历很容易理解，先输出节点的值，再递归遍历左右子树。中序和后序的递归类似，改变根节点输出位置即可。
//前序-----迭代方式遍历
public void printBeforeSoft(TreeNode node) {
if (node == null) {
return;
}
System.out.println(node.data);
printBeforeSoft(node.left);
printBeforeSoft(node.right);
}
非递归先序遍历
因为要在遍历完节点的左子树后接着遍历节点的右子树，为了能找到该节点，需要使用栈来进行暂存。中序和后序也都涉及到回溯，所以都需要用到栈。
//前序-----非迭代方式遍历------压栈方式
public void printBeforeSoft1(TreeNode node) {
if (node == null) {
return;
}
// 用来暂存节点的栈
Stack<TreeNode<String>> datas = new Stack<>();
datas.push(node);
// 只要栈不为空，都进入循环
while (!datas.isEmpty()) {
//将栈顶元素取出来并打印，接着把右、左节点压入栈,一直循环下去，直到栈为空。
TreeNode<String> treeNode = datas.pop();
System.out.println("--->" + treeNode.data);
if (treeNode.right != null) {
datas.push(treeNode.right);
}
if (treeNode.left != null) {
datas.push(treeNode.left);
}
}
}
非递归前序遍历输出结果：A B D C
中序遍历
中序
递归中序遍历
过程和递归先序遍历类似
//中序遍历
public void printMidSoft(TreeNode node) {
if (node == null) {
return;
}
printMidSoft(node.left);
System.out.print(node.data + " ");
printMidSoft(node.right);
}
非递归中序遍历
和非递归先序遍历类似，唯一区别是当前移步操作到这个节点时，并不直接输出该节点，而是当此结点下左子数为空时，从栈中弹出，再输出，接着压入右边子节点。
//中序-----非迭代方式遍历------压栈方式
public void printMidSoft1(TreeNode node) {
if (node == null) {
return;
}
System.out.println();
Stack<TreeNode<String>> datas = new Stack<>();
TreeNode head = node;
while (!datas.isEmpty() || head != null) {
if (head != null) {
datas.push(head);
head = head.left;
} else {
head = datas.pop();
System.out.print(head.data + " ");
head = head.right;
}
}
}
非递归中序遍历：D B A C
后序遍历
后序
递归后序遍历
过程和递归先序遍历类似
//后序遍历
public void printPostSoft(TreeNode node) {
if (node == null) {
return;
}
printPostSoft(node.left);
printPostSoft(node.right);
System.out.print(node.data + " ");
}
非递归后序遍历
后续遍历和先序、中序遍历不太一样。
后序遍历在决定是否可以输出当前节点的值的时候，需要考虑其左右子树是否都已经遍历完成。
所以有多种思路。如用双栈、断链标记、末尾标记等。
方案一:双栈
//后序-----非迭代方式遍历------压栈方式---双栈
public void printPostSoft1(TreeNode node) {
if (node == null) {
return;
}
TreeNode head = node;
System.out.println();
Stack<TreeNode<String>> datas = new Stack<>();
Stack<TreeNode> twoDatas = new Stack<>();
datas.push(head);
while (!datas.isEmpty()) {
head = datas.pop();
twoDatas.push(head);
if (head.left != null) {
datas.push(head.left);
}
if (head.right != null) {
datas.push(head.right);
}
}
while (!twoDatas.isEmpty()) {
System.out.print(twoDatas.pop().data + " ");
}
}
方案二：断链标记
//后序-----非迭代方式遍历------压栈方式 2
public void printPostSoft2(TreeNode node) {
if (node != null) {
System.out.println();
Stack<TreeNode<String>> datas = new Stack<>();
datas.push(node);
TreeNode head = node;
while (!datas.isEmpty()) {
head = datas.peek();
if (head.left != null) {
datas.push(head.left);
head.left = null;
} else if (head.right != null) {
datas.push(head.right);
head.right = null;
} else {
datas.pop();
System.out.print(head.data + " ");
}
}
}
}
方案三：末尾标记
//后序-----非迭代方式遍历------压栈方式 3
public void printPostSoft3(TreeNode root) {
if (root != null) {
Stack<TreeNode<String>> datas = new Stack<>();
TreeNode node = root;
TreeNode lastVisit = root;
while (node != null || !datas.isEmpty()) {
while (node != null) {
datas.push(node);
node = node.left;
}
//查看当前栈顶元素
node = datas.peek();
//如果其右子树也为空，或者右子树已经访问
//则可以直接输出当前节点的值
if (node.right == null || node.right == lastVisit) {
System.out.print(node.data + " ");
datas.pop();
lastVisit = node;
node = null;
} else {
//否则，继续遍历右子树
node = node.right;
}
}
}
非递归后序遍历：D B C A
层序：
与前面三个都不一样，按照二叉树的层次输出，从左到右，从上到下依次输出。
这里采用队列的方式实现(LinkedList刚好是一个双向链表的队列)。
//层序
public void levelOrderTrav(TreeNode n) {
Queue<TreeNode> q = new LinkedList<>();
q.add(n);
while (q.size() != 0) {
n = q.poll();
System.out.print(" " + n.data);
if (n.left != null)
q.add(n.left);
if (n.right != null)
q.add(n.right);
}
}
有什么错误请留言纠正。
