首页 / 算法 / 二叉树遍历-java实现
二叉树遍历-java实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了二叉树遍历-java实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4916字，纯文字阅读大概需要8分钟。
内容图文
二叉树相关的概念主参考 https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91
public class BinaryTree {
static class Node {
//左结点
private Node leftNode;
//右结点
private Node rightNode;
//值
private int value;
public Node() {
}
public Node(int value) {
this.value = value;
}
public Node getLeftNode() {
return leftNode;
}
public void setLeftNode(Node leftNode) {
this.leftNode = leftNode;
}
public Node getRightNode() {
return rightNode;
}
public void setRightNode(Node rightNode) {
this.rightNode = rightNode;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
}
private static Node init(int value, int level) {
level++;
Node node = new Node(value);
if (level > 6) {
return node;
}
node.setLeftNode(init(new Random().nextInt(10), level));
node.setRightNode(init(new Random().nextInt(10), level));
return node;
}
private static Node init2() {
Node node1 = new Node(1);
Node node0 = new Node(0);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node6 = new Node(6);
Node node7 = new Node(7);
Node node8 = new Node(8);
node1.setLeftNode(node0);
node1.setRightNode(node8);
node0.setLeftNode(node2);
node0.setRightNode(node3);
node8.setLeftNode(node6);
node8.setRightNode(node7);
return node1;
}
/**
* 前序遍历
*
* @param node
*/
private static void preOrder(Node node) {
System.out.print(node.getValue());
if (node.getLeftNode() != null) {
preOrder(node.getLeftNode());
}
if (node.getRightNode() != null) {
preOrder(node.getRightNode());
}
}
/**
* 前序遍历 非递归
*
* @param node
*/
private static void preOrderWithStack(Node node) {
Stack<Node> nodeStack = new Stack<>();
nodeStack.push(node);
while (!nodeStack.isEmpty()) {
Node top = nodeStack.pop();
if (top != null) {
System.out.print(top.getValue());
if (top.getRightNode() != null) {
nodeStack.push(top.getRightNode());
}
if (top.getLeftNode() != null) {
nodeStack.push(top.getLeftNode());
}
} else {
break;
}
}
}
/**
* 中序遍历
*
* @param node
*/
private static void inOrder(Node node) {
if (node.getLeftNode() != null) {
inOrder(node.getLeftNode());
}
System.out.print(node.getValue());
if (node.getRightNode() != null) {
inOrder(node.getRightNode());
}
}
/**
* 中序遍历 非递归
*
* @param node
*/
private static void inOrderWithStack(Node node) {
Map<Node, Boolean> nodeExecuteMap = new HashMap<>();
Stack<Node> nodeStack = new Stack<>();
nodeStack.push(node);
nodeExecuteMap.put(node, false);
while (!nodeStack.isEmpty()) {
Node top = nodeStack.pop();
if (top != null) {
if (!nodeExecuteMap.get(top)) {
nodeExecuteMap.put(top, true);
if (top.getRightNode() != null) {
nodeStack.push(top.getRightNode());
nodeExecuteMap.put(top.getRightNode(), false);
}
nodeStack.push(top);
if (top.getLeftNode() != null) {
nodeStack.push(top.getLeftNode());
nodeExecuteMap.put(top.getLeftNode(), false);
}
} else {
System.out.print(top.getValue());
}
}
}
}
/**
* 后序遍历
*
* @param node
*/
private static void postOrder(Node node) {
if (node.getLeftNode() != null) {
postOrder(node.getLeftNode());
}
if (node.getRightNode() != null) {
postOrder(node.getRightNode());
}
System.out.print(node.getValue());
}
/**
* 后序遍历 非递归
*
* @param node
*/
private static void postOrderWithStack(Node node) {
Map<Node, Boolean> nodeExecuteMap = new HashMap<>();
Stack<Node> nodeStack = new Stack<>();
nodeStack.push(node);
nodeExecuteMap.put(node, false);
while (!nodeStack.isEmpty()) {
Node top = nodeStack.pop();
if (top != null) {
if (!nodeExecuteMap.get(top)) {
nodeExecuteMap.put(top, true);
nodeStack.push(top);
if (top.getRightNode() != null) {
nodeStack.push(top.getRightNode());
nodeExecuteMap.put(top.getRightNode(), false);
}
if (top.getLeftNode() != null) {
nodeStack.push(top.getLeftNode());
nodeExecuteMap.put(top.getLeftNode(), false);
}
} else {
System.out.print(top.getValue());
}
}
}
}
/**
* 层次优先
*
* @param node
*/
private static void levelOrder(Node node) {
Queue<Node> nodeQueue = new ArrayDeque<>();
nodeQueue.add(node);
while (!nodeQueue.isEmpty()) {
Node root = nodeQueue.poll();
if (root != null) {
System.out.print(root.getValue());
if (root.getLeftNode() != null) {
nodeQueue.add(root.getLeftNode());
}
if (root.getRightNode() != null) {
nodeQueue.add(root.getRightNode());
}
} else {
break;
}
}
}
public static void main(String[] args) {
// Node node = init2();
Node node = init(5, 1);
System.out.println(JSON.toJSONString(node));
System.out.println("前序递归");
preOrder(node);
System.out.println();
System.out.println("前序非递归");
preOrderWithStack(node);
System.out.println();
System.out.println("中序递归");
inOrder(node);
System.out.println();
System.out.println("中序非递归");
inOrderWithStack(node);
System.out.println();
System.out.println("后序递归");
postOrder(node);
System.out.println();
System.out.println("后序非递归");
postOrderWithStack(node);
System.out.println();
System.out.println("层次优化");
levelOrder(node);
}
原文：https://www.cnblogs.com/feichen-2018/p/9157313.html
内容总结
以上是互联网集市为您收集整理的二叉树遍历-java实现全部内容，希望文章能够帮你解决二叉树遍历-java实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】