二叉树相关知识

一、二叉树的构建与打印

Node.java

public class Node {
	private int value;
	private Node left;
	private Node right;
	public Node(int value){
		this.value = value;
	}
	public void setLeft(Node left){
		this.left = left;
	}
	public void setRight(Node right){
		this.right = right;
	}
	
	public Node getLeft(){
		return this.left;
	}
	public Node getRight(){
		return this.right;
	}
	
	public void setValue(int value){
		this.value = value;
	}
	public int getValue(){
		return this.value;
	}
}

BinaryTree.java

import java.util.ArrayList;
import java.util.List;


public class BinaryTree {
	private int[] bTreeValue = new int[]{89,100,34,20,200,102,50,300,178,145,134,7,18,4,1};
	
	private void order(){
		
		//冒泡法
		if(bTreeValue.length==0){
			return;
		}
		
		//相临两个值依次比较，如果前一个值小于或等于第二个值则不变位置
		//如果第一个值大于第二个值，第一个值与第二个值交换位置
		//经过第一轮后，本数组中最大值会排在数组最后一个位置
		
		//然后第二次比较，重覆上一次的比较，唯一不同的是不需要和最后一个值比较（N次比较时，进行到倒数第(N-1)个值就可以结束比较）
		//因为进行一轮比较，后面的序列就是有序的了。
		
		int k=0,j=0;
		for(k=0;k<bTreeValue.length-1;k++){//当只剩下一个数时，就不需要和自己比较了
			for(j=0;j<bTreeValue.length-1-k;j++){
				if(bTreeValue[j]>bTreeValue[j+1]){
					int tmp = bTreeValue[j];
					bTreeValue[j] =  bTreeValue[j+1];
					bTreeValue[j+1] = tmp;
				}
			}
			for(int t=0;t<bTreeValue.length;t++){
				System.out.print(bTreeValue[t]+",");
			}
			System.out.println();
		}
		
		
		
		
	}
	
	
	public Node buildTree(){
		if(bTreeValue.length==0){
			return null;
		}
		
		
		int[] remain = bTreeValue;
		int i = remain.length/2;
		Node root =new Node(remain[i]);
		
		buildSubTree(root,remain);
		
		return root;
		
	}
	
	
	private void buildSubTree(Node root,int[] remain){
		
		if(remain.length==1){
			return;
		}
		
		int i = remain.length/2;
		
		if(i>0){
			int[]leftArr = new int[i];
			for(int j=0;j<i;j++){
				leftArr[j] = remain[j];
			}
			int lInd = leftArr.length/2;
			Node left = new Node(leftArr[lInd]);
			root.setLeft(left);
			buildSubTree(left,leftArr);
		}
		
		if(remain.length-i-1>0){
			int[]rightArr = new int[remain.length-i-1];
			for(int j=0;j<remain.length-i-1;j++){
				rightArr[j] = remain[i+1+j];
			}
			int rInd = rightArr.length/2;
			Node right = new Node(rightArr[rInd]);
			root.setRight(right);
			buildSubTree(right,rightArr);
		}
		
	}
	
	/**
	 * 根据节点数计算二叉树的层数
	 * @return
	 */
	public int calculateLevel(int n){
		return (int)Math.floor(Math.log(n+1)/Math.log(2))+1;	
	}
	
	/**
	 * 计算某层的最大节点数
	 * @param level
	 * @return
	 */
	public int nodesNum(int level){
		return (int)Math.pow(2, level-1);
	}
	
	//逐层打印节点
	public void levelStructure(List list,List all){
		//同层数之间以三个字符与10个*分开
		//根为其所在子树的下底中点上
		List subList = new ArrayList();
		for(int i=0;i<list.size();i++){
			Node node = (Node)list.get(i);
			if(node.getLeft()!=null){
				subList.add(node.getLeft());
			}
			if(node.getRight()!=null){
				subList.add(node.getRight());
			}
		}
		if(subList.size()>0){
			all.add(subList);
			levelStructure(subList,all);
		}
	}
	
	
	public void print(List all){
		int len = 6;
		int wordLen = 3;
		//设定最底层二节点之间的长为10个字符宽，节点宽先忽略
		//根节点的左边，最下层有2的(level-1)次幂个节点，那么距离最下层左边的距离也就是2的(level-1)次幂减1乘以10/2
		
		//从下往上数，第二层开始，第一个节点距左边距离为(math.pow(2,level-1)-1)*(10/2)
		//当层节点之间的距离为下层节点之间长度的两倍可以推出从下住上数，节点之间距离为math.pow(2,level-1)*10
		
		
		for(int i=0;i<all.size();i++){
			List tmp = (List)all.get(i);
			int level = all.size()-i;//倒数第几层，最下层为第一层
			//左边的跟离
			StringBuffer sb = new StringBuffer(200);
			
			//==============================
			sb.append(separator(Math.pow(2, level-1)*(len/2)));
			if(level>=2){
				sb.append(separator(wordLen*Math.pow(2, level-2)));
			}
			//没有实际依据
			//==============================
			for(int k=0;k<tmp.size();k++){
				Node n = (Node)tmp.get(k);
				sb.append(value(n.getValue()));
				if(k<tmp.size()-1){
					sb.append(separator(Math.pow(2, level-1)*len+(Math.pow(2, level-1)-1)*wordLen));
				}
			}
			
			//if(level>=2){
			//	sb.append(separator(Math.pow(2, level-1)*len/2));
			//}
			
			//sb.append("\n\r");
			System.out.println(sb.toString());
			if(i<all.size()-1){//空两行，更美观一些
				System.out.println();
				System.out.println();
			}
		}
		
		
		
	}
	
	
	private String value(int v){
		//只考虑三个字符长度
		if(v<10){
			return " "+v+" ";
		}else if(v<100){
			return v+" ";
		}
		return v+"";
		
	}
	
	private String separator(double len){
		StringBuffer sb = new StringBuffer((int)len);
		for(int i=0;i<len;i++){
			sb.append(" ");
		}
		return sb.toString();
	}
	
	private int len(int l,int num){
		return (num-1)*l;
	}
	
	
	public static void main(String[] args){
		BinaryTree tree = new BinaryTree();
		tree.order();
		List all = new ArrayList();
		
		List subL = new ArrayList();
		subL.add(tree.buildTree());
		all.add(subL);
		
		tree.levelStructure(subL, all);
		
		tree.print(all);
		
	}
}

打印结果

                                    89


                  18                                  145


          4                34                102               200


    1        7       20       50       100      134      178      300




二、遍历算法
（未完）