두 갈래 나무의 정의, 순서, 넓이

두 갈래 나무의 정의:

public class BTree<T> {

	private T data;
	private BTree<T> leftChild;
	private BTree<T> rightChild;
	
	public BTree()
	{
		
	}

	public BTree(T data, BTree<T> leftChild, BTree<T> rightChild) {
		this.data = data;
		this.leftChild = leftChild;
		this.rightChild = rightChild;
	}

	public T getData() {
		return data;
	}

	public void setData(T data) {
		this.data = data;
	}

	public BTree<T> getLeftChild() {
		return leftChild;
	}

	public void setLeftChild(BTree<T> leftChild) {
		this.leftChild = leftChild;
	}

	public BTree<T> getRightChild() {
		return rightChild;
	}

	public void setRightChild(BTree<T> rightChild) {
		this.rightChild = rightChild;
	}

}

깊이 우선 두 갈래 트리 앞차례 반복 (DLR) 의 귀속 알고리즘: 두 갈래 트리가 비어 있으면 알고리즘이 끝납니다. 그렇지 않으면 루트 결점에 접근합니다.뿌리 결점의 왼쪽 나무를 순서대로 옮겨다니기;앞의 순서가 뿌리 결점의 오른쪽 나무를 두루 훑어보다.
넓이가 두 갈래 나무를 우선적으로 훑어본다.넓이 우선 두 갈래 나무(층 서열 두루두루두루)는 대열로 이루어진 것으로 두 갈래 나무의 1층(뿌리 결점)부터 위에서 아래로 층층이 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루같은 층에서 왼쪽에서 오른쪽으로 순서대로 결점을 방문한다.뿌리 결점에서 잎 결점, 왼쪽 나무에서 오른쪽 나무까지의 순서에 따라 두 갈래 나무의 결점을 방문한다.알고리즘: 1 대기열을 초기화하고 루트 결점을 대기열에 넣기;2 대기열이 비어 있지 않을 때 3단계에서 5단계까지 순환하고 그렇지 않으면 6단계를 실행한다.3 대기열에서 결점을 얻어 이 결점을 방문한다.4 이 결점의 왼쪽 트리가 비어 있지 않으면 이 결점의 왼쪽 트리를 대기열에 넣는다.5 이 결점의 오른쪽 트리가 비어 있지 않으면 이 결점의 오른쪽 트리를 대기열에 넣는다.6 끝.

public class BTreeList {

	private static List<BTree<String>> binTree = new ArrayList<BTree<String>>();
	
	public static void main(String[] args) {
		BTreeList test = new BTreeList();
		
		test.createBinTree();
		//test.preOrder(binTree.get(0));
		test.guangDuList(binTree.get(0));
	}
	
	/**
	 *  
	 */
	public void createBinTree()
	{
		
		for(int i = 0; i < 64; i++)
		{
			binTree.add(new BTree<String>(" " + i, null, null));
		}
		
		for(int i = 0; i < 64; i++)
		{
			int leftChildIndex = (2*i) + 1;
			int rightChildIndex = (2*i) + 2;
			
			if( leftChildIndex < binTree.size())
			{
				binTree.get(i).setLeftChild(binTree.get(2*i+1));
			}
			else
			{
				binTree.get(i).setLeftChild(null);
			}
				
			if(rightChildIndex < binTree.size())
			{
				binTree.get(i).setRightChild(binTree.get((2*i)+2));
			}
			else
			{
				binTree.get(i).setRightChild(null);
			}
		}
	}
	
	/**
	 * 
	 *  。
	 */
	public void guangDuList(BTree<String> rootElement)
	{
		ArrayDeque<BTree<String>> queue = new ArrayDeque<BTree<String>>();
		queue.push(rootElement);
		
		while(true)
		{
			if(queue.isEmpty())
			{
				break;
			}
			BTree<String> binTree = queue.pop();
			System.out.println(binTree.getData());
			
			if(binTree.getLeftChild() != null)
			{
				queue.push(binTree.getLeftChild());
			}
			
			if(binTree.getRightChild() != null)
			{
				queue.push(binTree.getRightChild());
			}
		}
	}
	
	/**
	 *  。
	 */
	public void preOrder(BTree<String> binNode)
	{
		if(binNode == null)
		{
			return;
		}
		System.out.println(binNode.getData());
		preOrder(binNode.getLeftChild());
		preOrder(binNode.getRightChild());
	}
}