データ構造-ツリー(作成、遍歴)java実装

8206 ワード
java データ構造 巡回する 二叉の木 作成
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;
	}
}
</span>

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();
}
</span>

3、スタックインタフェース
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();
}
</span>

4、チェーンキュー
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;
		}
	}

}
</span>

4、チェーンスタック
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;
		}
	}
}
</span>

5、ツリーノード
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;
	}
}
</span>

6、ツリー(ツリーの基本操作を含む)
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;
	}
}

7、試験手順
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();
	}

}
</span>

8、テスト結果
LinuxでのFTPサーバの構築チュートリアル
ブラックサルの家:Linux Crondtabシステムタイミングタスクコマンド