두 갈래 트리 차원, 선 루트, 후 루트, 인쇄 조작

6052 단어 알고리즘 학습
노드 클래스 정의
package pri.lr.java_tools.trees;

public class TreeNode {
	private T value;
	private TreeNode parent;
	private TreeNode leftChild;
	private TreeNode rightChild;
	
	public TreeNode() {
	}

	public TreeNode(T value) {
		this.value = value;
	}
		
	public T getValue() {
		return value;
	}

	public void setValue(T value) {
		this.value = value;
	}

	public TreeNode getParent() {
		return parent;
	}

	public void setParent(TreeNode parent) {
		this.parent = parent;
	}

	public TreeNode getLeftChild() {
		return leftChild;
	}

	public void setLeftChild(TreeNode leftChild) {
		this.leftChild = leftChild;
	}

	public TreeNode getRightChild() {
		return rightChild;
	}

	public void setRightChild(TreeNode rightChild) {
		this.rightChild = rightChild;
	}
	
	public void setInfo(T value, TreeNode leftChild, TreeNode rightChild){
		this.value = value;
		
	}
	
	public void setChildren(T value, TreeNode leftChild, TreeNode rightChild){
		this.leftChild = leftChild;
		this.rightChild = rightChild;
	}
}

두 갈래 트리 클래스 정의:
package pri.lr.java_tools.trees;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 *  , 
 * @author 57721
 *
 */
public class BinaryTree {
	private TreeNode root = null;
	private int treeNodeCount;
	
	private Queue> notFullNodeQue = new LinkedList<>();
	
	public BinaryTree(){}
	
	/**
	 *  
	 * @param value
	 * @return
	 */
	public boolean add(T value){
		TreeNode oneNode = new TreeNode<>(value);
		if(root == null) {
			root = oneNode;
			treeNodeCount++;
			notFullNodeQue.add(root);
			return true;
		}
		
		if(notFullNodeQue.peek().getLeftChild() == null) {
			notFullNodeQue.peek().setLeftChild(oneNode);
			notFullNodeQue.offer(oneNode);
			treeNodeCount++;
			return true;
		}
		if(notFullNodeQue.peek().getRightChild() == null) {
			notFullNodeQue.peek().setRightChild(oneNode);
			notFullNodeQue.offer(oneNode);
			treeNodeCount++;
			notFullNodeQue.poll();
		}
		return false;
	}
	
	public void printTreeByPreOrder(){
		System.out.println(" :");
		preOrder(root);
		System.out.println();
	}
	
	public void printTreeByInOrder(){
		System.out.println(" ");
		InOrder(root);
		System.out.println();
	}
	
	public void printTreeByPostOrder(){
		System.out.println(" :");
		postOrder(root);
		System.out.println();
	}
	
	public void printTreeByLevel(){
		System.out.println(" :");
		if(root == null) {
			return;
		}
		levelOrder();
		System.out.println();
	}
	
	public void printTree(){
		System.out.println(" ( ):");
		printTree(root, 1);
		System.out.println();
	}
	
	public void printTreeUpDown(){
		System.out.println(" ( ):");
		if(root == null) {
			return;
		}
		int distance = (int) Math.pow(2, this.getHeight() -1) - 1;
		
		List> list = new ArrayList<>();
		list.add(root);
		int pre = 0;//  , 
		int aft = 0;// , 
		int idx = 0;
		
		while(pre <= aft){
			for(idx = pre, pre = aft + 1; idx < pre; idx++) {
				printBlank(distance);				
				System.out.print(list.get(idx).getValue());				
				printBlank(distance);
				System.out.print(" ");
				
				if(list.get(idx).getLeftChild() != null) {
					list.add(list.get(idx).getLeftChild());
					aft++;
				}
				if(list.get(idx).getRightChild() != null) {
					list.add(list.get(idx).getRightChild());
					aft++;
				}
			}
			System.out.println();
			distance /= 2;
		}
	}
	
	

	
	public int getNodeCount(){
		return this.treeNodeCount;
	}
	
	public int getHeight(){
		return (int) (Math.log(this.treeNodeCount)/Math.log(2) + 1);
	}
	
	
	private void printBlank(int k) {
		for(int i = 0 ; i< k; i++) {
			System.out.print(" ");
		}
	}
	private void printTree(TreeNode root, int h){
		if(root == null) return;
		printTree(root.getRightChild(), h + 1);
		for(int i = 0 ; i < h; i++) {
			System.out.print(" ");
		}
		System.out.println(root.getValue());
		printTree(root.getLeftChild(), h+1);
	}
	private void levelOrder() {
		Queue> que = new LinkedList<>();
		que.offer(root);
		TreeNode current = null;
		while(!que.isEmpty()){
			current = que.poll();
			System.out.print(current.getValue() + " ");
			if(current.getLeftChild() != null) {
				que.offer(current.getLeftChild());
			}
			if(current.getRightChild() != null) {
				que.offer(current.getRightChild());
			}
		}
	}

	private void postOrder(TreeNode root2) {
		if(root2 != null) {
			postOrder(root2.getLeftChild());
			postOrder(root2.getRightChild());
			System.out.print(root2.getValue() + " ");
		}
	}

	private void preOrder(TreeNode root1){
		if(root1 != null) {
			System.out.print(root1.getValue() + " ");
			preOrder(root1.getLeftChild());
			preOrder(root1.getRightChild());
		}
	}
	private void InOrder(TreeNode root3){
		if(root3 != null) {
			InOrder(root3.getLeftChild());
			System.out.print(root3.getValue() + " ");
			InOrder(root3.getRightChild());
		}
	}
	

}

테스트 결과:
package pri.lr.java_tools.trees;

public class Demo {

	public static void main(String[] args) {
		BinaryTree oneTree = new BinaryTree<>();
		oneTree.add("A");
		oneTree.add("B");
		oneTree.add("C");
		oneTree.add("D");
		oneTree.add("E");
		oneTree.add("F");
		oneTree.add("G");
		oneTree.add("H");
		
		oneTree.printTree();
		oneTree.printTreeUpDown();
		oneTree.printTreeByInOrder();
		oneTree.printTreeByPreOrder();
		oneTree.printTreeByPostOrder();
		oneTree.printTreeByLevel();
	}
}

결과:
 ( ):
   G
  C
   F
 A
   E
  B
   D
    H

 ( ):
       A        
   B       C    
 D   E   F   G  
H 
 
H D B E A F C G 
 :
A B D H E C F G 
 :
H D E B F G C A 
 :
A B C D E F G H 

좋은 웹페이지 즐겨찾기