package myTest;
import java.util.ArrayList;
//二叉树的节点类，你可以将它写成内部类的形式
class BTreeNode {
int data;
BTreeNode Left;
BTreeNode Right;
public BTreeNode(int data) {
this.data=data;
this.Left=null;
this.Right=null;
}
public BTreeNode(int data,BTreeNode Left,BTreeNode Right) {
this.data=data;
this.Left=Left;
this.Right=Right;
}
public BTreeNode getLeft() {
return Left;
}
public void setLeft(BTreeNode Left) {
this.Left = Left;
}
public BTreeNode getRight() {
return Right;
}
public void setRight(BTreeNode Right) {
this.Right = Right;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
}
//二叉树的创建
//(1)* 创建树
//*
//* 以完全二叉树的格式来创建（子树不存在的用-1填充），
//* 对完全二叉树中每一个节点从0开始进行编号，
//* 那么第i个节点的左孩子的编号为2*i+1，右孩子为2*i+2。
public class BTreeFactory{
/*完全二叉树格式+for循环建立二叉树
*for循环创建。基本思路是先针对输入数组产生相同大小的节点对象数组，存储这些节点对象的引用变量和对应的数据存储到一个数组中。
*之后用for循环再进行Left和Right的保存
*/
public static BTreeNode CreateTree1(int[]a,int k){
ArrayList<BTreeNode>aList=new ArrayList<BTreeNode>();
if(a.length==0) return null;
for(int i=0;i<a.length;i++)
{ //-1表示该位置处节点为空
if(a[i]!=-1){aList.add(new BTreeNode(a[i]));}
else {aList.add(null);}
}
//针对前N/2的节点的Left和Right进行赋值
for(int i=0;i<aList.size()/2;i++){
if(aList.get(i)!=null){
aList.get(i).Left=aList.get(2*i+1);
if((2*i+2)<aList.size())
{aList.get(i).Right=aList.get(2*i+2);}
}
}
return aList.get(0);
}
/*完全二叉树的输入格式+递归法
*/
public static BTreeNode CreateTree2(int[]a,int k){
if(a.length==0) return null;//如果数组长度为0，则不创建节点
if(k>(a.length-1)) return null;//遍历完了数组中所有的值
if(a[k]==-1) return null;//如果当前值为-1，则不建立节点
BTreeNode root=new BTreeNode(a[k]);//创建当前节点
root.Left=CreateTree2(a, 2*k+1);
root.Right=CreateTree2(a,2*k+2);
return root;
}
/*根据先序遍历和中序遍历创建二叉树
*/
public static int[] GetPartArray(int[]a,int start,int end){
if(end<start) return null;
int[]aa=new int[end-start+1];
for(int i=start;i<=end;i++){
aa[i-start]=a[i];
}
return aa;
}
public static int GetPosition(int[]a,int target){
int pos=-1;
for(int i=0;i<a.length;i++){
if(a[i]==target) {pos=i;break;}
}
return pos;
}
/*根据先序遍历和中序遍历创建二叉树
*/
public static BTreeNode CreateTree3(int[]a,int[]b){
if(a==null) return null;
BTreeNode root=new BTreeNode(a[0]);
if(a.length==1)
{root.Left=null;
root.Right=null;}
else{int Posroot=GetPosition(b,a[0]);
root.Left=CreateTree3(GetPartArray(a, 1, Posroot),GetPartArray(b, 0, Posroot-1));
root.Right=CreateTree3(GetPartArray(a, Posroot+1, a.length-1),GetPartArray(b, Posroot+1, a.length-1));
}
return root;
}
/*根据中序遍历和后序遍历建立二叉树
*
*/
public static BTreeNode CreateTree4(int[]b,int[]c){
if(c==null) return null;
BTreeNode root=new BTreeNode(c[c.length-1]);
if(c.length==1)
{root.Left=null;
root.Right=null;}
else{int Posroot=GetPosition(b,c[c.length-1]);
root.Left=CreateTree4(GetPartArray(b, 0, Posroot-1),GetPartArray(c, 0, Posroot-1));
root.Right=CreateTree4(GetPartArray(b, Posroot+1, b.length-1),GetPartArray(c, Posroot, c.length-2));
}
return root;
}
/*先序遍历输出一个二叉树
*
*/
public static void PrePrintBTree(BTreeNode root){
if(root==null)
{return;}
else
{System.out.println(root.data);
PrePrintBTree(root.Left);
PrePrintBTree(root.Right);
}
}
/*中序遍历输出一个二叉树
*
*/
public static void MidPrintBTree(BTreeNode root){
if(root==null)
{return;}
else
{MidPrintBTree(root.Left);
System.out.println(root.data);
MidPrintBTree(root.Right);
}
}
/*后序遍历输出一个二叉树
*
*/
public static void LastPrintBTree(BTreeNode root){
if(root==null)
{return;}
else
{LastPrintBTree(root.Left);
LastPrintBTree(root.Right);
System.out.println(root.data);
}
}
public static void main(String[]args){
//完全二叉树层序遍历格式的输入
int[]arr={89,73,82,-1,-1,92,5,-1,-1,-1,-1,69};
//完全二叉树格式的输入+递归法创建
BTreeNode root=CreateTree2(arr,0);
//先序遍历
System.out.println("先序遍历:");
PrePrintBTree(root);
//中序遍历
System.out.println("中序遍历:");
MidPrintBTree(root);
//后序遍历
System.out.println("后序遍历:");
LastPrintBTree(root);
//完全二叉树格式先序遍历的输入+for循环创建
BTreeNode root2=CreateTree1(arr,0);
//先序遍历
System.out.println("先序遍历:");
PrePrintBTree(root2);
//中序遍历
System.out.println("中序遍历:");
MidPrintBTree(root2);
//后序遍历
System.out.println("后序遍历:");
LastPrintBTree(root2);
//以先序加中序的数组来创建一个二叉树
int[]a={5,2,1,4,3,6,8,7,9,11,10};//先序遍历结果
int[]b={1,2,3,4,5,6,7,8,9,10,11};//中序遍历结果
int[]c={1,3,4,2,7,10,11,9,8,6,5};//后序遍历结果
BTreeNode root3=CreateTree3(a, b);
//先序遍历
System.out.println("先序遍历:");
PrePrintBTree(root3);
//中序遍历
System.out.println("中序遍历:");
MidPrintBTree(root3);
//后序遍历
System.out.println("后序遍历:");
LastPrintBTree(root3);
BTreeNode root4=CreateTree4(b, c);
//先序遍历
System.out.println("先序遍历:");
PrePrintBTree(root4);
//中序遍历
System.out.println("中序遍历:");
MidPrintBTree(root4);
//后序遍历
System.out.println("后序遍历:");
LastPrintBTree(root4);
}
}
