Java实现二叉树的建立、计算高度与递归输出操作示例

Java实现二叉树的建立、计算高度与递归输出操作示例

本文实例讲述了java实现二叉树的建立、计算高度与递归输出操作。分享给大家供大家参考，具体如下：

1. 建立 递归输出 计算高度 前中后三种非递归输出

public class Tree_Link {

private int save = 0;

private int now = 0;

Scanner sc = new Scanner(System.in);

/*

* 构造函数

*/

Tree_Link(){

}

/*

* 链表建立

*/

public Tree Link_Build(Tree head){

// Tree head = new Tree();//头节点

System.out.println("继续code：1");

int flag = sc.nextInt();

if(flag != 1){

return head;

}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++;

Tree LTree = new Tree();

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++;

Tree Rtree = new Tree();

head.SetRtree(Rtree);

Rtree.SetFronttree(head);//设置父母节点

Link_Build( head.GetRtree() );

}

if( now > save ){

save = now;

}

now--;

}

return head;

}

/*

* 输出树

*/

public Tree output(Tree head){

int flag;

if(head.GetCode() == -1){

return head;

}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() );

}

}

return head;

}

/*

* 获得高度

*/

public int GetSave(){

return this.save;

}

/*

* 非递归 前序遍历

*/

public void Front_Traverse(Tree head){

Tree star = head;//退出标记

int choose = 1; //左

int flag = 1; //右

System.out.println( "<---前序遍历--->" + head.GetCode() );//先访问根

while(true){

if( head.GetLtree() != null && choose != 0 ){

head = head.GetLtree();

System.out.println( "<---前序遍历--->" + head.GetCode() );//获得信息

flag = 1;

}else if( head.GetRtree() != null && flag != 0 ){

head = head.GetRtree();

System.out.println( "<---前序遍历--->" + head.GetCode() );

choose = 1;

}else if( 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" );

}

}

}

/*

* 非递归 中序遍历

*/

public void Center_Traverse(Tree head){

Tree star = head;//退出标记

int choose = 1; //左

int flag = 1; //右

while(true){

if( head.GetLtree() != null && choose != 0 ){

head = head.GetLtree();

flag = 1;

}else if( head.GetRtree() != null && flag != 0 ){

if(head.GetLtree() == null){//因为左边为空而返回

System.out.println( "<-1--中序遍历--->" + head.GetCode());

}

head = head.GetRtree();

choose = 1;

}else if( flag == 0 && choose == 0 && head == star){

break;

}else{

int area = 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" );

}

}

}

/*

* 非递归 后续遍历

*/

public void Bottom_Traverse(Tree head){

Tree star = head;//退出标记

int choose = 1; //左

int flag = 1; //右

while(true){

if( head.GetLtree() != null && choose != 0 ){

head = head.GetLtree();

flag = 1;

}else if( head.GetRtree() != null && flag != 0 ){

head = head.GetRtree();

choose = 1;

}else if( flag == 0 && choose == 0 && head == star){

break;

}else{

int area = 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 类实现：

public class Tree {

private int code = -1;

private Tree Fonttree;

private Tree Ltree;

private Tree Rtree;

Tree(){

this.code = -1;

this.Ltree = null;

this.Rtree = null;

}

/*

* 树内容查看方法：

*/

public void SetCode(int code){//设置编号

this.code = code;

}

public int GetCode(){ //获取编号

return this.code;

}

/*

* 设置父母指针：

*/

public void SetFronttree(Tree Front){

this.Fonttree = Front;

}

public Tree GetFronttree(){

System.out.println("emFwYD获得 父母");

return this.Fonttree;

}

/*

* 设置左子女：

*/

public void SetLtree(Tree Ltree){

this.Ltree = Ltree;

}

public Tree GetLtree(){

System.out.println("获得左子树");

return this.Ltree;

}

/*

* 设置右子女：

*/

public void SetRtree(Tree Rtree){

this.Rtree = Rtree;

}

public Tree GetRtree(){

System.out.println("获得右子树");

return this.Rtree;

}

}

3. 主函数测试：

public class MainAhttp://ctivity {

Scanner sc = new Scanner(System.in);

public static void main(String[] args) {

Tree head = new Tree();

Tree_Link link_1st = new Tree_Link();

head = link_1st.Link_Build(head);

System.out.println("Build succeed !");

System.out.println("\n二叉树高度-->" + link_1st.GetSave());

link_1st.output(head);

System.out.println("Output Over !");

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\nText over !\n\n\n");

}

}

更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。