本文实例讲述了java实现二叉树的建立、计算高度与递归输出操作。分享给大家供大家参考，具体如下：
1. 建立 递归输出 计算高度 前中后三种非递归输出
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 |
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 类实现：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
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("获得 父母"); 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. 主函数测试：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
public class mainactivity { 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程序设计有所帮助。
原文链接：https://blog.csdn.net/qq_43377749/article/details/83475907
查看更多关于Java实现二叉树的建立、计算高度与递归输出操作示例的详细内容...