/**
* Desc:二叉树的遍历
* 前序遍历：根节点，左子节点，右子节点.
* 中序遍历：左子节点，根节点，右子节点
* 后序遍历：左子节点，右子节点，根节点
*/
public class BinaryTree {
public static void main(String[] args) {
Node node = initNode();
ergodicNode(node, Order.ORDER_AFTER);
orderNode(node, Order.ORDER_AFTER);
}
/**
* 递归遍历.
* @param node 二叉树
* @param order 遍历方式
*/
private static void ergodicNode(Node node, Order order) {
if (node != null) {
if (order == Order.ORDER_FRONT) {
System.out.print(node.getValue() + " ");
}
ergodicNode(node.getLeft(), order);
if (order == Order.ORDER_CENTER) {
System.out.print(node.getValue() + " ");
}
ergodicNode(node.getRight(), order);
if (order == Order.ORDER_AFTER) {
System.out.print(node.getValue() + " ");
}
}
}
/**
* 非递归遍历.
* @param root 二叉树
* @param order 遍历方式
*/
private static void orderNode(Node root, Order order) {
Stack<Node> stack = new Stack<>();
switch (order) {
case ORDER_FRONT:
if (root != null) {
stack.push(root);
}
while (!stack.empty()) {
Node node = stack.pop();
System.out.print(node.getValue() + " ");
if (node.getRight() != null) {
stack.push(node.getRight());
}
if (node.getLeft() != null) {
stack.push(node.getLeft());
}
}
break;
case ORDER_CENTER:
while (root != null || !stack.empty()) {
while (root != null) {
stack.push(root);
root = root.getLeft();
}
if (!stack.empty()) {
Node node = stack.pop();
System.out.print(node.getValue() + " ");
root = node.getRight();
}
}
break;
case ORDER_AFTER:
Stack<Node> output = new Stack<>();
while (root != null || !stack.empty()) {
if (root != null) {
output.push(root);
stack.push(root);
root = root.getRight();
} else {
root = stack.pop();
root = root.getLeft();
}
}
while (!output.isEmpty()) {
System.out.print(output.pop().getValue() + " ");
}
break;
}
}
/**
* 63
* / \
* / \
* / \
* / \
* 27 80
* / \ / \
* / \ / \
* / \ 70 92
* 13 51 /
* \ / \ /
* \ / \ 82
* 26 33 58
* / \
* / \
* 57 60
* 前序遍历：63 27 13 26 51 33 58 57 60 80 70 92 82
* 中序遍历：13 26 27 33 51 57 58 60 63 70 80 82 92
* 后序遍历：26 13 33 57 60 58 51 27 70 82 92 80 63
*
* @return Node
*/
private static Node initNode() {
return new Node(63)
.setLeft(new Node(27)
.setLeft(new Node(13)
.setRight(new Node(26)))
.setRight(new Node(51)
.setLeft(new Node(33))
.setRight(new Node(58)
.setLeft(new Node(57))
.setRight(new Node(60)))))
.setRight(new Node(80)
.setLeft(new Node(70))
.setRight(new Node(92)
.setLeft(new Node(82))));
}
enum Order {
ORDER_FRONT, ORDER_CENTER, ORDER_AFTER
}
private static class Node {
private int value;
private Node left;
private Node right;
private Node(int value) {
this.value = value;
}
private int getValue() {
return value;
}
private Node getLeft() {
return left;
}
private Node setLeft(Node left) {
this.left = left;
return this;
}
private Node getRight() {
return right;
}
private Node setRight(Node right) {
this.right = right;
return this;
}
}
}
Java实现二叉树的三种遍历方式
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
