java分别使用递归和非递归实现二叉树中序遍历 _遍历

【java分别使用递归和非递归实现二叉树中序遍历】对于二叉树，它的特点就是任何一个节点，左节点小于父节点、右节点大于父节点遍历二叉树有多种方式，如中序遍历、层序遍历、后序遍历，中序遍历的思路就是左-->父--->右的顺序，下面给出递归和非递归的两种方法，递归很好理解，非递归就是一直找到最左节点，然后回溯节点，如果存在右节点，则重复上述过程
如将下面的二叉树使用中序遍历输出有序数组

文章插图

代码如下

import JAVA.util.ArrayList;import java.util.List;import java.util.Stack;/** * 中序遍历的非递归和递归的实现 ** @author ssj * */public class MiddleList {	public static void main(String[] args) {// 创建一颗二叉树Node root = new Node("10");Node n6 = new Node("6");Node n14 = new Node("14");n6.setParent(root);n14.setParent(root);root.setLeft(n6);root.setRight(n14);Node n4 = new Node("4");Node n8 = new Node("8");n6.setLeft(n4);n6.setRight(n8);Node n12 = new Node("12");Node n16 = new Node("16");n14.setLeft(n12);n14.setRight(n16);System.out.println("---------递归遍历结果--------------------");List list = new ArrayList();middleListDG(root, list);System.out.println(list);System.out.println("---------非递归遍历结果--------------------");List list2 = middleList(root);System.out.println(list2);	}	/*** 递归中序遍历** @param root* @return*/	public static void middleListDG(Node root, List list) {if (root == null) {return;}middleListDG(root.left, list);list.add(root.name);middleListDG(root.right, list);	}	/*** 非递归中序遍历* @param root* @return*/	public static List middleList(Node root) {Stack<Node> sk = new Stack<Node>();List list = new ArrayList();Node n = root;while (n != null) {// 一直找到最左边的节点while (n != null) {sk.push(n);n = n.left;}// 输出最左边的节点while (!sk.empty()) {Node n2 = sk.pop();list.add(n2.getName());// 如果该节点存在右节点，先输出所有的右节点，即重复以上过程if (n2.right != null) {n = n2.right;break;}}}return list;	}}/** * 树节点 * @author ssj * */class Node {	public String name;	public Node left;	public Node right;	public Node parent = null;	public String getName() {return name;	}	public void setName(String name) {this.name = name;	}	public Node getParent() {return parent;	}	public void setParent(Node parent) {this.parent = parent;	}	public Node(String name) {super();this.name = name;	}	public Node getLeft() {return left;	}	public void setLeft(Node left) {this.left = left;	}	public Node getRight() {return right;	}	public void setRight(Node right) {this.right = right;	}}

输出结果