前言

数据结构还是大二的时候学过的，当然由于是非计算机专业的学生，所以学的也不怎么样，去年用c++实现了最基本的数据结构，链表/栈/队列/二叉树，三月份看的时候还贴到了博客上。然而当时由于代码量不够，其实写的并不是很好，理解也太不到位。

最近在看算法导论，当然最基本的就是数据结构，于是打算将基本的知识在回顾一下。

我是一个疯狂的人，一旦决定做一件事，就会全天埋头去干，因为总有一种恨不得赶快学完的感觉。前几天我连续写了好几篇博客，讲解一些排序算法，其实在这个过程中，我深深的发现：

书上的伪代码/算法思路能看懂不一定能用代码轻松地实现，因为有很多小细节需要注意。能把代码写出来不一定能给别人讲清楚，就如这里的树的后序非递归遍历算法，我大致感觉和先序非递归有很大相似，但想讲清楚还是想了好久的。

写博客记录自己的学习笔记其实就是一个强迫自己把学到的知识不仅仅停留在会的层次上而是上升到理解的高度的过程。

二叉树?

4.n个结点的完全二叉树深度为(lgn下取整)+1

二叉树的实现

结点数据结构，BinaryTreeNode类描述每个结点

public class BinaryTreeNode {
	public int data;
	public BinaryTreeNode lchild;
	public BinaryTreeNode rchild;
	public BinaryTreeNode parent;
	
	public BinaryTreeNode(int data) {
		this.data = data;
		this.lchild = null;
		this.rchild = null;
		this.parent = null;
	}
}

public class BinaryTree {
	public BinaryTreeNode root;
	// 从数组递归创建二叉树时用来作为数组下标
	private int index = 0;
	/**
	 * 通过数组作为输入的一棵先序遍历的树节来创建二叉树
	 * @param array
	 */
	public void createTree(int[] array) {
		index = 0;
		root = createPreOrder(array,root);
	}
	
	private BinaryTreeNode createPreOrder(int[] a,BinaryTreeNode root) {
		if (a[index] == 0 || index > a.length - 1) {
			index++;
			root = null;
		} else {
			root = new BinaryTreeNode(a[index]);
			index++;
			root.lchild = createPreOrder(a,root.lchild);
			if (root.lchild != null)
				root.lchild.parent = root; // 双亲节点主要用在寻找前驱和后继
			root.rchild = createPreOrder(a,root.rchild);
			if (root.rchild != null)
				root.rchild.parent = root; // 双亲节点主要用在寻找前驱和后继
		}
		return root;
	}

	/**
	 * 通过键盘输入一棵先序遍历的树节点创建二叉树
	 */
	public void createTree() {
		Scanner in = new Scanner(System.in);
		root = createPreOrder(in,root);
	}

	private BinaryTreeNode createPreOrder(Scanner in,BinaryTreeNode root) {
		int a = in.nextInt();
		if (a == 0) {
			return null;
		} else {
			root = new BinaryTreeNode(a);
			root.lchild = createPreOrder(in,root.lchild);
			if (root.lchild != null)
				root.lchild.parent = root; // 双亲节点主要用在寻找前驱和后继
			root.rchild = createPreOrder(in,root.rchild);
			if (root.rchild != null)
				root.rchild.parent = root; // 双亲节点主要用在寻找前驱和后继
			return root;
		}
	}

	/**
	 *  先序递归遍历
	 */
	public void preOrder(BinaryTreeNode root) {
		if (root != null) {
			System.out.print(root.data + "  ");
			preOrder(root.lchild);
			preOrder(root.rchild);
		}
	}

	/**
	 *  先序非递归遍历
	 */
	public void preOrder() {
		Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
		visitAlongLeft(root,stack);
		while (stack.size() > 0) {
			BinaryTreeNode node = stack.poll();
			visitAlongLeft(node,stack);
		}
	}
	
	/**
	 * 沿着某个给定结点root的左分支访问，同时将有孩子入栈
	 * @param root
	 * @param stack
	 */
	private void visitAlongLeft(BinaryTreeNode root,Stack<BinaryTreeNode> stack) {
		while (root != null) {
			System.out.print(root.data + "  ");
			if (root.rchild != null)
				stack.push(root.rchild);
			root = root.lchild;
		}
	}

	/**
	 * 中序递归遍历
	 * @param root
	 */
	public void inOrder(BinaryTreeNode root) {
		if (root != null) {
			inOrder(root.lchild);
			System.out.print(root.data + "  ");
			inOrder(root.rchild);
		}
	}

	/**
	 * 中序非递归遍历
	 */
	public void inOrder() {
		Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
		goAlongLeft(root,stack);
		while (stack.size() > 0) {
			BinaryTreeNode node = stack.poll();
			System.out.print(node.data + "  ");
			goAlongLeft(node.rchild,stack);
		}
	}

	/**
	 * 沿着某个给定结点root的左分支入栈
	 * @param root
	 * @param stack
	 */
	private void goAlongLeft(BinaryTreeNode root,Stack<BinaryTreeNode> stack) {
		while (root != null) {
			stack.push(root);
			root = root.lchild;
		}
	}

	/**
	 * 后序递归遍历
	 * @param root
	 */
	public void postOrder(BinaryTreeNode root) {
		if (root != null) {
			postOrder(root.lchild);
			postOrder(root.rchild);
			System.out.print(root.data + "  ");
		}
	}

	//	stack2 用来访问
	private void goAlongRight(BinaryTreeNode root,Stack<BinaryTreeNode> stack1,Stack<BinaryTreeNode> stack2) {
		while (root != null) {
			stack2.push(root); // 访问
			if (root.lchild != null)
				stack1.push(root.lchild);
			root = root.rchild;
		}
	}
	
	/**
	 * 后序非递归遍历
	 */
	public void postOrder() {
		Stack<BinaryTreeNode> myStack1 = new Stack<BinaryTreeNode>();
		Stack<BinaryTreeNode> myStack2 = new Stack<BinaryTreeNode>();
		goAlongRight(root,myStack1,myStack2);
		while (myStack1.size() > 0) {
			BinaryTreeNode node = myStack1.poll();
			goAlongRight(node,myStack2);
		}
		while (myStack2.size() > 0) {
			BinaryTreeNode node = myStack2.poll();
			System.out.print(node.data + "  ");
		}
	}

	/**
	 * 层序遍历
	 */
	public void levelOrder() {
		Queue<BinaryTreeNode> queue = new Queue<BinaryTreeNode>();
		if (root != null) {
			queue.offer(root);
		}
		while (!queue.isEmpty()) {
			BinaryTreeNode node = queue.poll();
			System.out.print(node.data + "  ");
			if (node.lchild != null)
				queue.offer(node.lchild);
			if (node.rchild != null)
				queue.offer(node.rchild);
		}
	}
	
	/**
	 * 层序打印，每层用还行区分
	 */
	public void levelOrderH()  
	{  
	    if (root == null) return;  
	    Queue<BinaryTreeNode> current = new Queue<BinaryTreeNode>(); 
	    Queue<BinaryTreeNode> next = new Queue<BinaryTreeNode>(); 
	    current.offer(root);  
	    while (current.size() > 0) {  
	    	BinaryTreeNode node = current.poll();  
	        if (node!=null) {  
	            System.out.print(node.data + "  ");
	            next.offer(node.lchild);  
	            next.offer(node.rchild);  
	        }  
	        if (current.size() == 0) {  
	        	 System.out.println("");
	            asign(current,next);  
	        }  
	    }  
	}  
	
	// 将next行的元素给current行
	private void asign(Queue<BinaryTreeNode> current,Queue<BinaryTreeNode> next) {
		while (next.size() > 0) {  
	        current.offer(next.poll());
	    }  
	}

	public static void main(String[] args) {
		BinaryTree tree = new BinaryTree();
		int[] array = {1,2,4,7,5,3,6,8,0};
		tree.createTree(array);
		System.out.println("先序递归遍历");
		tree.preOrder(tree.root);
		System.out.println("\n中序递归遍历");
		tree.inOrder(tree.root);
		System.out.println("\n后序递归遍历");
		tree.postOrder(tree.root);
		System.out.println("\n先序非递归遍历");
		tree.preOrder();
		System.out.println("\n中序非递归遍历");
		tree.inOrder();
		System.out.println("\n后序非递归遍历");
		tree.postOrder();
		System.out.println("\n层序遍历");
		tree.levelOrder();
		System.out.println("\n层序遍历");
		tree.levelOrderH();
	}
}

相关算法

2.先序非递归遍历

（编辑：ASP站长网）