一、二叉树

     特点最多度为2，有左右之分。

     第i层最多有有个节点。

     K层总得最多有个节点。

     终端节点要比度为2的树节点多一个。

二、存储

       存储既可以用数组因为子树的个数是定的、也可以用链表。

public class BinaryTree {	private BinaryTree left;	private BinaryTree rigth;	private int number;}

创建一个二叉树

/**	 * 创建一个二叉树	 */	public BinaryTree createBinaryTree(){		BinaryTree headTree=new BinaryTree(); 		int input=-1;//如果输入是-1结束树的创建 		Scanner sc=new Scanner(System.in); 		 		System.out.print("请输入当前节点的值："); 		input=sc.nextInt(); 		if(input==-1)return null; 		        headTree.setNumber(input);        System.out.print("请输入左子树的值：");        headTree.setLeft(createBinaryTree());        System.out.print("请输入右子树的值：");        headTree.setRigth(createBinaryTree());        		return headTree;	}

三、二叉树的遍历

先序、中序、后序 都是深度遍历

借助于栈广度遍历

先序遍历

/**	 * 二叉树的先序遍历 中左右	 */	public void PreOrderTraverse(BinaryTree bt){		if(bt!=null){			System.out.println("当前节点值："+bt.getNumber());			PreOrderTraverse(bt.getLeft());			PreOrderTraverse(bt.getRigth());		}	}

中序遍历

/*	 * 二叉树的中序遍历 左中右	 */	public void midOrderTraverse(BinaryTree bt){		if(bt!=null){			midOrderTraverse(bt.getLeft());			System.out.println("当前节点值："+bt.getNumber());			midOrderTraverse(bt.getRigth());		}	}

后序遍历

/*	 * 二叉树的后序遍历 左右中	 */	public void afterOrderTraverse(BinaryTree bt){		if(bt!=null){			afterOrderTraverse(bt.getLeft());			afterOrderTraverse(bt.getRigth());			System.out.println("当前节点值："+bt.getNumber());		}	}

非递归先序

/**	 * 非递归先序遍历	 */	public void preOrderNoRecursive(BinaryTree bt){		Stack
    
      btStack=new Stack
     
      ();		if(bt==null)return;	while(bt!=null||!btStack.isEmpty()){			while(bt!=null){			System.out.println("当前节点值："+bt.getNumber());			btStack.add(bt);			bt=bt.getLeft();		}				if(!btStack.isEmpty()){			bt=btStack.pop();			bt=bt.getRigth();		}	}	}
     
    

非递归中序遍历

/**	 * 非递归中序遍历	 */	public void midOrderNoRecursive(BinaryTree bt){	Stack
    
      btStack=new Stack
     
      ();	while(bt!=null||!btStack.isEmpty()){			while(bt!=null){			btStack.add(bt);			bt=bt.getLeft();		}				if(!btStack.isEmpty()){			bt=btStack.pop();			System.out.println("当前节点值："+bt.getNumber());			bt=bt.getRigth();		}	}			}
     
    

非递归后序

/**	 * 非递归后序遍历	 */	public void afterOrderNoRecursive(BinaryTree bt){		Stack
    
      btStack=new Stack
     
      ();		Stack
      
        btStackFlag=new Stack
       
        ();		while(bt!=null||!btStack.isEmpty()){				while(bt!=null){				btStack.add(bt);				btStackFlag.add(false);				bt=bt.getLeft();			}						if(!btStack.isEmpty()){				bt=btStack.pop();				Boolean flag=btStackFlag.pop();				if(!flag){					btStackFlag.push(true);					btStack.push(bt);					bt=bt.getRigth();				}else{				    System.out.println("当前节点值："+bt.getNumber());				    bt=null;				}			}		}	}
       
      
     
    

 四、二叉树的推导

没有中序时无法推到结果的