Java实现二叉树的建立、计算高度与递归输出操作示例
本文实例讲述了Java实现二叉树的建立、计算高度与递归输出操作。分享给大家供大家参考，具体如下：
1.建立递归输出计算高度前中后三种非递归输出
publicclassTree_Link{
privateintsave=0;
privateintnow=0;
Scannersc=newScanner(System.in);
/*
*构造函数
*/
Tree_Link(){
}
/*
*链表建立
*/
publicTreeLink_Build(Treehead){
//Treehead=newTree();//头节点
System.out.println("继续code：1");
intflag=sc.nextInt();
if(flag!=1){
returnhead;
}else{
System.out.println("\n\n\n输入节点信息：");
head.SetCode(sc.nextInt());
System.out.println("\n建立左子树code：1否则：0");
flag=sc.nextInt();
if(flag==1){
now++;
TreeLTree=newTree();
head.SetLtree(LTree);
LTree.SetFronttree(head);//设置父母节点
Link_Build(head.GetLtree());
}
System.out.println("\n当前位置："+head.GetCode());
System.out.println("\n建立右子树code：1否则：0");
flag=sc.nextInt();
if(flag==1){
now++;
TreeRtree=newTree();
head.SetRtree(Rtree);
Rtree.SetFronttree(head);//设置父母节点
Link_Build(head.GetRtree());
}
if(now>save){
save=now;
}
now--;
}
returnhead;
}
/*
*输出树
*/
publicTreeoutput(Treehead){
intflag;
if(head.GetCode()==-1){
returnhead;
}else{
System.out.println("\n当前位置："+head.GetCode());
System.out.println(head.GetLtree()!=null);
if(head.GetLtree()!=null){
System.out.println("\n访问左子树:");
output(head.GetLtree());
}
if(head.GetRtree()!=null){
System.out.println("\n访问右子树:");
output(head.GetRtree());
}
}
returnhead;
}
/*
*获得高度
*/
publicintGetSave(){
returnthis.save;
}
/*
*非递归前序遍历
*/
publicvoidFront_Traverse(Treehead){
Treestar=head;//退出标记
intchoose=1;//左
intflag=1;//右
System.out.println("<---前序遍历--->"+head.GetCode());//先访问根
while(true){
if(head.GetLtree()!=null&&choose!=0){
head=head.GetLtree();
System.out.println("<---前序遍历--->"+head.GetCode());//获得信息
flag=1;
}elseif(head.GetRtree()!=null&&flag!=0){
head=head.GetRtree();
System.out.println("<---前序遍历--->"+head.GetCode());
choose=1;
}elseif(flag==0&&choose==0&&head==star){
break;
}else{
if(head==head.GetFronttree().GetRtree()){
flag=0;
choose=0;
}
if(head==head.GetFronttree().GetLtree()){
choose=0;
flag=1;
}
head=head.GetFronttree();
System.out.println("获得父母"+head.GetCode());
System.out.println("\n\n\n");
}
}
}
/*
*非递归中序遍历
*/
publicvoidCenter_Traverse(Treehead){
Treestar=head;//退出标记
intchoose=1;//左
intflag=1;//右
while(true){
if(head.GetLtree()!=null&&choose!=0){
head=head.GetLtree();
flag=1;
}elseif(head.GetRtree()!=null&&flag!=0){
if(head.GetLtree()==null){//因为左边为空而返回
System.out.println("<-1--中序遍历--->"+head.GetCode());
}
head=head.GetRtree();
choose=1;
}elseif(flag==0&&choose==0&&head==star){
break;
}else{
intarea=0;//判断哪边回来
flag=1;
choose=1;
if(head==head.GetFronttree().GetRtree()){
area=1;//右边回来
flag=0;
choose=0;
}
if(head==head.GetFronttree().GetLtree()){
area=2;//左边回来
choose=0;
flag=1;
}
if(head.GetLtree()==null&&head.GetRtree()==null){//因为左边为空而返回
System.out.println("<-2--中序遍历--->"+head.GetCode());
}
head=head.GetFronttree();
if(area==2){//因为左边访问完返回
System.out.println("<-3--中序遍历--->"+head.GetCode());
}
System.out.println("获得父母"+head.GetCode());
System.out.println("\n\n\n");
}
}
}
/*
*非递归后续遍历
*/
publicvoidBottom_Traverse(Treehead){
Treestar=head;//退出标记
intchoose=1;//左
intflag=1;//右
while(true){
if(head.GetLtree()!=null&&choose!=0){
head=head.GetLtree();
flag=1;
}elseif(head.GetRtree()!=null&&flag!=0){
head=head.GetRtree();
choose=1;
}elseif(flag==0&&choose==0&&head==star){
break;
}else{
intarea=0;//判断哪边回来
flag=1;
choose=1;
if(head==head.GetFronttree().GetRtree()){
area=1;//右边回来
flag=0;
choose=0;
}
if(head==head.GetFronttree().GetLtree()){
choose=0;
flag=1;
}
if(head.GetRtree()==null){//因为右边为空而返回
System.out.println("<-1--后序遍历--->"+head.GetCode());
}
head=head.GetFronttree();
if(area==1){
System.out.println("<-2--后序遍历--->"+head.GetCode());
}
System.out.println("获得父母"+head.GetCode());
System.out.println("\n\n\n");
}
}
}
}
2.Tree类实现：
publicclassTree{
privateintcode=-1;
privateTreeFonttree;
privateTreeLtree;
privateTreeRtree;
Tree(){
this.code=-1;
this.Ltree=null;
this.Rtree=null;
}
/*
*树内容查看方法：
*/
publicvoidSetCode(intcode){//设置编号
this.code=code;
}
publicintGetCode(){//获取编号
returnthis.code;
}
/*
*设置父母指针：
*/
publicvoidSetFronttree(TreeFront){
this.Fonttree=Front;
}
publicTreeGetFronttree(){
System.out.println("获得父母");
returnthis.Fonttree;
}
/*
*设置左子女：
*/
publicvoidSetLtree(TreeLtree){
this.Ltree=Ltree;
}
publicTreeGetLtree(){
System.out.println("获得左子树");
returnthis.Ltree;
}
/*
*设置右子女：
*/
publicvoidSetRtree(TreeRtree){
this.Rtree=Rtree;
}
publicTreeGetRtree(){
System.out.println("获得右子树");
returnthis.Rtree;
}
}
3.主函数测试：
publicclassMainActivity{
Scannersc=newScanner(System.in);
publicstaticvoidmain(String[]args){
Treehead=newTree();
Tree_Linklink_1st=newTree_Link();
head=link_1st.Link_Build(head);
System.out.println("Buildsucceed!");
System.out.println("\n二叉树高度-->"+link_1st.GetSave());
link_1st.output(head);
System.out.println("OutputOver!");
System.out.println("\n\n<----------------前------------------>\n前序访问根：");
link_1st.Front_Traverse(head);
System.out.println("\n\n<----------------中------------------>\n中序访问根：");
link_1st.Center_Traverse(head);
System.out.println("\n\n<----------------后------------------>\n后序访问根：");
link_1st.Bottom_Traverse(head);
System.out.println("\n\n\n\nTextover!\n\n\n");
}
}
更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》
希望本文所述对大家java程序设计有所帮助。