本文共 7231 字，大约阅读时间需要 24 分钟。

1、链表的节点

package package1;public class Node {	//数据域	public Object data;	//引用域（指针域）	public Node next;	//无参构造器	public Node() {		this(null,null);	}	//一个参数的构造器	public Node(Object data) {		this(data,null);	}	//两个参数	public Node(Object data,Node next) {		this.data = data;		this.next = next;	}}

2、队列接口

package package1;public interface IQueue {	public void clear();	public boolean isEmpty();	public int length();	public Object peek();	public void offer(Object x) throws Exception;	public Object poll();}

package package1;public interface IStack {	public void clear();	public boolean isEmpty();	public int length();	public Object peek();	public void push(Object x) throws Exception;	public Object pop();}

package package1;public class LinkQueue implements IQueue{	private Node front;	private Node rear;		public LinkQueue() {		front = rear = null;	}	public void clear() {		front = rear = null;	}	public boolean isEmpty() {		return front == null;	}	public int length() {		Node n = front;		int length = 0;		while(n != null) {			n = n.next;			length++;		}		return length;	}	public Object peek() {		if(front != null) {			return front.data;		}else {			return null;		}	}	public void offer(Object x) {		Node n = new Node(x);		if(front != null) {			rear.next = n;			rear = n;		}else {			front = rear = n;		}	}	public Object poll() {		if(front != null) {			Node n = front;			front = front.next;			if(n == rear) {				rear = null;			}			return n.data;		}else {			return null;		}	}}

package package1;public class LinkStack implements IStack{	//栈顶元素	private Node top;	//将栈置空	public void clear() {		top = null;	}	//判断栈是否为空	public boolean isEmpty() {		return top == null;	}	//求链栈的长度	public int length() {		Node n = top;		int length = 0;		while(n != null) {			n = n.next;			length++;		}		return length;	}	//取栈顶元素，并返回其值	public Object peek() {		if(!isEmpty())			return top.data;		else 			return null;	}	//入栈	public void push(Object x) {		Node n = new Node(x);		n.next = top;		top = n;	}		//出栈	public Object pop() {		//this为隐式参数		if(this.isEmpty()) {			return null;		}else {			Node n = top;			top = top.next;			return n.data;		}	}	//整个栈的遍历	public void display() {		Node n = top;		while(n != null) {			System.out.print(n.data.toString() + " ");			n = n.next;		}	}}

package package1;public class BiTreeNode {	//域	public Object data;	public BiTreeNode lchild,rchild;		//构造空节点	public BiTreeNode() {		this(null);	}		//构造左右孩子域为空的二叉树	public BiTreeNode(Object data) {		this(data, null, null);	}		//构造左右孩子和数据域都不为空的二叉树	public BiTreeNode(Object data, BiTreeNode lchild, BiTreeNode rchild) {		this.data = data;		this.lchild = lchild;		this.rchild = rchild;	}}

package package1;public class BiTree {	//域	private BiTreeNode root;		//构造空树	public BiTree() {		this.root = null;	}	//构造二叉树	public BiTree(BiTreeNode root) {		this.root = root;	}		/*根据先根遍历和中根遍历创建一颗二叉树	 * preOrder 先根遍历序列	 * inOrder 中根遍历序列	 * preIndex 先根遍历序列在preOrder中的开始位置	 * inIndex 中根遍历序列在inOrder中的开始位置	 * count 节点的总数	 */	public BiTree(String preOrder, String inOrder, int preIndex, int inIndex, int count) {		/*		 * 算法描述：		 * 1.先根和中根非空		 * 2.取先根遍历序列中第一个节点作为根节点		 * 3.找到根节点在中序中的位置		 * 4.创建根节点、左子树、右子树		 */		if(count > 0){			char r = preOrder.charAt(preIndex);			int i = 0;			for(; i < count; i++){				if(r == inOrder.charAt(inIndex + i))					break;			}			root = new BiTreeNode(r);		    /*		     * 先序：root：lchild：rchild		     * 中序：lchild：root：rchild		     */			root.lchild = new BiTree(preOrder, inOrder, preIndex+1, inIndex, i).root;			root.rchild = new BiTree(preOrder, inOrder, preIndex+i+1, inIndex+i+1, count-i-1).root;					}	}		//标明空子树的 先根遍历序列创建一棵二叉树	private static int index = 0;	public BiTree(String preStr){		char c = preStr.charAt(index++);		if(c != '#') {			root = new BiTreeNode(c);			root.lchild = new BiTree(preStr).root;			root.rchild = new BiTree(preStr).root;		} else {			root = null;		}			}		//递归先根遍历	public void preRootTraverse(BiTreeNode T) {		if(T != null){			System.out.print(T.data);			preRootTraverse(T.lchild);			preRootTraverse(T.rchild);		}	}		/*	 * 非递归先根遍历	 * 1.第一层循环：栈是否为空	 * 2.不断的访问左子树，右子树入栈，一会返回（出栈）	 * 3.重点：直接访问	 */	public void preRootTraverse() {		BiTreeNode T = root;		if(T != null) {			//将root入栈之后就是不断的入栈出栈			LinkStack S = new LinkStack();			S.push(T);			//入栈出栈的过程			while(!S.isEmpty()) {				T = (BiTreeNode)S.pop();				System.out.print(T.data);				while(T != null) {					if(T.lchild != null) {						System.out.print(T.lchild.data);					}					if(T.rchild != null) {						S.push(T.rchild);					}					T = T.lchild;//一直向下				}			}		}	}		//递归中根遍历	public void inRootTraverse(BiTreeNode T) {		if(T != null){			inRootTraverse(T.lchild);			System.out.print(T.data);			inRootTraverse(T.rchild);		}	}		/*	 * 非递归中根遍历	 * 1.第一层循环同先根	 * 2.左孩子不断入栈，然后到底之后出栈时访问输出，之后右孩子入栈	 * 3.重点：没有左子树，出栈，访问	 */	public void inRootTraverse() {		BiTreeNode T = root;		if(T != null) {			LinkStack S = new LinkStack();			S.push(T);			while(!S.isEmpty()) {				while(S.peek() != null) {					S.push(((BiTreeNode)S.peek()).lchild);				}				//空节点出栈				S.pop();				if(!S.isEmpty()) {					T = (BiTreeNode)S.pop();					System.out.print(T.data);					S.push(T.rchild);			}						}		}	}		//递归后根遍历	public void postRootTraverse(BiTreeNode T) {		if(T != null){			postRootTraverse(T.lchild);			postRootTraverse(T.rchild);			System.out.print(T.data);		}	}		/*	 * 非递归后根遍历	 * 1.第一层同上两个	 * 2.不断将左子树入栈，到底，出栈，如果出栈节点为叶子节点，访问	 * 3.重点：没有左子树 和 右子树 （已经被访问了）	 */	public void postRootTraverse() {		BiTreeNode T = root;		if(T != null) {			LinkStack S = new LinkStack();			S.push(T);			Boolean flag;			BiTreeNode p = null;			while(!S.isEmpty()) {				while(S.peek() != null) {					S.push(((BiTreeNode)S.peek()).lchild);				}				S.pop();				while(!S.isEmpty()) {					T = (BiTreeNode)S.peek();//取栈顶元素					if(T.rchild == null || T.rchild == p) {						System.out.print(T.data);						S.pop();						p = T;						flag = true;					} else {						S.push(T.rchild);						flag = false;					}					if(!flag) {						break;					}				}			}		}	}		//层次遍历（自左向右）	//http://blog.csdn.net/peerslee/article/details/49473831	public void levelTraverse() {				BiTreeNode T = root;		if(T != null) {			LinkQueue L = new LinkQueue();			L.offer(T);						while(!L.isEmpty()) {				T = (BiTreeNode)L.poll();								System.out.print(T.data);				if(T.lchild != null) {					L.offer(T.lchild);				}				if(T.rchild != null) {					L.offer(T.rchild);				}			}		}	}		public BiTreeNode getRoot() {		return root;	}		public void setRoot(BiTreeNode root) {		this.root = root;	}}

package package1;public class t1 {	public static void main(String[] args) {		String preOrder = "ABDEGCFH";		String inOrder = "DBGEAFHC";				BiTree T = new BiTree(preOrder,inOrder,0,0,preOrder.length());		System.out.println("先根遍历(递归）");		T.preRootTraverse(T.getRoot());		System.out.println();		System.out.println("先根遍历(非递归）");		T.preRootTraverse();		System.out.println();		System.out.println("中根遍历（递归）");		T.inRootTraverse(T.getRoot());		System.out.println();		System.out.println("中根遍历（非递归）");		T.inRootTraverse();		System.out.println();		System.out.println("后根遍历（递归）");		T.postRootTraverse(T.getRoot());		System.out.println();		System.out.println("后根遍历（非递归）");		T.postRootTraverse();				System.out.println();		System.out.println("层次遍历");		T.levelTraverse();	}}

转载地址：https://lipenglin.blog.csdn.net/article/details/50081717 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！