日日操夜夜添-日日操影院-日日草夜夜操-日日干干-精品一区二区三区波多野结衣-精品一区二区三区高清免费不卡

對(duì)于二叉樹，它的特點(diǎn)就是任何一個(gè)節(jié)點(diǎn)，左節(jié)點(diǎn)小于父節(jié)點(diǎn)、右節(jié)點(diǎn)大于父節(jié)點(diǎn)遍歷二叉樹有多種方式，如中序遍歷、層序遍歷、后序遍歷，中序遍歷的思路就是左-->父--->右的順序，下面給出遞歸和非遞歸的兩種方法，遞歸很好理解，非遞歸就是一直找到最左節(jié)點(diǎn)，然后回溯節(jié)點(diǎn)，如果存在右節(jié)點(diǎn)，則重復(fù)上述過程

如將下面的二叉樹使用中序遍歷輸出有序數(shù)組

代碼如下

import JAVA.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
 * 中序遍歷的非遞歸和遞歸的實(shí)現(xiàn)
 * 
 * @author ssj
 *
 */
public class MiddleList {
	public static void main(String[] args) {
		// 創(chuàng)建一顆二叉樹
		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("---------遞歸遍歷結(jié)果--------------------");
		List list = new ArrayList();
		middleListDG(root, list);
		System.out.println(list);
		System.out.println("---------非遞歸遍歷結(jié)果--------------------");
		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) {
			// 一直找到最左邊的節(jié)點(diǎn)
			while (n != null) {
				sk.push(n);
				n = n.left;
			}
			// 輸出最左邊的節(jié)點(diǎn)
			while (!sk.empty()) {
				Node n2 = sk.pop();
				list.add(n2.getName());
				// 如果該節(jié)點(diǎn)存在右節(jié)點(diǎn)，先輸出所有的右節(jié)點(diǎn)，即重復(fù)以上過程
				if (n2.right != null) {
					n = n2.right;
					break;
				}
			}
		}
		return list;
	}
}
/**
 * 樹節(jié)點(diǎn)
 * @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;
	}
}

輸出結(jié)果