龙空技术网

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

万物生的好物 173

前言:

现在姐妹们对“java树前序遍历 中序遍历 后序遍历”可能比较注重,大家都需要分析一些“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;	}}

输出结果

标签: #java树前序遍历 中序遍历 后序遍历 #java遍历二叉树代码 #java二叉树层次遍历输出每一层元素 #java二叉树的先序中序后序遍历非递归算法 #递归算法实现二叉树的遍历