Java 实现二叉树的三种非递归遍历
1.思路
其实思路就是递归的思路,无非就是加入了栈这个数据结构。
具体来看代码吧,个人觉得还算简洁。
2.实现
首先是结点数据结构的设置:
/**
* @author WK
*/
public class SearchBinaryTree {
public String tag =
"";
public boolean flag =
false;
public SearchBinaryTree leftChild =
null;
public SearchBinaryTree rightChild =
null;
}
- 前序遍历
/**
*
* @param T 传入的树的根结点
*/
public static void priorOrderNonRecursive(SearchBinaryTree T) {
Stack<SearchBinaryTree> binaryTrees =
new Stack<>();
SearchBinaryTree p = T;
while (p !=
null || (!binaryTrees.empty())) {
if (p.flag ==
false) {
System.out.println(p.tag);
p.flag =
true;
binaryTrees.push(p);
}
if (p.leftChild !=
null && p.leftChild.flag ==
false) {
p = p.leftChild;
continue;
}
if (p.rightChild !=
null && p.rightChild.flag ==
false) {
p = p.rightChild;
continue;
}
if (!binaryTrees.empty())
p = binaryTrees.pop();
else
p =
null;
}
}
- 中序遍历
/**
* 中序遍历和前序的区别就在于遍历的位置,也就是输出tag的位置,其他完全类似
* @param root 传入的树的根结点
*/
public static void infixOrderNonRecursive(SearchBinaryTree root) {
Stack<SearchBinaryTree> binaryTrees =
new Stack<>();
SearchBinaryTree p = root;
while (p !=
null || (!binaryTrees.empty())) {
if (p.flag ==
false)
binaryTrees.push(p);
if (p.leftChild !=
null && p.leftChild.flag ==
false) {
p = p.leftChild;
continue;
}
if (p.flag ==
false) {
System.out.println(p.tag);
p.flag =
true;
}
if (p.rightChild !=
null && p.rightChild.flag ==
false) {
p = p.rightChild;
continue;
}
if (!binaryTrees.empty())
p = binaryTrees.pop();
else
p =
null;
}
}
- 后序遍历
/**
*可以发现其实后序遍历的代码与前两个也类似,只是遍历位置不同,由此可见非循环遍历其实也并不难,掌握其中一个其他的也就掌握了
* @param root
*/
public static void postOrderNonRecursive(SearchBinaryTree root) {
Stack<SearchBinaryTree> binaryTrees =
new Stack<>();
SearchBinaryTree p = root;
while (p !=
null || (!binaryTrees.empty())) {
if (p.flag ==
false)
binaryTrees.push(p);
if (p.leftChild !=
null && p.leftChild.flag ==
false) {
p = p.leftChild;
continue;
}
if (p.rightChild !=
null && p.rightChild.flag ==
false) {
p = p.rightChild;
continue;
}
if (p.flag ==
false) {
System.out.println(p.tag);
p.flag =
true;
}
if (!binaryTrees.empty())
p = binaryTrees.pop();
else
p =
null;
}
}
3.测试
以这棵树为例:
初始化代码:
private static SearchBinaryTree
initTree() {
SearchBinaryTree A =
new SearchBinaryTree(
"A");
SearchBinaryTree B =
new SearchBinaryTree(
"B");
SearchBinaryTree C =
new SearchBinaryTree(
"C");
SearchBinaryTree D =
new SearchBinaryTree(
"D");
SearchBinaryTree E =
new SearchBinaryTree(
"E");
SearchBinaryTree F =
new SearchBinaryTree(
"F");
SearchBinaryTree G =
new SearchBinaryTree(
"G");
A.leftChild = B;
A.rightChild = F;
B.leftChild = C;
B.rightChild = D;
D.leftChild = E;
F.leftChild = G;
return A;
}
测试:
SearchBinaryTree root = initTree();
System.out.println(
"--------前序遍历开始:");
priorOrderNonRecursive(root);
System.out.println(
"--------中序遍历开始:");
root = initTree();
infixOrderNonRecursive(root);
System.out.println(
"--------后序遍历开始:");
root = initTree();
postOrderNonRecursive(root);
结果:
--------前序遍历开始:
A
B
C
D
E
F
G
--------中序遍历开始:
C
B
E
D
A
G
F
--------后序遍历开始:
C
E
D
B
G
F
A
3.总结
实现之后发现静下心来思考的话这个问题并不难,说明对其他事物来讲也应该这样,静心下来去做。
转载请注明出处:http://blog.csdn.net/OfWK/article/details/78505862